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

2022-01-07 00:00:00 deque iterator c++ stl

如果我错了,请纠正我.谢谢!

inserterase 将重新定位元素,但在插入/擦除发生位置之前的元素不会重新定位,因此它们的迭代器仍然有效.

push_backpop_back 不会使任何迭代器失效.

push_frontpop_front 使所有迭代器无效.

swap 不会重新定位元素,但我认为它应该使迭代器无效.

解决方案

push_back()push_front() 是根据 insert()<定义的/代码>.类似地,pop_back()pop_front() 是根据 erase() 定义的.

以下是 C++03 标准关于 insert() (23.2.1.3/1) 的迭代器失效的说明:

<块引用>

在双端队列中间插入会使所有迭代器和对双端队列元素的引用.两端插入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.

相关文章