CODEWITHSUNDEEP
c++listiterator
Engineer999
Engineer999

Reputation: 3955

How Iterators find the next address in a linked list

I'm coming from a C background.

When iterating through a container such as a vector or deque which contains elements in contiguous memory, it's easy to understand that by incrementing the iterator to point to the next element in the vector, such as in the loop below, it may just increase the address of the iterator by the size of the element in the vector, in this case int.

vector<int> vec;
vector<int>::iterator it;

for (it = vec.begin; it != vec.end(); it++)
{
    // do something on each element

}

The benefits i believe of using iterators is that we can decouple the algorithm code from the actual container type, so if we decide later to use a list instead of a vector, we can use the same iteration code as above on the list.

It is possible to iterate through a list in the exact same way, but a list will have elements not in contiguous memory locations, so how does the iterator increment and find the correct address of the next element?

My understanding from implementing linked lists in C is that we would check the pointer in the node, possibly called "next" which points to the next node in the list.

Is this exactly what's happening here in C++ behind the scenes when using list iterators? Therefore , when an iterator is pointing to a list element, in order to point to the next element, the compiler will generate completely different code to that of pointing to the next element in a vector? Thanks in advance.

Upvotes: 2

Views: 455

Answers (1)

Davis Herring
Davis Herring

Reputation: 39838

You have the correct idea. The critical point is here:

when an iterator is pointing to a list element

A better phrasing would be “for a kind of iterator used with a linked list”: no one iterator can indicate an element of a vector or a list.

Because each container type has its own iterator type, and the type in use is always known to the compiler, the correct code can be generated (and optimized!) in all cases. (Generic code can be written with no explicit types, but the types must be specified (or in some cases inferred by the compiler) for each use.)

Note that not all iterator types are implemented using (only) a pointer: for example, a deque<T>::iterator typically bundles a pointer to a short array and an index into that array. The template system also supports this size and composition variation between data types with corresponding operations.

Upvotes: 1

Related Questions