Input iterators can only step forward element-by-element with read access. Thus, they return values elementwise. Table 7.2 lists the operations of input iterators.

Note that input iterators can read elements only once. Thus, if you copy an input iterator and let the original and the copy read forward, they might iterate over different values.

Almost all iterators have the abilities of input iterators. However, usually they can have more. A typical example of a pure input iterator is an iterator that reads from the standard input (typically the keyboard). The same value can't be read twice. After a word is read from an input stream (out of the input buffer), the next read access returns another word.

Two input iterators are equal if they occupy the same position. However, as stated previously, this does not mean that they return the same value on element access.

You should always prefer the preincrement operator over the postincrement operator because it might perform better. This is because the preincrement operator does not have to return an old value that must be stored in a temporary object. So, for any iterator pos (and any abstract data type), you should prefer

   ++pos       //OK and fast

rather than

   pos++       //OK, but not so fast

The same applies to decrement operators, as long as they are defined (they aren't for input iterators).

Output iterators are the counterparts of input iterators. They can only step forward with write access. Thus, you can assign new values only element-by-element. You can't use an output iterator to iterate twice over the same range. The goal is to write a value into a "black hole" (whatever that means). So, if you write something for the second time at the same position into the same black hole, it is not guaranteed that you will overwrite a previous value. Table 7.3 lists the valid operations for output iterators. The only valid use of operator * is on the left side of an assignment statement.

Note that no comparison operations are required for output iterators. You can't check whether an output iterator is valid or whether a "writing" was successful. The only thing you can do is to write, and write, and write values.

Usually iterators can read and write values. So, as for input iterators, almost all iterators also have the abilities of output iterators. A typical example of a pure output iterator is an iterator that writes to the standard output (for example, to the screen or a printer). If you use two output iterators to write to the screen, the second word follows the first rather than overwriting it. Another typical example of output iterators are inserters. Inserters are iterators that insert values into containers. If you assign a value, you insert it. If you then write a second value, you don't overwrite the first value; you just also insert it. Inserters are discussed in Section 7.4.2.

Forward iterators are combinations of input and output iterators. They have all the abilities of input iterators and most of those of output iterators. Table 7.4 summarizes the operations of forward iterators.

Unlike input iterators and output iterators, forward iterators can refer to the same element in the same collection and process the same element more than once.

You might wonder why a forward iterator does not have all of the abilities of an output iterator. One restriction applies that prohibits valid code for output iterators from being valid for forward iterators:

This loop does not compile for output iterators because operator ! = is not defined for them.

Bidirectional iterators are forward iterators that provide the additional ability to iterate backward over the elements. Thus, they provide the decrement operator to step backward (Table 7.5).

Random access iterators are bidirectional iterators that can perform random access. Thus, they provide operators for "iterator arithmetic" (in accordance with the "pointer arithmetic" of ordinary pointers). That is, they can add and subtract offsets, process differences, and compare iterators with relational operators such as < and >. Table 7.6 lists the additional operations of random access iterators.

Random access iterators are provided by the following objects and types:

The following program demonstrates the special abilities of random access iterators:

// iter/itercat.cpp

   #include <vector>
   #include <iostream>
   using namespace std;


   int main()
   {
      vector<int> coll;


      //insert elements from
-3 to 9
      for (int i=-3; i<=9; ++i) {
          coll.push_back (i);
      }


      /* print number of elements by processing the distance between beginning and end
* - NOTE: uses operator -for iterators
*/
      cout << "number/distance: " << coll.end()-coll.begin() << endl;


      /* print all elements
* - NOTE: uses operator < instead of operator ! =
       */
      vector<int>::iterator pos;
       for (pos=coll.begin(); pos<coll.end(); ++pos) {
           cout << *pos << ' '; 
       }
       cout << endl;


       /* print all elements
* - NOTE: uses operator [ ] instead of operator *
        */
       for (int i=0; i<coll.size(); ++i) {
           cout << coll.begin() [i] << ' ';
       }
       cout << endl;


       /* print every second element
* - NOTE: uses operator +=
*/
       for (pos = coll.begin(); pos < coll.end()-1; pos += 2) {
           cout << *pos << ' ';
       }
       cout << endl;
   }

The output of the program is as follows:

   number/distance: 13
   −3 −2 −1 0 1 2 3 4 5 6 7 8 9
   −3 −2 −1 0 1 2 3 4 5 6 7 8 9
   −3 −1 1 3 5 7

This example won't work with lists, sets, and maps because all operations that are marked with NOTE: are provided only for random access iterators. In particular, keep in mind that you can use operator < as an end criterion in loops for random access iterators only.

Note that in the last loop the expression

   pos < coll.end()−1

requires that coll contains at least one element. If the collection was empty, coll.end() −1 would be the position before coll.begin(). The comparison might still work; but, strictly speaking, moving an iterator to before the beginning results in undefined behavior. Similarly, the expression pos += 2 might result in undefined behavior if it moves the iterator beyond the end() of the collection. Therefore, changing the final loop to the following is very dangerous because it results in undefined behavior if the collection contains an even number of elements (Figure 7.2):

Figure 7.2. Incrementing Iterators by More than One Element

   for (pos = coll.begin(); pos < coll.end(); pos += 2) {
       cout << *pos << ' ';
   }

The use of the increment and decrement operators of iterators includes a strange problem. In general, you can increment and decrement temporary iterators. However, for vectors and strings, you typically can't. Consider the following vector example:

   std::vector<int> coll;
   ...
   //sort, starting with the second element
// - NONPORTABLE version 
   if (coll.size() > 1) {
       sort (++coll.begin(), coll.end());
   }

Typically, the compilation of sort() fails. However, if you use, for example, a deque rather than a vector, it will compile. It might compile even with vectors, depending on the implementation of class vector.

The reason for this strange problem lies in the fact that vector iterators are typically implemented as ordinary pointers. And for all fundamental data types, such as pointers, you are not allowed to modify temporary values. For structures and classes, however, it is allowed. Thus, if the iterator is implemented as an ordinary pointer, the compilation fails; if implemented as a class, it succeeds. It always works with deques, lists, sets, and maps because you can't implement iterators as ordinary pointers for them. But for vectors, whether it works depends on the implementation. Usually, ordinary pointers are used. But if, for example, you use a "safe version" of the STL, the iterators are implemented as classes. To make your code portable you should not code as the previous example, using vectors. Instead, you should use an auxiliary object:

   std::vector<int> coll;
   ...
   //sort, starting with the second element
// - PORTABLE version
   if (coll.size() > 1) {
       std::vector<int>::iterator beg = coll.begin();
       sort (++beg, coll.end()); 
   }

The problem is not as bad as it sounds. You can't get unexpected behavior because it is detected at compile time. But it is tricky enough to spend time solving it. This problem also applies to strings. String iterators are usually also implemented as ordinary character pointers, although this is not required.

The function advance() increments the position of an iterator passed as the argument. Thus, it lets the iterator step forward (or backward) more than one element:

#include <iterator>
void advance (InputIterator& pos, Dist n)

Due to the use of iterator traits (introduced in Section 7.5), the function always uses the best implementation, depending on the iterator category. For random access iterators, it simply calls pos+=n. Thus, for such iterators advance() has constant complexity. For all other iterators, it calls ++pos n times (or −−pos, if n is negative). Thus, for all other iterator categories advance() has linear complexity.

To be able to change container and iterator types, you should use advance() rather than operator +=. However, in doing so be aware that you risk unintended worse performance. This is because you don't recognize that the performance is worsening when you use other containers that don't provide random access iterators (bad runtime is the reason why operator += is provided only for random access iterators). Note also that advance() does not return anything. Operator += returns the new position, so it might be part of a larger expression. Here is an example of the use of advance():

// iter/advance1.cpp

   #include <iostream>
   #include <list>
   #include <algorithm>
   using namespace std;


   int main()
   {
       list<int> coll;


       //insert elements from 1 to 9
       for (int i=1; i<=9; ++i) {
            coll.push_back(i);
       }


       list<int>::iterator pos = coll.begin();


       //print actual element
       cout << *pos << endl;


       //step three elements forward
       advance (pos, 3);


       //print actual element
       cout << *pos << endl;


       //step three elements backward
       advance (pos, -1);


       //print actual element
       cout << *pos << endl; 
   }

In this program, advance() lets the iterator pos step three elements forward and one element backward. Thus, the output is as follows:

   1
   4
   3

Another way to use advance() is to ignore some input for iterators that read from an input stream. See the example on page 282.

The distance() function is provided to process the difference between two iterators:

#include <iterator>
Dist distance (InputIterator pos1, InputIterator pos2)

By using iterator tags, this function uses the best implementation according to the iterator category. For random access iterators, it simply returns pos2−pos1. Thus, for such iterators distance() has constant complexity. For all other iterator categories, pos1 is incremented until it reaches pos2 and the number of incrementations is returned. Thus, for all other iterator categories distance() has linear complexity. Therefore, distance() has bad performance for other than random access iterators. You should consider avoiding it.

The implementation of distance() is described in Section 7.5.1. The following example demonstrates its use:

// iter/distance.cpp

   #include <iostream>
   #include <list>
   #include <algorithm>
   using namespace std;


   int main()
   {
       list<int> coll;


       // insert elements from
-3 to 9
       for (int i=-3; i<=9; ++i) {
           coll.push_back(i); 
       }


       // search element with value 5
       list<int>::iterator pos;
       pos = find (coll.begin(), coll.end(),        // range
                   5);                              // value


       if (pos != coll.end()) {
           // process and print difference from the beginning
           cout << "difference between beginning and 5: "
                << distance(coll.begin(),pos) << endl;
       }
       else {
            cout << "5 not found" << endl; 
       } 
   }

find() assigns the position of the element with value 5 to pos. distance() uses this position to process the difference between this position and the beginning. The output of the program is as follows:

   difference between beginning and 5: 8

To be able to change iterator and container types, you should use distance() instead of operator-. However, if you use distance() you don't recognize that the performance is getting worse when you switch from random access iterators to other iterators.

To process the difference between two iterators that are not random access iterators, you must be careful. The first iterator must refer to an element that is not after the element of the second iterator. Otherwise, the behavior is undefined. If you don't know which iterator position comes first, you have to process the distance between both iterators to the beginning of the container and process the difference of these distances. However, you must then know to which container the iterators refer. If you don't, you have no chance of processing the difference of the two iterators without running into undefined behavior. See the remarks about subranges on page 99 for additional aspects of this problem.

In older versions of the STL, the signature of distance() was different. Instead of the difference being returned, it was added to a third argument. This version was very inconvenient because you could not use the difference directly in an expression. If you are using an old version, you should define this simple workaround:

// iter/distance.hpp

   template <class Iterator>
   inline long distance (Iterator pos1, Iterator pos2)
   {
       long d = 0;
       distance (pos1, pos2, d);
       return d;
   }

Here, the return type does not depend on the iterator; it is hard coded as long. Type long normally should be big enough to fit all possible values, however this is not guaranteed.

The following simple auxiliary function is provided to swap the values to which two iterators refer:

#include <algorithm>
void iter_swap (ForwardIterator1 pos1, ForwardIterator2 pos2)

Here is a simple example (function PRINT_ELEMENTS() is introduced in Section 5.7):

// iter/swap1.cpp

   #include <iostream>
   #include <list>
   #include <algorithm>
   #include "print.hpp"
   using namespace std;


   int main() 
   {
       list<int> coll;


       // insert elements from 1 to 9
       for (int i=1; i<=9; ++i) {
           coll.push_back(i); 
       }


       PRINT_ELEMENTS(coll);


       //swap first and second value
       iter_swap (coll.begin(), ++coll.begin());


       PRINT_ELEMENTS(coll);


       //swap first and last value
       iter_swap (coll.begin(), --coll.end());

       PRINT_ELEMENTS(coll);
   }

The output of the program is as follows:

   1 2 3 4 5 6 7 8 9
   2 1 3 4 5 6 7 8 9
   9 1 3 4 5 6 7 8 2

Note that this program normally does not work if you use a vector as a container. This is because ++coll.begin() and −−coll.end() yield temporary pointers (see Section 7.2.6, for details regarding this problem).

Reverse iterators are adapters that redefine increment and decrement operators so that they behave in reverse. Thus, if you use these iterators instead of ordinary iterators, algorithms process elements in reverse order. All standard container classes provide the ability to use reverse iterators to iterate over their elements. Consider the following example:

// iter/reviter1.cpp

   #include <iostream> 
   #include <list>
   #include <algorithm>
   using namespace std;


   void print (int elem) 
   {
       cout << elem << ' ';
   }


   int main()
   {
       list<int> coll;


       //insert elements from 1 to 9
       for (int i=1; i<=9; ++i) {
            coll.push_back(i);
       }


       //print all elements in normal order
       for_each (coll.begin(), coll.end(),      //range
                 print);                        //operation
       cout << endl;


       //print all elements in reverse order
       for_each (coll.rbegin(), coll.rend(),    //range
                 print);                        //operations
       cout << endl; 
   }

The rbegin() and rend() member functions return a reverse iterator. According to begin() and end(), these iterators define the elements to process as a half-open range. However, they operate in a reverse direction:

Iterators and Reverse Iterators

You can convert normal iterators to reverse iterators. Naturally, the iterators must be bidirectional iterators, but note that the logical position of an iterator is moved during the conversion. Consider the following program:

// iter/reviter2.cpp

   #include <iostream>
   #include <vector>
   #include <algorithm>
   using namespace std;


   int main() 
   {
       vector<int> coll;


       //insert elements from 1 to 9
       for (int i=1; i<=9; ++i) {
            coll.push_back(i);
       }


       //find position of element with value 5
       vector<int>::iterator pos;
       pos = find (coll.begin(), coll.end(),
                   5);


       //print value to which iterator pos refers
       cout << "pos: " << *pos << endl;


       //convert iterator to reverse iterator rpos
       vector<int>::reverse_iterator rpos(pos);


       //print value to which reverse iterator rpos refers
       cout << "rpos: " << *rpos <<endl;
   }

This program has the following output:

   pos:  5
   rpos: 4

Thus, if you print the value of an iterator and convert the iterator into a reverse iterator, the value has changed. This is not a bug; it's a feature! This behavior is a consequence of the fact that ranges are half-open. To specify all elements of a container, you must use the position after the last argument. However, for a reverse iterator this is the position before the first element. Unfortunately, such a position may not exist. Containers are not required to guarantee that the position before their first element is valid. Consider that ordinary strings and arrays might also be containers, and the language does not guarantee that arrays don't start at address zero.

As a result, the designers of reverse iterators use a trick: They "physically" reverse the "half-open principle." Physically, in a range defined by reverse iterators, the beginning is not included, whereas the end is. However, logically, they behave as usual. Thus, there is a distinction between the physical position that defines to which element the iterator refers and the logical position that defines to which value the iterator refers (Figure 7.3). The question is, what happens on a conversion from an iterator to a reverse iterator? Does the iterator keep its logical position (the value) or its physical position (the element)? As the previous example shows, the latter is the case. Thus the value is moved to the previous element (Figure 7.4).

Figure 7.3. Position and Value of Reverse Iterators

Figure 7.4. Conversion Between Iterator pos and Reverse Iterator rpos

You can't understand this decision? Well, it has its advantages: You have nothing to do when you convert a range that is specified by two iterators rather than a single iterator. All elements stay valid. Consider the following example:

// iter/reviter3.cpp

   #include <iostream>
   #include <deque>
   #include <algorithm>
   using namespace std;


   void print (int elem)
   {
        cout << elem << ' ';
   }


   int main()
   {
       deque<int> coll;


       //insert elements from 1 to 9
       for (int i=1; i<=9; ++i) {
           coll.push_back(i);
       }


       //find position of element with value 2
       deque<int>::iterator pos1;
       pos1 = find (coll.begin(), coll.end(),    //range
                    2);                          //value
//find position of element with value 7
       deque<int>::iterator pos2;
       pos2 = find (coll.begin(), coll.end(),    //range
                    7);                          //value
//print all elements in range [pos1,pos2)
       for_each (pos1, pos2,               //range
                 print);                   //operation
       cout << endl;


       //convert iterators to reverse iterators
       deque<int>::reverse_iterator rpos1(pos1);
       deque<int>::reverse_iterator rpos2(pos2);


      //print all elements in range [pos1,pos2) in reverse order
      for_each (rpos2, rpos1,             //range
                print);                   //operation
      cout << endl; 
   }

The iterators pos1 and pos2 specify the half-open range, including the element with value 2 but excluding the element with value 7. When the iterators describing that range are converted to reverse iterators, the range stays valid and can be processed in reverse order. Thus, the output of the program is as follows:

   2 3 4 5 6
   6 5 4 3 2

Thus, rbegin() is simply:

container::reverse_iterator(end())

and rend() is simply:

   container::reverse_iterator(begin())

Of course, constant iterators are converted into type const_reverse_iterator.

   namespace std {
       template <class Iterator>
       class reverse_iterator ... {
           ...
           Iterator base() const;
           ...
       };
   }

// iter/reviter4.cpp

   #include <iostream>
   #include <list>
   #include <algorithm>
   using namespace std;


   int main()
   {
       list<int> coll;


       //insert elements from 1 to 9 
       for (int i=1; i<=9; ++i) {
            coll.push_back(i);
       }


       //find position of element with value 5
       list<int>::iterator pos;
       pos = find (coll.begin(), coll.end(),    //range
                   5);                          //value
//print value of the element
       cout << "pos: " << *pos << endl;


       //convert iterator to reverse iterator
       list<int>::reverse_iterator rpos(pos);


       //print value of the element to which the reverse iterator refers
       cout << "rpos: " << *rpos << endl;


       //convert reverse iterator back to normal iterator
       list<int>::iterator rrpos;
       rrpos = rpos.base();


       //print value of the element to which the normal iterator refers
       cout << "rrpos: " << *rrpos << endl;
   }

   pos:     5
   rpos:    4
   rrpos:   5

   *rpos.base()

Insert iterators, also called inserters, are iterator adapters that transform an assignment of a new value into an insertion of that new value. By using insert iterators, algorithms can insert rather than overwrite. All insert iterators are in the output iterator category. Thus, they provide only the ability to assign new values (see Section 7.2.2).

   namespace std {
       template <class InputIterator, class OutputIterator>
       OutputIterator copy (InputIterator from_pos,    //beginning of source
                            InputIterator from_end,    //end of source
                            OutputIterator to_pos)     //beginning of dest.
       {
           while (from_pos != from_end) {
               *to_pos = *from_pos;    //copy values
               ++from_pos;             //increment iterators
               ++to_pos;
           }
           return to_pos; 
       }
   }

   *to_pos = value

// iter/backins.cpp

   #include <iostream>
   #include <vector>
   #include <algorithm>
   #include "print.hpp"
   using namespace std;


   int main() 
   {
       vector<int> coll;


       //create back inserter for coll
       // - inconvenient way
       back_insert_iterator<vector<int> > iter(coll);


       //insert elements with the usual iterator interface
       *iter = 1;
       iter++;
       *iter = 2;
       iter++;
       *iter = 3;


       PRINT_ELEMENTS(coll);


       //create back inserter and insert elements
// - convenient way
       back_inserter(coll) = 44;
       back_inserter(coll) = 55;


       PRINT_ELEMENTS(coll);


       //use back inserter to append all elements again 
       copy (coll .begin(), coll.end(),                     //source
             back_inserter(coll));                          //destination
       PRINT_ELEMENTS(coll); 
   }

   1 2 3
   1 2 3 44 55
   1 2 3 44 55 1 2 3 44 55

// iter/frontins.cpp

   #include <iostream>
   #include <list>
   #include <algorithm>
   #include "print.hpp"
   using namespace std;


   int main()
   {
       list<int> coll;


       //create front inserter for coll
       // - inconvenient way
       front_insert_iterator<list<int> > iter(coll);


       //insert elements with the usual iterator interface
       *iter = 1;
       iter++;
       *iter = 2;
       iter++;
       *iter = 3;


       PRINT_ELEMENTS(coll);


       //create front inserter and insert elements
// - convenient way
       front_inserter(coll) = 44;
       front_inserter(coll) = 55;


       PRINT_ELEMENTS(coll);


       //use front inserter to insert all elements again
       copy (coll.begin(), coll.end(),                  //source
             front_inserter(coll));                     //destination

       PRINT_ELEMENTS(coll); 
   }

   3 2 1
   55 44 3 2 1
   1 2 3 44 55 55 44 3 2 1

pos = container .insert (pos, value);
++pos;

// iter/inserter.cpp

   #include <iostream>
   #include <set>
   #include <list>
   #include <algorithm>
   #include "print.hpp"
   using namespace std;


   int main() 
   {
       set<int> coll;


       //create insert iterator for coll
       // - inconvenient way
       insert_iterator<set<int> > iter(coll,coll.begin());


       //insert elements with the usual iterator interface
       *iter = 1;
       iter++;
       *iter = 2;
       iter++;
       *iter = 3;


       PRINT-ELEMENTS(coll,"set: ");


       //create inserter and insert elements
// - convenient way
       inserter(coll,coll.end()) = 44;
       inserter(coll,coll.end()) = 55;


       PRINT_ELEMENTS(coll,"set: ");


       //use inserter to insert all elements into a list
       list<int> coll2;
       copy (coll.begin(), coll.end(),                             //source
             inserter(coll2,coll2.begin()));                       //destination


       PRINT_ELEMENTS(coll2,"list: ");


       //use inserter to reinsert all elements into the list before the second element
       copy (coll.begin(), coll.end(),                             //source
             inserter(coll2,++coll2.begin()));                     //destination


       PRINT_ELEMENTS(coll2,"list: "); 
   }

   set:  1 2 3
   set:  1 2 3 44 55
   list: 1 2 3 44 55
   list: 1 1 2 3 44 55 2 3 44 55

A stream iterator is an iterator adapter that allows you to use a stream as source or destination of algorithms. In particular, an istreams iterator can be used to read elements from an input stream and an ostream iterator can be used to write values to an output stream.

A special form of a stream iterator is a stream buffer iterator, which can be used to read from or write to a stream buffer directly. Stream buffer iterators are discussed in Section 13.13.2, page 665.

   namespace std {
       template <class T,
                 class charT = char,
                 class traits = char_traits<charT> >
       class ostream_iterator; 
   }

// iter/ostriter.cpp

   #include <iostream>
   #include <vector>
   #include <algorithm>
   using namespace std;


   int main()
   {
       //create ostream iterator for stream cout
       // - values are separated by a newline character
       ostream_iterator<int> intWriter (cout,"
");


       //write elements with the usual iterator interface
       *intWriter = 42;
       intWriter++;
       *intWriter = 77;
       intWriter++;
       *intWriter = -5;


       //create collection with elements from 1 to 9
       vector<int> coll;
       for (int i=1; i<=9; ++i) {
           coll.push_back(i); 
       }


       //write all elements without any delimiter 
       copy (coll.begin(), coll.end(),
             ostream_iterator<int> (cout));
       cout << endl;


       //write all elements with " < " as delimiter
       copy (coll.begin(), coll.end(),
             ostream_iterator<int>(cout," < "));
       cout << endl;
   }

   42
   77
   −5
   123456789
   1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 <

   string delim;
   ...
   ostream_iterator<int>(cout,delim.c_str());

   namespace std {
       template <class T,
                 class charT = char,
                 class traits = char_traits<charT>,
                 class Distance = ptrdiff_t>
       class istream_iterator; 
   }

// iter/istriter.cpp

   #include <iostream> 
   #include <iterator>
   using namespace std;


   int main() 
   {
       //create istream iterator that reads integers from cin
       istream_iterator<int> intReader(cin);


       //create end-of-stream iterator
       istream_iterator<int> intReaderEOF;


       /* while able to read tokens with istream iterator
* - write them twice
*/
       while (intReader != intReaderEOF) {
           cout << "once:       " << *intReader << endl;
           cout << "once again: " << *intReader << endl;
           ++intReader;
       }
   }

   1 2 3 f 4

   once:       1
   once again: 1
   once:       2
   once again: 2
   once:       3
   once again: 3

// iter/advance2.cpp

   #include <iostream>
   #include <string>
   #include <algorithm>
   using namespace std;


   int main() 
   {
       istream_iterator<string> cinPos(cin);
       ostream_iterator<string> coutPos(cout," ");


       /* while input is not at the end of the file
* - write every third string
*/
       while (cinPos != istream_iterator<string>()) {
           //ignore the following two strings 
           advance (cinPos, 2);


           //read and write the third string
           if (cinPos != istream_iterator<string>()) {
               *coutPos++ = *cinPos++;
           }
       }
       cout << endl;
   }

   No one objects if you are doing
   a good programming job for
   someone whom you respect.

   objects are good for you

Using iterator traits, you can write generic functions that derive type definitions or use different implementation code depending on the iterator category.

   typename std::iterator_traits<T>::value_type tmp;

   template <class ForwardIterator>
   void shift_left (ForwardIterator beg, ForwardIterator end)
   {
       //temporary variable for first element
       typedef typename
        std::iterator_traits<ForwardIterator>::value_type value_type;


       if (beg != end) {
           //save value of first element
           value_type tmp(*beg);


           //shift following values
           ...
        }
   }

//general distance()
    template <class Iterator>
    typename std::iterator_traits<Iterator>::difference_type
    distance (Iterator pos1, Iterator pos2)
    {
        return distance (pos1, pos2,
                         std::iterator_traits<Iterator>
                            ::iterator_category()); 
    }


    //distance() for random access iterators
    template <class RaIterator>
    typename std::iterator_traits<RaIterator>::difference_type
    distance (RaIterator pos1, RaIterator pos2,
               std::random_access_iterator_tag) 
    {
        return pos2 - pos1; 
    }


    //distance() for input, forward, and bidirectional iterators
    template <class InIterator>
    typename std::iterator_traits<lnIterator>::difference_type
    distance (Inlterator pos1, InIterator pos2,
              std::input_iterator_tag) 
    {
        typename std::iterator_traits<lnIterator>::difference_type d;
        for (d=0; pos1 != pos2; ++pos1, ++d) {
             ;
        }
        return d; 
    }

Let's write an iterator. As mentioned in the previous section, you need iterator traits provided for the user-defined iterator. You can provide them in one of two ways:

For the first way, the C++ standard library provides a special base class, iterator<>, that does the type definitions. You need only to pass the types^[6]:

   class MyIterator
   : public std::iterator <std::bidirectional_iterator_tag,
                           type, std::ptrdiff_t, type*, type&> {
      ...
   };

The first template parameter defines the iterator category, the second defines the element type type, the third defines the difference type, the fourth defines the pointer type, and the fifth defines the reference type. The last three arguments are optional and have the default values ptrdiff_t, type*, and type&. Often it is enough to use the following definition:

    class MyIterator
     : public std::iterator <std::bidirectional_iterator_tag, type> {
        ...
    };

The following example demonstrates how to write a user-defined iterator. It is an insert iterator for associative containers. Unlike insert iterators of the C++ standard library (see Section 7.4.2), no insert position is used.

Here is the implementation of the iterator class:

// iter/assoiter.hpp

   #include <iterator>


   /* template class for insert iterator for associative containers
    */
   template <class Container>
   class asso_insert_iterator
    : public std::iterator <std::output_iterator_tag,
                            void, void, void, void> 
   {
     protected:
       Container& container;   //container in which elements are inserted


     public:
       //constructor
       explicit asso_insert_iterator (Container& c) : container(c) {
       }


       //assignment operator
// - inserts a value into the container
       asso_insert_iterator<Container>&
       operator= (const typename Container::value_type& value) {
           container.insert(value);
           return *this; 
       }


       //dereferencing is a no-op that returns the iterator itself
       asso_insert_iterator<Container>& operator* () {
           return *this; 
       }


       //increment operation is a no-op that returns the iterator itself
       asso_insert_iterator<Container>& operator++ () {
           return *this;
       }
       asso_insert_iterator<Container>& operator++ (int) {
           return *this;
       }
   };


   /* convenience function to create the inserter
*/
   template <class Container> 
   inline asso_insert_iterator<Container> asso_inserter (Container& c)
   {
       return asso_insert_iterator<Container>(c);
   }

The asso_insert_iterator class is derived from the iterator class. The first template argument output_iterator_tag is passed to iterator to specify the iterator category. Output iterators can only be used to write something. Thus, as for all output iterators, element and difference types are void.^[7]

At creation time the iterator stores its container in its container member. Any value that gets assigned is inserted into the container by insert(). Operators * and ++ are no-ops that simply return the iterator itself. Thus, the iterator maintains control. If the usual iterator interface is used

   *pos = value

the *pos expression returns *this to which the new value is assigned. That assignment is transfered into a call of insert(value) for the container.

After the definition of the inserter class, the usual convenient function asso_inserter is defined as convenience function to create and initialize an inserter. The following program uses such an inserter to insert some elements into a set:

// iter/assoiter.cpp

   #include <iostream>
   #include <set>
   #include <algorithm>
   using namespace std;


   #include "print.hpp"


   #include "assoiter.hpp"


   int main()
   {
       set<int> coll;


       //create inserter for coll
       // - inconvenient way
       asso_insert_iterator<set<int> > iter(coll);


       //insert elements with the usual iterator interface
       *iter = 1;
       iter++;
       *iter = 2;
       iter++;
       *iter = 3;


       PRINT_ELEMENTS(coll);


       //create inserter for coll and insert elements
// - convenient way
       asso_inserter(coll) = 44;
       asso_inserter(coll) = 55;


       PRINT_ELEMENTS(coll);


       //use inserter with an algorithm
       int vals[] = { 33, 67, -4, 13, 5, 2 };
       copy (vals, vals+(sizeof(vals)/sizeof(vals[0])),   //source
             asso_inserter(coll));                         //destination


       PRINT_ELEMENTS(coll); 
   }

The output of the program is as follows:

   1 2 3
   1 2 3 44 55
   −4 1 2 3 5 13 33 44 55 67