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

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 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

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 4

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.