=====C++ Iterators=====

Iterators are used to access elements of a sequence, and can be used
in a similar manner to pointers. For example, one might use an iterator to step
through the elements of a vector.

The following code creates and uses an iterator with a vector:

<code>
    vector<int> the_vector;
    vector<int>::iterator the_iterator;


    for( int i=0; i < 10; i++ ) the_vector.push_back(i);
    int total = 0;
    the_iterator = the_vector.begin();
    while( the_iterator != the_vector.end() ) {
      total += *the_iterator;
      ++the_iterator;
    }

    cout << "Total=" << total << endl;
</code>

Notice that you can access the elements of the container by dereferencing the
iterator.

NOTES: You should prefer pre-increment operator (''++iter'') to post-increment operator (''iter++'')\\ 
if you are not going to use the old value. \\ 
Post-increment is generally implemented as follows:
<code>
  Iter operator++(int)
  {
    Iter tmp(*this); // store the old value in a temporary object
    ++*this;         // call pre-increment
    return tmp;      // return the old value
  }
</code>

Obviously, it's less efficient than pre-increment. 

\\ 


====Iterator Categories====
Not every kind of iterator has exactly the same abilities. Reading and writing require different abilities.\\ 
Random access is efficient and convenient for a ''vector'', whereas it would be expensive for a ''list''.\\ 
For this reason, iterators are classified into five categories according to their abilities:

^Iterator Category^Description^Providers^
|input_iterator|Read values with forward movement. These can be incremented, compared, and dereferenced.|istream|
|output_iterator|Write values with forward movement. These can be incremented and dereferenced.|ostream, inserter|
|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.| |
|bidirectional_iterator|Read and write values with forward and backward movement. These are like the forward iterators, but you can increment and decrement them.|list, map, multimap, set, multiset|
|random_access_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.|array, deque, string, vector|

Each of the STL containers is associated with a category of iterator,
and each of the [[stl/algorithm/|STL algorithms]] uses a certain category of iterator. 

For example, [[stl/vector/|vectors]] are associated with random-access
iterators, which means that they can use algorithms that require
random access. Since random-access iterators encompass all of the
characteristics of the other iterators, vectors can use algorithms
designed for other iterators as well.

<code>
    vector<int> the_vector(10);
    
    // generate_n requires output_iterator
    generate_n(the_vector.begin(), 5, rand);

    // fill requires forward_iterator
    fill(the_vector.begin()+5, the_vector.end(), 100);

    // random_shuffle requires random_access_iterator
    random_shuffle(the_vector.begin(), the_vector.end());

    // copy requires input_iterator
    copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));

    // reverse_copy requires bidirectional_iterator
    reverse_copy(the_vector.begin(), the_vector.end(), ostream_iterator<int>(cout, " "));
</code>
\\ 

====Auxiliary Iterator Functions====
The ''<iterator>'' header file defines two auxiliary functions.
<code>
  void advance( input_iterator& pos, Dist n );
</code>
''advance()'' lets ''pos'' step ''n'' elements forward (or backward).\\ 
For bidirectional and random_access_iterators, ''n'' can be negative to step backward.\\ 
For random_access_iterators, ''advance()'' runs in constant time (simply calls ''pos''+=''n'').\\
For all other iterators, ''advance()'' has linear complexity (calls ''++pos'' ''n'' times).

<code>
  typename iterator_traits<input_iterator>::difference_type
  distance( input_iterator pos1, input_iterator pos2 );
</code>
''distance()'' returns the distance between two iterators.\\ 
For random_access_iterators, ''distance()'' runs in constant time (simply returns ''pos2'' - ''pos1'').\\
For all other iterators, ''distance()'' runs in linear time ( ''pos1'' is incremented until it reaches ''pos2'', and returns the number of incrementation).

====Invalidating Iterators====
Iterators to exisiting elements in a container can become invalidated when the container is changed. This makes changing the container while iterating it problematic. The containers offer different guarantees in this regard:\\
  * vectors: insert/erase can invalidate all iterators.\\
  * list/map: erase only invalidates iterators to the erased element(s) & no others.\\

\\
\\
Related topics: [[http://www.oreillynet.com/pub/a/network/2005/10/18/what-is-iterator-in-c-plus-plus.html]]