Iterators

Rationale

a desirable object for containers is a ``bookmark-like'' object for the list to act as a place-holder. For those who've seen pointers, we refer here to an abstraction of pointer behaviour. C++ has such place holders. The place holders are referred to as iterators.

Iterators offer two key advantages over indices:

Simple numerical indices make sense for vectors and arrays because of the way the data is arranged. In particular, the indices correspond to the address offsets of the elements. But they don't make sense for lists or maps. The problem is that Numerical indices are invalidated by (for example) inserting data into the front of a container. Since the address of elements in a list or map is invariant under insertion, one would hope that placeholders for these containers have the same property. Moreover, for containers such as lists and maps, computing these indices would be slower than locating elements.
The iterator interface makes sense for all container types. Therefore, iterators offer a way to create a consistant interface for all container types.
Because of this consistency, one can write functions that are general in the sense that they work not only for a single container that contains an arbitrary type - one can code algorithms that can operate on arbitrary containers (for example, lists, vectors, etc). The algorithms are written so that they depend on certain properties of the given iterators (an increment operator, and optionaly decrement and difference and sum operators)

Basic Properties And Operations

There are four basic properties of iterators we need to understand before we can use them:

Namespaces

Iterators are defined in the same namespace as the container that uses them. For example:

// constant iterator over a vector of double
std::vector<double>::const_iterator it1; 
// constant iterator over a vector of double
std::list<int>::iterator it2;

Locating the beginning and end of a container

The method begin() returns an iterator that references the first element on the list. The method end() returns an iterator one past the end of the list (so that we can use myIterator != container.end() as a check in loops.) We'll see an example of this shortly.

Retrieving Elements

One can retrieve the element of the container referenced by an iterator by applying the * operator. For example:

iterator0.cc


#include <vector>
int main()
{
    std::vector<int> v;
    v.push_back(1);
    std::vector<int>::iterator it1 = v.begin();
    int a = *it1;	// a is the first element of v
    *it1 = ++a;	// OK since *it is non-const hence an lvalue
    std::vector<int>::const_iterator it2 = v.begin();
    a = *it2;	// *it2 is an rvalue only, since it is const
    return 0;
}

Auto-Increment

To advance to the next position in the list, we apply the increment operator ++ to an iterator. To go backwards, we apply the decrement operator. For example,

iterator1.cc


#include <iostream>
#include <vector>

using std::vector;
using std::cout;
using std::endl;

int main()
{
    vector<double> v;
    v.push_back(3);
    v.push_back(2.3);

    vector<double>::iterator it;

    it = v.begin();            // it refers to the first element of v
    cout << *it << endl;     // 3
    *it = 2.4;                // OK since *it is non-const, hence an l-value
    cout << *it << endl;    // 2.4
    it++;
    cout << *it << endl;    // 2.3
    return 0;
}

There are several things one can do with iterators:

The loop idiom: to iterate over the elements of a container, one uses the following idiom:

using std::vector;
for ( vector<double>::iterator it = v.begin(); it != v.end(); ++it )
	*it = rand(); // for example.

random_shuffle: iterators for random access containers (for example, vector iterators and array pointers) admit the random_shuffle operation. To randomly shuffle a vector, one uses:
```
random_shuffle(v.begin(), v.end());
```
find: The syntax for find is find(start,finish,key) where start and finish are iterators, and key is the term being searched for. The return value is an iterator.
copy ( iterator source_start, iterator source_end, iterator dest_start ); copies the elements in the range [source_start, source_end) to elements beginning from dest_start. (note: the notation [start, end ) refers to the elements between start and end, excluding end)
erase(iterator): The erase method is a member function (of the list, vector, and map classes, for example) it removes the element referred to by the iterator from the container.