C++ deque: when iterators are invalidated

2019-01-17 01:06发布

问题:

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.

回答1:

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.