can someone explain what they mean is list.pushback documentation (does not invalidate iterators)

Question

In list.pushback the documentation say that

Due to the nature of a %list this operation can be done in constant time, and does not invalidate iterators and references.

How add cannot change the iterator? what they mean by not invalidate references?

Thank you

I think they mean that as you add an element at the end of the list with pushback, if you had an iterator which points to the 5th element, it still points to the 5th element. In the same way, if you had a reference to this 5th element, this reference will still be valid after the pushback, because pushback do not alter the list, it just add an element at the end. — Flinth, Jul 31 '12 at 07:37

fredoverflow · Accepted Answer · 2012-07-31T07:42:27.010

3

It means that all iterators and references obtained prior to the call to push_back can still be used after:

std::list<int> numbers { 2, 3, 5, 7};
auto it = numbers.begin();
int& r  = numbers.front();
numbers.push_back(11);
std::cout << *it << '\n';   // guaranteed to print 2
std::cout <<   r << '\n';   // guaranteed to print 2

Other data structures do not necessarily offers such guarantees. If you use a vector instead of a list, each call to push_back might invalidate all the iterators and references obtained prior to the call, because the capacity might be exhausted, and in that case, the data has to be moved into a bigger array. Using an invalid iterator or reference results in undefined behavior (read: anything can happen).

edited Jul 31 '12 at 07:42

answered Jul 31 '12 at 07:35

fredoverflow

256,549
94
388
662

lets say that you iterate over a list in theradA and you are in the last element. simultaneously in threadB you add element . dosnt the iterate next in the thread A can be in the middle of setting the pointer and create new instance to the new last element? – Avihai Marchiano Jul 31 '12 at 07:43
If some thread A iterator points to the 7 and thread B adds the 11, then thread A iterator still points to the 7 and not to same random garbage in memory. That's all there is to it. – fredoverflow Jul 31 '12 at 07:46
Of course, if you throw multi-threading into the mix and do not correctly synchronize access to shared lists, you are going to run into concurrency problems. But that has nothing to do with iterator invalidation. – fredoverflow Jul 31 '12 at 07:48
Data races are orthogonal to iterator invalidation. – R. Martinho Fernandes Jul 31 '12 at 17:23

score 1 · Answer 2 · answered Jul 31 '12 at 07:37

As an example compare with the behaviour std::vector. With that if you do:

std::vector<int> foo(1);
std::vector<int>::iterator it = foo.begin();

foo.push_back(2);

*it = 0;

It's illegal - the act of calling push_back could have caused the vector to grow. This growth would have caused new memory to be allocated and the contents to be moved into that, before releasing the older, smaller memory.

With std::list that doesn't apply. It's a linked list so the other elements in the list aren't changed when you add a new element. Growth is purely a local thing.

score 0 · Answer 3 · answered Jul 31 '12 at 07:35

0

appending element to the list does not change other elements and so iterators and references to these elements remain valid

answered Jul 31 '12 at 07:35

Andrew

24,218
13
61
90

can someone explain what they mean is list.pushback documentation (does not invalidate iterators)

3 Answers3