Example with iterators


1. Why using iterators

The iterator concept is very powerful traversing lists, maps and sets. Look at following code:


TSingleLinkedList<Int> lstData;
fillList(lstData, 100); //fucntion to fill the list with n elements

for(Int i = 0; i < lstData.getCount(); i++)
{
  foo(lstData[i]); //index the i-th value
}

This code produces a lot of instructions because the single linked list has to start indexing the i-th item from the beginning. The time complexity of this simple loop is O(n²).


1st:  0
2nd:  0-1
3rd:  0-1-2
4th:  0-1-2-3
...
10th: 0-1-2-3-4-5-6-7-8-9

We see that a loop from 1 to 10 will produce 55 indexing steps (10 x 11 / 2).

The iterator will now store the last indexing position of the list. This is much more efficient and will reduce the time complexity to O(n).


TIterator<Int> It = lstData.getIterator();
while(It.hasNextItem())
{
  foo(It.getNextItem());
}

2. Zeus-Implementation

2.1 Using smart pointer

Because of the interface concept Zeus-Framework has wrapped the STL iterators, or implemented its own interators. The container interfaces define two methods to get an iterator and one method to release the iterator since we can not use the delete operator for interfaces.


IListIterator<Int>* pIt = lstData.getIterator();
...
lstData.releaseIterator(pIt); //same as pIt->release();

This code is not very convenient, because if we forget to release the iterator there will be a resource leak. There fore we better use smart pointers:


{
  TIterator<Int> It = lstData.getIterator();
  ...
}  //Will automatically release the iterator leaving the scope

2.2 Regular iterator

The regular iterator is non const. It allows to change items of the list using this iterator. Following iterators are available:

  • TIterator: Used to iterate lists, maps and sets
  • TMapIterator: Used to iterate a map receiving the keys as well.

TIterator<Int> It = lstData.getIterator();
while(It.hasNextItem())
{
  Int& rValue = It.getNextItem();
  rValue += 10;
}

It.reset();
while(It.hasNextItem())
{
  const Int& rValue = It.getNextItemConst();
  ...
}

The map iterator will also return the key value of the map item:


TMap<Int, Float> mapData;
...
TMapIterator<Int, Float> It = mapData.getIterator();
while(It.hasNextItem())
{
  Int iKey = 0;
  Float fValue = It.getNextItemWithKey(iKey);
  ...
}

2.3 Const iterator

The const iterator is used if the list must be traversed without changing any content. Therefore we use following iterators:


TConstIterator<Int> It = lstData.getIterator();
while(It.hasNextItem())
{
  const Int& rValue = It.getNextItemConst();
  ...
}