C++ deque:当迭代器失效时

在双端队列中间插入会使所有迭代器和对双端队列元素的引用.两端插入deque 使 deque 的所有迭代器无效，但对 deque 没有影响对双端队列元素引用的有效性.

所以 push_front() 和 push_back() 会使迭代器无效，但对元素本身的引用仍然有效.

对于任一端的 erase() (23.2.1.3/4):

在双端队列中间的擦除会使所有迭代器和对双端队列元素的引用.两端的擦除deque 仅使迭代器和对被擦除的引用无效元素.

所以 pop_front() 和 pop_back() 只会使迭代器/引用到相关元素的末尾无效.

据说这是关于任何标准容器的swap()(23.1/10容器要求"):

没有 swap() 函数使任何引用、指针或迭代器失效指被交换的容器的元素.

C++11 添加了以下关于 deque 上的 end() 迭代器对这些操作的行为的说明.基本上，end() 的迭代器应该在 swap() 之后或擦除 deque 中的最后一个元素之后被视为无效:

擦除双端队列最后一个元素的擦除操作只会使尾后迭代器和所有迭代器以及对被擦除元素的引用无效.

<块引用>

在交换之前引用一个容器中的元素的每个迭代器都将在交换之后引用另一个容器中的相同元素.未指定交换前值为 a.end() 的迭代器在交换后是否具有值 b.end().

我认为即使您还没有使用 C++11 编译器，也可以像这些规则一样进行编码.

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.