元素的迭代器, 指针和引用 + 首前/尾后迭代器

对list与forward_list的迭代器, 引用和指针无影响

对于连续存储的容器, 此处特指vector(string):

• 如果需要移动元素, 被移动元素的迭代器, 引用和指针失效, 首前迭代器不受影响, 尾后迭代器失效
  
• 如果需要扩容, 所有迭代器, 引用和指针均失效
  

让人困惑的deque

一个理想的情况

一块内存中的元素向右增长, 一块内存中的元素向左增长, 中间有若干元素已满的块

IMHO, deque is collection of blocks with first block growing in one direction and the last block in opposite direction.

in my humble opinion

此时在首尾添加元素不会使得已有元素的迭代器, 引用和指针失效, 可能会影响首前/尾后迭代器

《C++标准库》持此观点

作者: Nicolai M. Josuttis 英文名: The C++ Standard Library - A Tutorial and Reference

未考证

Any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.

C++11标准

1. 添加元素
   
   • 首尾添加元素会导致所有迭代器失效, 但元素的引用不受影响
     
   • 其他位置添加元素会导致所有元素的迭代器和引用失效
     
2. 删除元素
   
   • 删除尾元素: 被删除元素的迭代器和引用失效, 尾后迭代器失效
     
   • 删除首元素: 被删除元素的迭代器和引用失效
     
   • 其他位置元素: 所有元素的迭代器和引用均失效, 包括尾后迭代器
     

未考证

C++11

• Insertion: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.3.3.4/1]
  

• Erasure: erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) [23.3.3.4/4]
  

• Resizing: as per insert/erase [23.3.3.4/1]
  

《C++ Primer(第五版)》持此观点

同时, P316也提到:

…或在deque中首元素之外任何位置添加/删除元素后，原来end返回的迭代器总是会失效。

隐含添加首元素后, 尾后迭代器不会失效的意思

验证deque添加首元素, 尾后迭代器情况

尾后迭代器仍有效

Copy 1#include <iostream>
 2#include <deque>
 3
 4using namespace std;
 5
 6int main()
 7{
 8    deque<int> id = {1, 2, 3};
 9
10    auto end = id.end();
11
12    id.push_front(0);
13
14    auto end2 = id.end();
15
16    if (end == end2)
17    {
18        cout << "equal" << endl;
19    }
20    else
21    {
22        cout << "not equal" << endl;
23    }
24    return 0;
25}

Copy1g++ -std=c++11 test.cpp

采用的观点

1. 理想的情况可作为对deque的理解
   
2. 迭代器是否有效需要与具体实现挂钩
   
   万一添加首元素导致扩容, 确实影响到了尾后迭代器呢?
   
3. 跟随《C++ Primer(第五版)》观点
   

参考

-
StackOverflow: deque迭代器无效的困惑
StackOverflow: C++容器迭代器失效规则
deque迭代器失效的困惑
StackOverflow: STL和C++标准库的区别

添加元素时

vector(string)

受两个因素影响:

1. 未扩容时, 位置与插入位置的前后关系
   
   位置于插入位置之前, 相关迭代器, 引用和指针不受影响
   

   位置于插入位置之后, 相关迭代器, 引用和指针失效
   

2. 发生扩容, 为容器重新分配了内存空间
   
   所有迭代器, 引用和指针均失效
   

deque

迭代器一定会失效

首尾位置添加元素, 已有元素的引用和指针不受影响

其他位置添加元素, 所有元素的引用和指针失效

删除元素时

被删元素的迭代器, 引用和指针失效

讨论其他位置的迭代器, 引用和指针

vector(string)

位置于删除位置之前, 相关迭代器, 引用和指针不受影响

位置于删除位置之后, 相关迭代器, 引用和指针失效

尾后迭代器一定失效

deque

1. 删除首元素
   
   其他元素的迭代器, 引用和指针不受影响
   

   首前迭代器失效
   

2. 删除尾元素
   
   其他元素的迭代器, 引用和指针不受影响
   

   尾后迭代器失效
   

3. 删除其他位置的元素
   
   所有元素的迭代器, 引用和指针均失效
   

验证deque删除首元素, 其首前/尾后迭代器情况

首前迭代器失效, 尾后迭代器不受影响

Copy 1#include <iostream>
 2#include <deque>
 3
 4using namespace std;
 5
 6int main()
 7{
 8    deque<int> id = {0, 1, 2, 3};
 9
10    auto begin = id.rend();
11    auto end = id.end();
12
13    id.pop_front();
14
15    auto begin2 = id.rend();
16    auto end2 = id.end();
17
18    cout << "begin before: ";
19    if (begin == begin2)
20    {
21        cout << "equal" << endl;
22    }
23    else
24    {
25        cout << "not equal" << endl;
26    }
27
28    cout << "end after: ";
29    if (end == end2)
30    {
31        cout << "equal" << endl;
32    }
33    else
34    {
35        cout << "not equal" << endl;
36    }
37    return 0;
38}

建议

1. 对于要求迭代器有效的程序片段, 尽可能将其最小化
   

2. 每次执行改变容器的操作之后, 重新定位迭代器
   
   尤其是vector(string)和deque
   

   除余不尽复制元素, 除余为0则删除
   

   Copy 1vector<int> vi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    2auto iter = vi.begin();
    3
    4while (iter != vi.end())
    5{
    6    if (*iter % 2)
    7    {
    8        iter = vi.insert(iter, *iter);
    9        iter += 2;
   10    }
   11    else
   12        iter = vi.erase(iter);
   13}
   14
   15// vi = {1, 1, 3, 3, 5, 5, 7, 7, 9, 9};
   

3. 不要保存end操作返回的尾后迭代器, 每次重新获取尾后迭代器
   

   • 尾后迭代器失效的情况
     
     vector(string)增删元素一定会使尾后迭代器失效
     

     deque添加元素会使得所有迭代器失效, deque删除非首元素会使得尾后迭代器失效
     
     实际情况中, 添加首元素时, 尾后迭代器不一定会失效. 当前跟随《C++ Primer(第五版)》观点
     

     Copy1auto begin = v.begin(), end = v.end();
     2
     3while (begin != end)
     4{
     5    ++begin;
     6    begin = v.insert(begin, 42);        // 尾后迭代器失效
     7    ++begin;
     8}

   • 在判断是否遍历到末尾时，每回都调用end()更新尾后迭代器
     

     Copy1while (begin != end())
     2{
     3    ++begin;
     4    begin = v.insert(begin, 42);
     5    ++begin;
     6}