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?

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

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

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

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

View more solutions

Comments

[Björn Pollex]

I think the word is concept rather than type here.

[dekuShrub]

Isn't there a contradiction in this answer? If an iterator is more than a pointer, then surely a pointer cannot be an iterator?

[Milan]

Could you please elaborate on what did you mean by "... and doesn't make any reference to some actual place in the ram"? Thank you so much in advance!

[Tristram Gräbener]

For instance, an iterator on the nodes of the graph can be depth or breadth first. So that iterator needs to know where it stands in the graph to retrieve the node. So the iterator is a structure, with attributes and everything. It is more than a memory adress

[Thomas Weller]

The term RAM IMHO refers to physical memory. A pointer might point to memory that has been swapped to disk.

[Caleth]

@dekuShrub "an iterator" is a shorthand for "an instance of a type that models the iterator concept". All pointer-to-object types model the iterator concept, but there are also some class types that model that concept, e.g. std::map<K, V>::iterator

[anton_rh]

@dekuShrub, If an iterator is more than a pointer, then surely a pointer cannot be an iterator. An iterator is not (necessarily) more than a pointer, it can be more than a pointer. The original phrase was if you want to ..., [then] the iterator will be much more than a pointer. So it is more than pointer in some specific cases. There are different iterators. Some of them (for example, iterators of std::vector) are almost pointers, Some of them (for example, iterators of std::map) are more complex. A pointer is just the simplest example of iterator.