Container syntax

[sacrebleu]

Tell me about container syntax.

[jerome]

Here's an exerpt from the blog:

The standard container classes included in this release are “typed” class generics to replace the previous “non typed” container classes (List, BinaryTree, and pseudo-template Array, which will be slowly phased out. In the meantime List has been renamed to “OldList”, Array to “OldArray”, and Link to “OldLink”). The new containers are all derived from a base “Container” class from which all containers should derive in order to benefit from generic iteration and new eC syntactic sugar. The provided default containers cover dynamic arrays through the new Array class, link lists through the new classes List and LinkList, associative arrays through the new class Map, as well as AVL trees (a particular type of self balancing binary tree) through the new classes AVLTree and CustomAVLTree. It is somewhat analogous to a subset of the Standard Template Library and its corresponding classes such as std::vector, std::list and std::map, though I believe eC’s approach is generally a lot more elegant.

The syntactic sugar for containers include the array notation, e.g. [ 1, 2, 3 ] to denote a container containing the three integers 1, 2 and 3. It also introduces a “foreach” syntax using the regular for keyword in a new way. The following will print all i in array which are greater than 1:

Code: Select all

Array<int> array { [ 1, 2, 3 ] };
for(i : array; i > 1) PrintLn(i);

Notice how i (which takes the type of the array elements) does not need to be declared. Iterating can be done generically (not knowing what kind of container we’re dealing with) using the Iterator class, for example in the following manner:

Code: Select all

Iterator<int> i { array };
while(i.Next()) PrintLn(i.data);

The indexing operator can also be used directly with the container classes. The following example can be used to count the occurrences of strings, assuming it is repeatedly called with “s” being each string to count. Notice how wordCounts is indexed with “s”.

Code: Select all

Map<String, int> wordCounts { };
wordCounts[s]++;

The container classes can also be used to iterate through infinite collections, or through data contained outside the actual container class.

Please look at the sample in the samples/eC/Containers directory for additional examples, including iterating through the Fibonacci series.

[jerome]

Let's take a look at using a basic dynamic variable width array of integers.

We instantiate an array of int object as such:

Array<int> a { };

We can add int's to the array as such:

a.Add(20);
a.Add(33);

The array will now contain 2 elements that can be accessed as a[0] and a[1]. At the moment, the only optimization regarding how the array grows if elements are added one by one is in the renew implementation of the eC memory manager. One could specify an initial size for the array as such:

Array<int> a { size = 10 };

In which case memory will be pre-allocated for 10 elements and we can directly assign values to
a[0] through a[9] as such:

a[0] = 10;
a[9] = 33;

Alternatively, the minAllocSize can be set to ensure a minimal size, without affecting the number of elements in the array. minAllocSize can be used e.g. to implement a factored growth array.

To iterate through the array, one can use the for(i : a) PrintLn(i) syntax, or an iterator, as such:

Code: Select all

Iterator<int> it { a };
while(it.Next())
   PrintLn(i);

To remove an element from the array, one should use the iterator after it has been positioned at the proper place:

it.Remove();

Each particular container class has its own implementation for the iterators, and so the meaning of Iterator::pointer changes from one to the other. For the case of the array, the pointer represents the address of the element. This can be used to directly point an iterator to a particular element, but is considered an advanced technique. It is also possible to directly call the Container methods by casting the right pointer to an IteratorPointer.

The difference between Remove() and Delete(), and similarly RemoveAll() and Free() for the containers, is that Remove simply takes out the element of the container, without freeing the element itself. There is no difference here in the case of the Array<int>, because int types can not be freed. However, if we had an array of either a class or headless class ( class : struct ), each individual element will be deleted (or at least reference decremented) upon a call to Delete() or Free().

[jerome]

eC currently provides two levels of link lists, both doubly linked.

The difference lies in whether you want the linking members of each node to be within the same class as the data, or to be separate objects that 'hold' the data.

