CODEWITHSUNDEEP
c++
michalt38
michalt38

Reputation: 1193

Iterator to one past the last element in list

I'm working on implementing my own list. I see that std::list::end() returns iterator to one past the last element in the list container. I'm wondering how the position of this past-the-end element is estimated due to list elements are stored in non-contiguous memory locations.

std::list<int> ls;
ls.push_back(1);
ls.push_back(2);
std::list<int>::iterator it = ls.end();
std::cout << &(*it) << std::endl << &(*++it) << std::endl << &(*++it) << std::endl;

As the code above presents, I can even increment the iterator to point to the next elements. How can it be known at which positions (in memory) the next elements will be stored?

Upvotes: 0

Views: 997

Answers (1)

JaMiT
JaMiT

Reputation: 16853

How can it be known at which positions (in memory) the next elements will be stored?

It is not. Also, using that memory address as (part of) the past-the-end iterator would be incorrect.

Is not:
An iterator is not (necessarily) a pointer. An iterator is not required to store a memory address. What is required is that the de-reference operator be able to calculate a memory address (returned in the form of a reference). Good news, everyone! Applying the de-reference operator to the past-the-end iterator is undefined behavior. So even this reduced requirement is not applicable to the past-the-end iterator. If you are storing an address, go ahead and store whatever you want. (Just be consistent since two past-the-end iterators must compare equal.)

If your iterator does store a pointer (which admittedly is probably common), a simple approach would be to store whatever you would put in the next field of the last node in the list. This is typically either nullptr or a pointer to the list's sentinel node.

Would be incorrect:
A std::list does not invalidate iterators when elements are added to the list. This includes the past-the-end iterator. (See cppreference.com.) If your past-the-end iterator pointed to where the next element would be stored, it would be invalidated by adding that element to the list. Thus, you would fail to meet the iterator invalidation requirements for a std::list. So not only is storing that address in the past-the-end iterator impossible, it's not allowed.

Upvotes: 3

Related Questions