Iterator

Iterators are classes that traverse containers. They are used because sometimes it is imposible to look at the elements of a container without changin the container e.g. stack or knowing if anything is in it e.g. table.

There must be at least three functions for an iterator. They may vary language to language but they must allow the iterator to go through each element one by one and edit them. In Java the functions are hasNext(), is their more of the container to travers, next(), move the container one spot and return the element, and remove(), remove the element at the current position.

In C++ there are serval types of iterators, but they all have three/four functions. begin() returns the iterator at the begining of the container. end() returns true if the iterator is one more than the very last element in the container. (This allows it to be used in loops very easily.) Finally there is an advance and get/dereference function by overloading the operators ++ and * respectivly.

Usage

Probably the best way to understand an itertor is to see some examples of them. This is a traversal of a binary tree in which ten is added to all its values.

BTNode root;
BTNodeIter it(root);  //make an iterator attached to root
it.begin();           //set it to the begining
while(!it.end())      //while not at the end
{
   *it = *it + 10;    //add 10 to the element
   it++;              //advance one spot
}

Here's another example using Java style functions. Let's say Bob is know for cutting all the time so let's remove him from the queue and place him at the end.

StringQueue line;
StrQIter sqit = line.iterator();      //gets an iterator of line 
bool found = false;                   //while not found and the iter has more
while(!found && sqit.hasNext())   //stuff after it
{    
   string s = sqit.next();   //advance it and get the element
   if(s == "Bob")                        
   {
      sqit.remove();         //ditch Bob
      found = true;
   }
}
line.enqueue("Bob"); 

Implementation

In previous examples I have no clue as how the iterators are imlemented. This reemphasises the fact that classes should works are they are described as. Pointers to the elements, references to memory, or even intergers holding an index values can be iterators, so long as they work.

The other issue on iterators is how they relate to the container they traverse. The first way is to have the iterator separate from the container. Most likely it will hold a pointer to the container and make intricit usages of its functions. This is good but there are some problems. First their could be conflict in names since iterator is a concept and common class for containers. Is it to a linked list, stack, table...? The second problem is when the container changes while the iterator is working. This could cause a conflict with the iterator and an exception or program failure is the best solution. However this can be bad or tedious programing for the user.

The other and probably more usefull way is nest the iterator class in the container class. Now we can be sure that this iterator pertains to this type of container class.

To demonstrate the iterator one will be implemented for the Table. From the containers so far, it is the only one in which it cannot be traversed easily, since keys are the only means to obtain values. Since C++ is the main language for this site a C++ style iterator will be implemented, so the functions begin(), end(), ++, and * will be included. Since the Table is just an array of pairs let's make the interger just a refernence to its container and a interger holding the position of the array. Finally since the Table holds both a Key and value lets have a getKey() to return the Key (a string), and * return the integer value.

class Table
{
   public:
      //Table functions
      
      class Iterator
      {
         public:
            Iterator(const Table& t) : theIter(&t), theSpot(0) {} 
            
            void begin();       //set the iterator to the beginging
            int end();          //is it one more than the end?
            void operator++;    //one up one space
            double& operator*;  //return the current value, reference is there
                                //so the value could be edited
            string getKey();    //return the current key
            
         private:
            const *::Table theIter;  //constant pointer to the container being used
            int theSpot;             //the spot, let -1 be one more than the end  
      };
      friend Num::Iterator; //make sure that Iterator can see Table's members
      
      //the :: everywhere are scope qualifiers, since the classes are nested they
      //make sure that the correct one is being used

   private:
      vector<Pair> theTable;
}

Types of C++ Iterators

Since the C++ language can implement a lot of styles it has five types of iterators, output, input, formal, bi-directtional, and random access. Input and output ones only allow for writing and reading the elements respectivly. Formal iterators are ones that just go forward like Java ones. Bidirection can go forward and backwards like a doublely-linked list, and random acess ones allow imediate indexing like arrays. Here is a table summary of these variations.

All the properties should be understandable except for the Random Access. Since it can direcly acess points (with numbers) there is some order to it. That is why it has a bunch of other stuff like +=, add these two position togeher.

Prev -- Back to Portal -- Next