How are iterators and pointers related?

Question

Code with iterators looks very similar to code with pointers. Iterators are of some obscure type (for example, std::vector<int>::iterator ).

What I am not getting is how iterators and pointers are related to each other - is it an iterator of a wrapper around a pointer with overloaded operations to jump to neighboring elements or is it something else?

Answer 1

Iterators are a generalization of pointers.

Iterator (depending on options) needs to implement * and ++

Thus, the IS pointer is an iterator. But not necessarily the opposite.

If you want to iterate over a complex structure (tree, chart ...), then the iterator will be much larger than the pointer, and will not refer to any actual place in ram.

Answer 2

Conceptually, yes, but they do not have to be pointers. Their internals and capabilities will depend on the structure of the data they “wrap”.

This is why there are different "classes" of iterators . For example. Unidirectional, Bidirectional, RandomAccess, etc.

Some of them may have several classes.

eg. if the internal structure is a Red-Black or Linked List tree, iterators can be bidirectional, but not RandomAccess. If they wrap a vector (implemented as an array), you will get RandomAccess and bidirectional.

Answer 3

Iterators are objects that overload certain operators, so usage will look like pointers. This is within the scope of this category of iterators. Random access iterators look completely like pointers, other types of iterators do not provide some operations (for example, list<X>::iterator , which is bidirectional, does not have the += operator among many others, which require random access).

As for the "obscure names", it is not practical to use a simple pointer for an iterator:

  template <class T> class MyContainer { ... typedef T* iterator; } MyContainer<int>::iterator it; //the type is really int* 

Answer 4

An iterator is just a concept that provides the interface needed for iterators - they are different for different types of iterators and are specified in section 24.1 of the C ++ standard (Iterator requirements).

How iterators are implemented depends on what they iterate over - for vectors they are usually a wrapper around one pointer to an array (in any case, in the release), for more complex containers they have a more complicated implementation. For open-loop ranges, they will contain the state of any algorithm used to generate elements.

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