迭代器失效规则
什么是C ++容器的迭代器失效规则？
最好以摘要列表格式。
（注意：这是一个Stack Overflow的C ++常见问题解答的入口，如果你想批评在这个表单中提供FAQ的想法，那么在这个开始所有这些的meta上的贴子将是这个地方的答案。那个问题在C ++聊天室中进行监控，常见问题解决scheme首先出现，所以你的答案很可能会被那些提出这个想法的人阅读）。
C ++ 03 （来源： 迭代器失效规则（C ++ 03） ）
插入
序列容器
-
vector：插入点之前的所有迭代器和引用不受影响，除非新的容器大小大于先前的容量（在这种情况下，所有的迭代器和引用都是无效的）[23.2.4.3/1] -
deque：所有迭代器和引用都是无效的，除非插入的成员在deque的结尾（前面或后面）（在这种情况下，所有迭代器都是无效的，但对元素的引用不受影响）[23.2.1.3/1] -
list：所有迭代器和引用不受影响[23.2.2.3/1]
关联容器
-
[multi]{set,map}：所有迭代器和引用不受影响[23.1.2 / 8]
容器适配器
-
stack：从底层容器inheritance -
queue：从底层容器inheritance -
priority_queue：从底层容器inheritance
擦除
序列容器
-
vector：擦除点之后的每个迭代器和引用无效[23.2.4.3/3] -
deque：所有的迭代器和引用都是无效的，除非被清除的成员在deque的末端（前面或后面）（在这种情况下，只有迭代器和对被擦除成员的引用是无效的）[23.2.1.3/4] -
list：只有迭代器和对被擦除元素的引用无效[23.2.2.3/3]
关联容器
-
[multi]{set,map}：只有迭代器和对擦除元素的引用无效[23.1.2 / 8]
容器适配器
-
stack：从底层容器inheritance -
queue：从底层容器inheritance -
priority_queue：从底层容器inheritance
调整
-
vector：按照插入/擦除[23.2.4.2/6] -
deque：按照插入/擦除[23.2.1.2/1] -
list：根据插入/擦除[23.2.2.2/1]
注1
除非另有规定 （明确地或通过用其他函数定义函数），调用容器成员函数或将容器作为parameter passing给库函数不应使迭代器失效或更改该容器内的对象的值。 [23.1 / 11]
笔记2
C ++ 2003中不清楚“结束”迭代器是否遵循上述规则 ; 无论如何，你应该假设他们是（实际上就是这样）。
注3
指针失效的规则与引用无效的规则相同。
C ++ 11 （来源： 迭代器无效规则（C ++ 0x） ）
插入
序列容器
-
vector：插入点之前的所有迭代器和引用不受影响，除非新的容器大小大于先前的容量（在这种情况下，所有的迭代器和引用都是无效的）[23.3.6.5/1] -
deque：所有迭代器和引用都是无效的，除非插入的成员在deque的末端（前面或后面）（在这种情况下，所有迭代器都是无效的，但对元素的引用不受影响）[23.3.3.4/1] -
list：所有迭代器和引用不受影响[23.3.5.4/1] -
forward_list：所有迭代器和引用不受影响（适用于insert_after） [23.3.4.5/1] -
array： （n / a）
关联容器
-
[multi]{set,map}：所有迭代器和引用不受影响[23.2.4 / 9]
未分类的关联容器
-
unordered_[multi]{set,map}：发生重新散列时所有迭代器都失效，但是引用不受影响[23.2.5 / 8]。 如果插入不会导致容器的大小超过z * B其中z是最大负载因子，B是当前的存储桶数量），则不会发生重新散列。 [23.2.5 / 14]
容器适配器
-
stack：从底层容器inheritance -
queue：从底层容器inheritance -
priority_queue：从底层容器inheritance
擦除
序列容器
-
vector：擦除点处或之后的每个迭代器和引用无效[23.3.6.5/3] -
deque：擦除最后一个元素只会使迭代器和对擦除元素和过去末端迭代器的引用无效; 擦除第一个元素只会使迭代器和对擦除元素的引用无效; 擦除任何其他元素使所有迭代器和引用无效（包括过去末端迭代器）[23.3.3.4/4] -
list：只有迭代器和对擦除元素的引用无效[23.3.5.4/3] -
forward_list：只有迭代器和对擦除元素的引用无效（适用于 erase_after ） [23.3.4.5/1] -
array： （n / a）
关联容器
-
[multi]{set,map}：只有迭代器和对被擦除元素的引用无效[23.2.4 / 9]
无序的关联容器
-
unordered_[multi]{set,map}：只有迭代器和对擦除元素的引用无效[23.2.5 / 13]
容器适配器
-
stack：从底层容器inheritance -
queue：从底层容器inheritance -
priority_queue：从底层容器inheritance
调整
-
vector：按照插入/擦除[23.3.6.5/12] -
deque：按照插入/擦除[23.3.3.3/3] -
list：根据插入/擦除[23.3.5.3/1] -
forward_list：按照插入/擦除[23.3.4.5/25] -
array：（n / a）
注1
除非另有规定 （明确地或通过用其他函数定义函数），调用容器成员函数或将容器作为parameter passing给库函数不应使迭代器失效或更改该容器内的对象的值。 [23.2.1 / 11]
笔记2
没有swap（）函数使任何引用，指针或迭代器引用正在交换的容器的元素无效 。 [注意： end（）迭代器不引用任何元素，所以可能会失效 。 – 注意] [23.2.1 / 10]
注3
除了关于swap()的上述警告之外， 还不清楚“end”迭代器是否受到上面列出的每个容器规则的约束 。 无论如何，你应该假设他们是。
注4
vector和所有无序的关联容器支持reserve(n) ，保证不会自动resize，至less在容器的大小增长到n 。 应该注意无序的关联容器，因为未来的build议将允许指定最小的加载因子，这将允许在足够的erase操作将容器大小减小到最小值之后insert时发生重新哈希; erase后应该认为保证可能无效。
可能值得添加的是，只要所有的插入操作都是通过这个迭代器来完成的，并且没有其他迭代器无效的事件，任何types的插入迭代器（ std::back_insert_iterator ， std::front_insert_iterator ， std::insert_iterator ）都将保持有效发生。
例如，当你使用std::insert_iterator向std::vector执行一系列的插入操作时， std::vector很可能会经历一个重新分配事件，这将会使所有指向该向量的迭代器失效。 但是，插入迭代器问题是保证有效，即你可以安全地继续插入序列。 根本不需要担心触发vector重新分配。
这同样仅适用于通过插入迭代器本身执行的插入。 如果迭代器无效事件是由容器上的一些独立的动作触发的，那么插入迭代器也将根据一般规则变为无效。
例如，这个代码
std::vector<int> v(10); std::vector<int>::iterator it = v.begin() + 5; std::insert_iterator<std::vector<int> > it_ins(v, it); for (unsigned n = 20; n > 0; --n) *it_ins++ = rand();
保证在向量中执行插入的有效序列，即使向量“决定”在该过程中间的某个地方重新分配。
由于这个问题得出这么多票和种成为一个常见问题，我想最好是写一个单独的答案，提到一个显着的差异之间的C + + 03和C + + 11关于std::vector的影响插入操作对迭代器的有效性和对reserve()和capacity()引用，这是最有争议的答案未能注意到的。
C ++ 03：
重新分配将使所有引用序列中的元素的引用，指针和迭代器无效。 保证在调用reserve（）之后发生的插入过程中不发生重新分配，直到插入将使向量的大小大于最近调用reserve（）中指定的大小为止。
C ++ 11：
重新分配将使所有引用序列中的元素的引用，指针和迭代器无效。 保证在调用reserve（）之前发生的插入过程中不发生重新分配，直到插入将使vector的大小大于capacity（）的值 。
因此，在C ++ 03中， unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)另外的答案中提到， unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)它不是“ unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) ”，而应该是“ greater than the size specified in the most recent call to reserve() “。 这是C ++ 03与C ++ 11不同之处。 在C ++ 03中，一旦insert()导致vector的大小达到前一个reserve()调用中指定的值（这可能小于当前capacity()因为reserve()会导致更大capacity()比要求），任何后续的insert()可能会导致重新分配和无效所有的迭代器和引用。 在C ++ 11中，不会发生这种情况，您可以始终相信capacity()可以确定地知道下一次重新分配不会在大小超过capacity()之前发生。
总而言之，如果你使用的是C ++ 03向量，并且要确保在执行插入操作时不会发生重新分配，那么它就是你之前传递给reserve()的参数的值，你应该检查它的大小而不是调用capacity()的返回值，否则你可能会对“ 过早 ”重新分配感到惊讶。
