Is an iterator in C++ a pointer?

Question

Is an iterator in C++ a pointer? The reason I ask is that it seems like nobody completely understands what an iterator is. It's just a "thing" or a "value" they say. But an iterator simply points to the element, to its position. When we dereference it, it's like looking at what an iterator points to.

Is it a correct analogy?

Answer 1

The short answer is:

• Pointer is a kind of iterator.
• Pointer can be therefore used as an iterator.
• Pointer has properties other than iterator.

History

Historically, we have C pointer, and it is adapted into C++ when C++ is invented. Pointer represents a location in memory, therefore can be used as a location in an array.

Later, in 1990s, an idea called "iterator concept" is introduced to C++. The "iterator concept" is related to a library called STL (which is later absorbed into the Standard Library) and a paradigm called "generic programming". The iterator concept is inspired from C pointer to represent a location in containers like vector, deque and others, just like how C pointer represent location in array. The iterator concept is carefully engineered to be compatible with C pointer, hence we can nowadays say C pointer models iterator concept.

Iterator concept

A simplified way to understand iterator concept is that, if a data type suppports a list of operations and behaviours, such that it represent a location in a container, and enable some kind of access to the element, it can be called an iterator.

With carefull design of iterator concept, C pointer fulfill that list. Pointer is therefore a kind of iterator.

Iterator concept being just a set of requirement on types, means that you can create your own iterator through C++ power of data abstraction.

Other properties of pointer

Pointer exhibits other properties, and they are not related to iterator concept.

A significant use of pointer is to express reference semantics, i.e. to refer to an object in a remote memory location. This usage of pointer is later considered unsafe, and causes the invention of "smart pointer". By comparing smart pointers and iterators, we can find that they are totally unrelated concepts.

Another use of pointer is to refer to a raw memory location. This is completely unsafe for application programming, but is a essential tool for microcontroller programming to manipulate hardware.

Answer 2

No. An iterator is not "just a pointer".

In some cases, an iterator can be a pointer - but it can be more. An iterator is a generalization of what a pointer does.

When you increment a pointer, it advances to the next location in memory (modulo the size of the objects you are processing). When you increment an iterator, it advances to "the next element in the sequence". If you are working with a linked list, it advances to the next element in the list. If you are working with a map or set, to the next element in the map/set, and so on.

Answer 3

Iterator is more general than pointer. In the case that it's not a pointer, it's just a normal class that has custom operator++(), operator++(int), operator--(), operator--(int), operator->(), operator*(), etc. You can implement any behaviors you'd like in these operators. nothing magical here.

Answer 4

An iterator is just an object that can be used to iterate the elements in a container. There are different categories of iterators. The difference is what operations they support e.g. with a Forward iterator you you can use ++ to go from one element to the next and with a Random access iterator you can go from one element to another element in one step.

http://www.cplusplus.com/reference/iterator/

Iterators are usually structures that house a pointer which are given a common interface that containers can use to transverse their elements. Though, this isn't always the case. In some implementations of standard containers, std::vector::iterator, for example, iterator is merely defined as typedef T* iterator

In effect, the difference between a pointer and an iterator really depends on the implementation of the iterator.

Answer 5

In C, you can iterate through an array by using a simple for loop with a pointer variable, like this:

int arr[MAX];

for (int* p = arr; p < arr + MAX; ++p)
{
    do_something_with(*p);
}

This works because an array is stored contiguously in memory. But for other kinds of data structures — linked lists, trees, hash tables, etc. — the code to move to the next element of the container is more complicated than a simple ++.

A C++ iterator is like a pointer, but it generalizes to all types of containers.

std::set<int> s;

for (std::set<int>::const_iterator it = s.begin(); it != s.end(); ++it)
{
    do_something_with(*it);
}

Where std::set<T>::const_iterator is a class that has overloaded ++ and * operators so that it looks like a pointer to an array element. Behind the scenes, the ++ operator follows the link(s) within the set's internal tree structure to move to the next element.

The std::vector and std::string classes have iterators too, but because these classes are wrappers around classic arrays, these might well just be typedefs of the corresponding pointer types.

Iterators can also be used for things other than the iteration variable in a loop. For example, containers often have a find method that returns an iterator to the object it finds.