How are iterators and pointers related?

Question

Code with iterators looks pretty much like code with pointers. Iterators are of some obscure type (like std::vector<int>::iterator for example).

What I don't get is how iterators and pointer are related to each other - is an iterator a wrapper around a pointer with overloaded operations to advance to adjacent elements or is it something else?

Answer 1

Iterators are a generalization of pointers.

An iterator (depending on the variants) have to implement * and ++

So a pointer IS an iterator. But not necessarily the other way round.

If you want to iterate over a complex structure (a tree, a graph...), the iterator will be much more than a pointer, and doesn't make any reference to some actual place in the ram.

Answer 2

Iterators are objects that overload certain operators, so the usage would look like they were pointers. That's within the capabilities of a given iterator category. Random access iterators look entirely like pointers, other types of iterators don't provide some operations (e.g list<X>::iterator which is bidirectional doesn't have operator += among many others that would require random access).

As to the "obscure names", it is not completely unthinkable to use a plain pointer for an iterator:

 template <class T>
 class MyContainer
 {
     ...
     typedef T* iterator;
 }

 MyContainer<int>::iterator it; //the type is really int*

Answer 3

Conceptually, yes -- but they need not be pointers. Their internals and capabilities will depend on the data structure they "wrap".

That is why there are different "classes" of iterators. E.g. Unidirectional, Bidirectional, RandomAccess, etc.

Some are capable of multiple classes.

E.g. if the internal structure is a Red-Black tree or Linked List, the iterators might be Bidirectional, but not RandomAccess. If they wrap a vector (implemented as an array), you'll have RandomAccess and Bidirectional.

Answer 4

An iterator is just a type that provides the interface required for iterators - these are different for the different types of iterators and are specified in section 24.1 of the C++ standard (Iterator Requirements).

How iterators are implemented is dependent on what they iterate over - for vectors they are commonly a wrapper around a single pointer to an array (in release builds anyway), for more complex containers they have a more complicated implementation. For open ended ranges they will contain the state of whatever algorithm is beimng used to generate the elements.

Note that a pointer to an element in an array meets the requirements of a random access iterator, so to some extent they are interchangeable.

Answer 5

As it was said: iterators are a generalization of pointers. Every pointer is an iterator but not every iterator is a pointer (although most of non-pointer iterators contain pointers within).

Iterator is kind of interface (or concept). We could define the minimum iterator interface as follows:

template <typename T>
class iterator
{
    // Advance to the next element of the collection.
    virtual void operator++() = 0;

    // Get access to the element associated with the iterator.
    virtual const T &operator*() = 0;
};

But there is no real abstract base class for iterators. All functions that take iterators as parameters are template functions, and types for iterator parameters are defined using templates. This is called static polymorphism. We can use std::vector constructor as an example:

template< class InputIt >
vector::vector( InputIt first, InputIt last );

Since InputIt is a type defined using template and since all pointers support operator++() and operator*(), all pointers can be used as iterators. For example:

int arr[3] = {1, 2, 3};
int *begin = &arr[0];
int *end   = &arr[3];

// Initialize vector from a pair of iterators.
std::vector<int> v(begin, end); // The vector `v` will copy to itself
                               // all elements of `arr` in the range from
                              // arr[0] (including) to arr[3] (excluding).

or

std::string str = "hello";
std::string *begin = &str;
std::string *end   = begin + 1;

// Initialize vector from a pair of iterators.
std::vector<std::string> v(begin, end); // The vector `v` will contain
                                       // a single element which is
                                      // string "hello".

Since iterator is just an abstract interface, pointers are not the only example of iterators. Any class that overrides operator++() and operator*() can be used as an iterator. And usually containers use custom classes as iterators instead of pointers. But some functions still use pointers as iterators. An example is std::begin and std::end functions for static arrays:

template< class T, std::size_t N >
T* begin( T (&array)[N] );

template< class T, std::size_t N >
T* end( T (&array)[N] );

There are different types of iterators. The most advanced type of iterator is Random Access Iterator. Besides operator++() and operator*() it supports many other operations like advancing backward (operator--()) or advancing many elements forward at single step (operator+=(size_t n)). Pointers are Random Access Iterators.

This is how pointers and iterators are related.

Resume. Iterators are class of objects that allows to iterate through some collection of elements. Pointers are just an example of iterators but there are others.