If you want to have data 'holders', therefore not having the prev/next members inside each of your elements, you want to use the List class. If you want to have the linking built in your element data type, e.g. because you want to save an indirection level or because you often need to query the previous or next element given one, then you want to use the LinkList class.

Using both List and LinkList bears similarity and common features with the other containers such as the Array:

Code: Select all

List<int> l { };
l.Add(1);
l.Add(2);

The iterator pointer for a List will be the linking node (the data holder). The Container class also provides generic iterators for the first and last element: firstIterator and lastIterator.

With the LinkList class, each element linked should be a class (either a regular or headerless class) containing a LinkElement data member. Furthermore, the LinkList should know where that LinkElement is located in the class. This is done easily by making linked items inheriting from the ListItem class:

Code: Select all

class MyItem : private ListItem
{
public:
   int something;
};
 
LinkList<MyItem> l { };

However, this is not possible if one requires the class to be a regular class (because ListItem is a headerless class), or if one desires to inherit from another class. The solution in this case is to simply provide your own LinkElement, and specify in the LinkList generic parameters which LinkElement to use. It is also possible to have multiple LinkElements in the element class, and therefore link the elements differently in different lists. Note the use of a union in the following example to provide an easy way to access the previous and next elements.

Code: Select all

class MyItem : SomethingElse
{
public:
   int something;
   union
   {
      LinkElement<thisclass> link;
      struct { thisclass prev, next; };
   };
}
 
LinkList<MyItem, link = MyItem::link> l { };

The LinkList class also has an additional generic parameter 'circ' which can be set to true if one wants a circular link list, that is the last element's next pointer will point to the first, and the first element's prev pointer will point to the last.

Another interesting thing to point out is the Container::Insert method, which positions where an element is inserted according to an 'after' IteratorPointer parameter. This 'after' is the IteratorPointer of the element after which we wish to insert the new element, and null if we want to insert it as the first element of the container.

Note that this Insert method, although it is in the Container class, is mostly designed after the LinkList, and perhaps makes most sense with it. It is a little bit awkward to use Insert in that way with the Array class for example. To insert an element at the head of an array, the IteratorPointer should be null, and to insert it at the second place in the array, the 'after' IteratorPointer should be the actual first element of the array (which can seem a little awkward, since we want to insert it at the second position). I believe this should be solved by adding an InsertAtIndex or the like which makes more sense with arrays.

[fedor_bel]

Dear Jerome,

Is it possible to beautifully iterate through the container elements backwards?
Like, this is great

Code: Select all

Array<int> array { [ 1, 2, 3 ] };
for(i : array; i > 1) PrintLn(i);

But, what if I want to iterate from the last element to the first?

The same here

Code: Select all

Iterator<int> it { a };
while(it.Next())
   PrintLn(i);

But what if I want to delete some elements from a collection, I would prefer to iterate the collection elements backwards, from the last to the first.
Is there a sintactic sugar for backward array iteration?

Cheers,
Fedor

[jerome]

Iterating backwards: there is no elegant 'for' syntax for that at the moment. The most elegant way to do this would be:

Code: Select all

Array<int> a { [ 1, 2, 3 ] };
while(it.Prev())
   { int i = it.data; if(i > 1) PrintLn(i); }

As for safely deleting element from a collection, the usual way to do this is by calling the 'Remove' method of the Iterator. That will invalidate the iterator, effectively making the next call to 'Next()' reset to the first element, or the next call to 'Prev()' to the last element. So in your case you could do a:

Code: Select all

while(it.Prev()) it.Remove();

However, each collection class has its own type of implementation, and in the case of the Array this will be highly inefficient and do a reallocation for each Remove(). If you want to free the whole thing you should invoke RemoveAll() on the container, or Free() in case you wish the destructor of each element contained in the array to be invoked as well.

Hope this helps. Please ask if you're looking for further details about this

Cheers,

Jerome