std::list end iterator after insertion

user_5666503 0
Viewed 128

In std::list an insertion inside the container should not invalidate an iterator but how is that implemented? For example I have a list and insert one value:

std::list<int> list;
list.push_back(12);

Then I get the end iterator:

auto end = list.end();
auto it = --end;

Now end should point to the inserted element. What happens when I keep the end iterator and do another insertion? Will --end still point to 12 or to the new inserted value?

Edit1:

I tested this with the following program:

#include <iostream>
#include <string>
#include <list>

int main()
{
  std::list<int> list;
  list.push_back(12);
  auto end = list.end();
  auto it = std::prev(end);
  
  std::cout << *it << std::endl;
  list.push_back(13);
  it = std::prev(end);
  std::cout << *it << std::endl;
  it = std::prev(end);
  std::cout << *it << std::endl;
}

This gives me 12 13 13 as result which I don't understand because I did not edit the end iterator after the second insertion. This means the container has access to the iterator internals inside push_back?

stl c++
2 Answers

The end iterator is not invalidated by push_back*, which means it would keep point to the end. (in this case you can think it as a iterator to a sentinel node that's always the end)

std::list<int> list;
list.push_back(12);
auto end = list.end();

// one before the end
auto it = std::prev(end);
std::cout << *it << std::endl;
list.push_back(13);

// one before the end (now with 2 element)
it = std::prev(end);
std::cout << *it << std::endl;

// std::prev doesn't change `end` so it's the same as above
it = std::prev(end);
std::cout << *it << std::endl;

*on the other hand std::vector does have some operation that invalidate end iterator

user_59804300

What happens when I keep the end iterator and do another insertion?

--end modifies the iterator, so it points to the 12 before and after the insertion of the second element.

If you had kept the end iterator without modifying it, it would still be the iterator to one past the last element before and after the second insertion.

Will --end still point to 12 or to the new inserted value?

--end second time would be UB because after the first decrement it points to the first element.

But if you had not modified the end iterator, then the first --end would produce an iterator to the last element.

Example:

std::list<int> list;
list.push_back(12);
auto end1 = list.end();
auto end2 = list.end();
auto it1 = --end1;    // refers to to 12
list.push_back(13);
auto it2 = end1;      // refers to to 12
// auto it3 = --end1; // UB
auto it4 = --end2;    // refers to 13
user_20793030
Related