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.
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.