列表迭代器 vs. 向量迭代器

Question

我有两个关于迭代器的问题。

1. I thought the once you define an iterator to an STL container such as a vector or a list, if you add elements to the containers then these iterators won't be able to access them. But the following code defines a list of five elements and then adds another element in each loop iteration and results in an infinite loop:

   #include <iostream>
   #include <list>
   
   using namespace std;
   
   int main()
   {
       list<int> ls;
   
       for(int i = 0; i < 5; i++)
       {
           ls.push_back(i);
       }
   
       int idx = 0;
   
       for(list<int>::iterator iter = ls.begin(); iter != ls.end(); iter++)
       {
           cout << "idx: " << idx << ", *iter: " << *iter << endl;
           ls.push_back(7);
           idx++;
       }
   }
   

   However, doing the same for a vector results in an error:

   #include <iostream>
   #include <vector>
   
   using namespace std;
   
   int main()
   {
       vector<int> vec;
   
       for(int i = 0; i < 5; i++)
       {
           vec.push_back(i);
       }
   
       int idx = 0;
   
       for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++)
       {
           cout << "idx: " << idx << ", *iter: " << *iter << endl;
           vec.push_back(7);
           idx++;
       }
   }
   

2. I thought that when the vector container must be resized, it does so at powers of 2 and is located to a new area of memory, which is why you shouldn't define an iterator to a vector if you adding elements to it (since the iterators don't get passed to the new memory location). For example, I thought a vector containing 16 elements, after calling the push_back function, will be allocated space for 32 elements and the entire vector will be relocated. However, the this didn't happen for the following code. Was I just mistaken?

   #include <iostream>
   #include <vector>
   
   using namespace std;
   
   int main()
   {
       vector<int> vec;
   
       for(int i = 0; i < 4; i++)
       {
           vec.push_back(i);
           cout << "address of vec: " << &vec << ", capacity: " << vec.capacity() << endl;
       }
   
   
   
       for(int i = 0; i < 20; i++)
       {
           vec.push_back(i);
           cout << "address of vec: " << &vec << ", capacity: " << vec.capacity() << endl;
       }
   }
   

- bcf

---

不要假设事情。stdlib类的文档清楚地描述了在容器上进行某些类型的变异时，哪些迭代器何时被使无效。 - user529758

这里有一个关于迭代器何时失效的好答案：https://dev59.com/OGw15IYBdhLWcg3wuuGn#6438087 - Xymostech

请注意，一个无效的迭代器在指针值上可能与一个有效的迭代器无法区分。例如，当vector重新调整大小时，它的新存储可能从与旧存储相同的地址开始。即使你可以确保vector增加了其capacity()，也不能保证它位于不同的地址上。只有vector的规则告诉你何时迭代器被认为是有效或无效的。 - Joe Z

一个 vector 的容量增加速率并没有被标准规定。只要保持 push_back() 的摊销复杂度为 O(1)（并且保持其他方法的复杂度要求），实现可以以 1.5x、2x、3x 或任何它想要的速率进行。 - Cornstalks

Answer 1

不同容器的迭代器具有不同的属性。这里是迭代器失效规则。 链表循环：当您将元素推入list时，所有先前的迭代器仍然有效。如果每次向前迭代一个元素时也添加一个新元素，那么您永远不会到达末尾。 向量循环：对于向量，一旦push_back导致新大小超过旧容量，则您的迭代器无效。一旦发生这种情况，使用iter就是未定义的行为（您可能会崩溃）。

我认为当向量容器必须调整大小时，它会在2的幂处进行调整，并位于新的内存区域中

这在标准中没有指定。C++标准库的某些实现在大小超过旧容量时将向量的容量加倍，而其他实现则以不同的速率增长。

- David

---

@Dave，“implementation”是什么意思？我正在使用Visual C++ 2010 Express，我想这和使用emacs不同吧？ - bcf

@David，Emacs只是一个编辑器。我说的是标准库的实现。VS2010自带一个。Emacs没有。微软有选择地增加向量容量的选项。标准并没有 - David

@David：这里的“实现”指的是C++编译器及其标准库。Visual Studio C++自带C++编译器，而Emacs则没有。目前有多个不同的编译器可供选择，例如gcc和clang都是流行的开源编译器。 - Dietmar Kühl

@DietmarKühl您应该比我更清楚，但您所提到的“实现定义”和“未指定”的语义差异似乎相当模糊 - 您能详细解释一下吗？对我来说它们的意思是一样的。 - David

@DietmarKühl，“每次不同的选择”难道不能只是实现定义合同的一部分吗？如果标准中有“未指定”的内容，那么实现必须自己定义它。如果某些内容既“未由标准指定”又“由实现定义”，则另一个内容必须被暗示为真...是吗？看起来你所说的区别只是文档的问题？ - David

Answer 2

你第一个问题的答案包含在你的第二个问题中。

至于第二个问题，向量分配内存的方式是实现定义的。当内存用尽时，它不一定会每次都将内存大小加倍。

- Vlad from Moscow

Answer 3

不同的容器通常对于迭代器和指向元素的指针/引用的有效性有不同的保证：

1. 对于 std::list<T>，迭代器和指向元素的指针/引用在相应节点被删除或 std::list<T> 不存在之前保持有效。
2. 对于 std::vector<T>，有效性更为复杂：
   1. 迭代器和指针/引用的有效性是相同的（下面只使用迭代器）。
   2. 当 std::vector<T> 需要调整其内部缓冲区大小时，即插入操作超出容量时，所有迭代器都无效。当超出容量以及分配多少内存取决于实现（唯一的要求是容量呈指数增长，2 的因子是一个合理的选择，但还有许多其他选择）。
   3. 在向 std::vector<T> 插入元素时，除非需要重新分配内存，否则插入点之前的所有迭代器都保持有效。
   4. 从 std::vector<T> 删除元素时，所有删除点之后的迭代器都无效。

其他容器也有不同的有效性限制（例如，std::deque<T> 会使迭代器失效，但可以保持指针/引用有效）。

- Dietmar Kühl