So far, in this chapter we have indicated that containers give access to items through iterators. The implication is that iterators are simply pointers, and this is deliberate because iterators behave like pointers. However, they are usually objects of iterator classes (see the <iterator> header). All iterators have the following behaviors:

Unlike a C++ pointer, which assumes that data is contiguous in memory, iterators can be used for more complex data structures, such as linked lists, where the items may not be contiguous. The operators ++ and -- work as expected, regardless of the underlying storage mechanism.

The <iterator> header declares the next global function that will increment an iterator and the advance function that will change an iterator by a specified number of positions (forward or backward depending on whether the parameter is negative and the direction allowed by the iterator). There is also a prev function to decrement an iterator by one or more positions. The distance function can be used to determine how many items are between two iterators.

All containers have a begin method, which returns the iterator for the first item, and an end method, which returns an iterator after the last item. This means that you can iterate through all items in the container by calling begin and then incrementing the iterator until it has the value returned from end. The * operator on an iterator gives access to the element in the container, and if the iterator is read-write (as it will be if returned from the begin method) it means the item can be changed.

Containers also have the cbegin and cend methods that will return a constant iterator that gives just read-only access to elements:

    vector<int> primes { 1,2,3,5,7,11,13 }; 
    const auto it = primes.begin(); // const has no effect 
    *it = 42; 
    auto cit = primes.cbegin(); 
    *cit = 1;                       // will not compile

Here const has no effect because the variable is auto and the type is deduced from the item used to initialize the variable. The cbegin method is defined to return a const iterator, so you cannot alter the item it refers to.

The begin and cbegin methods return forward iterators so that the ++ operator moves the iterator forward. Containers may also support reverse iterators, where rbegin is the last item in the container (that is, the item before the position returned by end) and rend is the position before the first item. (There are also crbegin and crend, which return const iterators.) It is important to realize that the ++ operator for a reverse iterator moves backwards, as in the following example:

    vector<int> primes { 1,2,3,5,7,11,13 }; 
    auto it = primes.rbegin(); 
    while (it != primes.rend()) 
    { 
        cout << *it++ << " "; 
    } 
    cout << endl; // prints 13,11,7,5,4,3,2,1

The ++ operator increments the iterator according to the type of the iterator that it is applied to. It is important to note that the != operator is used here to determine if the looping should end because the != operator will be defined on all iterators.

The iterator type here is ignored by using the auto keyword. In fact, all containers will have typedef for all the iterator types they use, so in the previous case we can use the following:

    vector<int> primes { 1,2,3,5,7,11,13 }; 
    vector<int>::iterator it = primes.begin();

Containers that allow forward iteration will have a typedef for iterator and const_iterator, and containers that allow reverse iteration will have a typedef for reverse_iterator and const_reverse_iterator.

To be complete, containers will also have typedef for pointer and const_pointer for the methods that return pointers to the elements, and reference and const_reference for methods that return references to elements. These type definitions enable you to write generic code where you do not know the types in a container, but the code will still be able to declare variables of the right type.

Although they look like they are pointers, iterators are often implemented by classes. These types may only allow iteration in one direction: a forward iterator will only have the ++ operator, a reverse iterator will have the - operator, or the type may allow iteration in both directions (bidirectional iterators) and so they implement both the ++ and -- operators. For example, the iterators on the list, set, multiset, map, and multimap classes are bidirectional. The vector, deque, array, and string class have iterators that allow random access, so these iterator types have the same behavior as bidirectional iterators, but also have pointers like arithmetic, so they can be changed by more than one item position at a time.