Lesson 7: Iterators and algorithms

In our previous lesson (Lesson 6: STL containers), we have discovered that in C++ there are several different kinds of container that can be used to store data structures.

Putting things into a container is not enough, sooner or later we will need to manipulate the content of the container, or at least to get access to them.

The easiest way to access an element of a container is to use an iterator. To understand the meaning of iterator, one can use this rule of three:

container : array = iterator : pointer

We can use six different kinds of iterators:

1. input_iterator: read values with forward movement. These can be incremented, compared, and dereferenced.
2. output_iterator: write values with forward movement. These can be incremented and dereferenced.
3. forward_iterator: read or write values with forward movement. These combine the functionality of input and output iterators with the ability to store the iterators value.
4. bidirectional_iterator: read and write values with forward and backward movement. These are like the forward iterators, but you can increment and decrement them.
5. random_iterator: read and write values with random access. These are the most powerful iterators, combining the functionality of bidirectional iterators with the ability to do pointer arithmetic and pointer comparisons.
6. reverse_iterator: either a random iterator or a bidirectional iterator that moves in reverse direction.

Would like to see an example? Here you have it...

#include <iostream>
#include <vector>

using namespace std;

int main() {

   // define a vector of integer
   vector< int > aVector;

   // fill in the vector with some numbers
   const int n = 100;
   for ( int i = 0; i < n; i++ ) {
      aVector.push_back( n - i ) ;
   }

   // sum up the content
   int total = 0;

   // prepare an iterator for a vector of integer using the
   // static member iterator of the vector container
   vector< int >::iterator myIterator;

   // initialize the iterator to the first element of the vector
   myIterator = aVector.begin();

   // start looping till the end of the vector
   while ( myIterator != aVector.end() ) {
      // to get the value pointed by myIterator
      // you have to derefence it using the * operator
      total += (*myIterator);

      // the pointer algebra is valid for iterator as well
      // this is moving the iterator one position forward
      ++myIterator;
   }

   // print out the sum and exit
   cout << "The sum is " << total << endl;
 
   return 0;
}

Note that the end of a vector is not the last element, but it correspond to the position of the first element not belonging to the vector. This is necessary if you want to loop over all components, as we did in the example above, and if you want to add another element at the end.

What can we do on the elements of a container?

In principle, we can manipulate the elements of a container as we wish using the iterators, but before typing your own code, you should have a look at what is already available in the STL algorithm. Using these standard procedures is the best way especially for newbie, because they are by far more optimized with respect of whatever a newcomer can write and moreover they are tested bugfree!

STL algorithms can be classified in say 5 major categories:

1. Non-modifying sequence operations: like searching for an element or a range of elements in the container.
2. Modifying sequence operations: like copying, replacing and rearrange the elements of the container.
3. Sorting: a very important category. It gives the users the possibility to rearrange the elements of the container according to a specific sorting function.
4. Binary search (operating on sorted ranges): contains several tools for finding elements in the container. These algorithms are much faster than the non-modifying find because it takes advantage from the fact that the elements are sorted already.
   
5. Min/max: not too much complicated, but so frequently used in programming...

A complete list of all the algorithms is available for example on this page. I think that the best way to understand how they works is looking at an example...

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template< typename T >
void printElements( T i ) {
   cout << " " << i ;
}

int main() {

   // prepare an array of integers
   int myints[] = { 5, 23, 33, 15, 6, 7 };

   // convert the array into a vector
   vector< int > myVector( myints, myints + 6 );

   // define a general purpose iterator
   vector< int >::iterator myIterator;

   // first of all find the largest element in the range
   // using the max_element
   myIterator = max_element( myVector.begin() , myVector.end()) ;

   cout << "The largest int in the vector is " << (*myIterator) << endl;

   // now sort the elements
   sort( myVector.begin() , myVector.end() );

   // print each elements
   cout << "This is the sorted vectors " ;
   for_each( myVector.begin(), myVector.end(), printElements< int > );
   cout << endl;


   // now make a binary search for a specific element
   int targetValue = 13;

   // insert the targetValue into the vector w/o changing the order
   myIterator = upper_bound( myVector.begin(), myVector.end() , targetValue );
   myVector.insert( myIterator, targetValue );

   // reprint the elements
   cout << "This is the sorted enlarged vectors " ;
   for_each( myVector.begin(), myVector.end(), printElements< int > );
   cout << endl;

   return 0;
}

I believe that is example is a good starting point, but you may want to know more. So far, we used only containers filled in with built-in types, but what happens when we want to use algorithms with user-defined types? The only difference is that you need to define all the comparison functions for your type... If you want to abide to Object Orientation, instead of defining functions making comparison you should use specific objects doing the same jobs.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// forward declarations
class MyInt;
ostream& operator << ( ostream&, const MyInt& );

// declare a class MyInt containing an
// integer value
class MyInt {

 public:
   int i;

   // within the class define as an element
   // another class taking care of sorting
   class MyIntLesser {

    public:

      bool  operator() ( MyInt a, MyInt b ) {
         return a.i < b.i ;
      }

   } isLess;

   // now another element for printing
   class MyIntPrinter {

    public:
      void operator() ( MyInt a ) {
         cout << " " <<  a ;
      }
   } print;

};

// overload the operator<<
ostream& operator<< ( ostream& s, const MyInt& a ) {

   s << a.i ;
   return s;
}

int main() {

   // prepare a vector of MyInt
   vector< MyInt > myVec;

   // create a MyInt
   MyInt myInt;

   const int n = 10;

   // fill in the vector with some MyInt
   for ( int i = 0 ; i < n ; i++ ) {

      myInt.i = n - i;
      myVec.push_back( myInt );
   }

   // print the vector out
   cout << "Before sorting ... " ;
   for_each( myVec.begin(), myVec.end(), myInt.print );
   cout << endl;

   // sort the vector in ascending order
   sort ( myVec.begin(), myVec.end(), myInt.isLess );

   cout << "After  sorting ... " ;
   for_each( myVec.begin(), myVec.end(), myInt.print );
   cout << endl;

   return 0;

}

Give it a try and start playing with STL algorithms...