Menu
Please correct me if I am wrong. Thank you!
insert and erase will relocate elements, but elements before the position where insertion/erasure takes place don't relocate and hence their iterators remain valid.
push_back and pop_back don't invalidate any iterators.
push_front and pop_front invalidate all iterators.
swap won't relocate elements, but somehow I think it should invalidate iterators.
293
Iterator Invalidation in C++ When the container to which an Iterator points changes shape internally, i.e. when elements are moved from one position to another, and the initial iterator still points to the old invalid location, then it is called Iterator invalidation. One should be careful while using iterators in C++.
To avoid invalidation of references to elements you can use a std::deque if you do not insert or erase in the middle. To avoid invalidation of iterators you can use a std::list.
No; all of the iterators at or after the iterator(s) passed to erase are invalidated. However, erase returns a new iterator that points to the element immediately after the element(s) that were erased (or to the end if there is no such element). You can use this iterator to resume iteration.
For reference, std::vector::swap does not invalidate iterators.
push_back() and push_front() are defined in terms of insert(). Similarly, pop_back() and pop_front() are defined in terms of erase().
Here's what the C++03 standard says about iterator invalidation for insert() (23.2.1.3/1):
An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.
So push_front() and push_back() will invalidate iterators, but references to the elements themselves remain valid.
For erase() at either end (23.2.1.3/4):
An erase in the middle of the deque invalidates all the iterators and references to elements of the deque. An erase at either end of the deque invalidates only the iterators and the references to the erased elements.
So pop_front() and pop_back() only invalidate iterators/references to the element at the end in question.
And this is said says this about swap() for any standard container (23.1/10 "Container requirements"):
no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.
C++11 adds the following clarifications regarding how the end() iterator on a deque behaves for these operations. Basically, an iterator to end() should be treated as invalid after a swap() or after erasing the last element in the deque:
An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements.
Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap. It is unspecified whether an iterator with value a.end() before the swap will have value b.end() after the swap.
I think it would be a good idea to code as if these rules apply even if you're not yet using a C++11 compiler.
149
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
