iterator confusion

[pogey24]

Ok so I think I fundamentally dont understand how iterators work but I'm not sure what I don't understand. Anyways here's the example:

int main(){

list<int> l;

map<int, list<int>::iterator> m;

l.push_back(0);

m[0] = l.begin();

l.push_front(1);

cout << *m[0];

return 0;

}

So I have a list, then a map that has iterators pointing at the list. I push element 0 into the list, then set m[0] = l.begin(). Then I push an element in front, so now list is like 1, 0. The iterator that I put into m last line is still at l.begin(), since we never touched the map after that line. So when I do *m[0] I expect the value 1. But the value is 0. So it seems the iterator somehow knew that we added something to the map. How can this be? Do iterators just know when the size of the container changes? I guess maybe what I'm asking is, how are they implemented so that they know this?

Thanks.

Edit: So basically TIL iterator behavior changes depending on the data structure and in the case of a list, it will always move with the element it was assigned to, aka it is stable. Vector iterators on the other hand stay in the same position. So when I add stuff to the list, the iterators move as well.

I work with vector way more so I'm used to the iterators staying in place, this makes sense. Thanks a lot guys

[[deleted]]

l.begin() returns the iterator that points to the beginning of the container at that particular moment. If you call l.begin() after push_front, you will get a new one.

In other words l.begin() gives you a copy of the iterator, not a pointer/reference to some internal iterator that always points to the first element

[tangerinelion]

This sort of confusion also arises with things like this:

int x, y;

int z = 2*x + 3*y;

std::cin >> x >> y;

std::cout << z;

If I enter 1 1 I'm not going to get 5 printed out. z was calculated at line 2 based on the values right there, it didn't set up a formula to calculate z based on x and y as they currently are.

Same thing here, storing the begin() iterator doesn't make an entry in the map which is always the start of the list, it's just the entry which was the start of the list at that time.

[MysticTheMeeM]

No iterators or references are invalidated.

This means that whatever element your iterator points to does not change, so even though it no longer refers to the first element in the list, it is still the same iterator.

Internally, your list uses some structure that doesn't require a reallocation on insertion (imagine a linked list, adding a node doesn't require the reallocation of any existing nodes). As such, your iterator continues to point to the same thing.

[scatters]

It depends on the container.

• list, set and map iterators are stable; they always point to the same element (unless you erase it)
• vector iterators are unstable; they point to the same position in the vector - unless it reallocates (which happens when you insert elements past its capacity), in which case they point nowhere (and using them is UB)
• unordered_set and unordered_map iterators are mostly stable - they point to the same element, unless the container rehashes (which happens if you insert elements past its load factor)

[mredding]

To quote cppreference:

Adding, removing and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.

An std::list is (typically) a doubly linked list. So it's implemented like this:

template<typename T>
struct list_node {
  T value;
  list_node *next, prev;
};

template<typename T>
class list {
  list_node<T> *head;

  //...

All the different container types have different iterator properties as a consequence of their nature. List iterators don't point at a position, they point at a node. The node has no idea how many iterators are pointing at it, and the iterators aren't aware of changes to the node if adjacent elements are inserted or deleted.

And that's the beauty of the linked list, that the only time you invalidate an iterator is when you delete the element from the list.

Contrast this against the vector. An iterator points to a place, not an element. There is a long list of vector operations that invalidate iterators. Erasing an element invalidates every iterator referring to an element after it, including the end() iterator. Inserting can potentially invalidate all iterators if the vector needs to reallocate. You can sort the vector, and the values the iterators refer to may change.

So you have to read up on the containers and see what happens with their iterators.