列表迭代器与向量迭代器

Question

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

1. 我认为，一旦您为STL容器(如向量或列表)定义了迭代器，如果将元素添加到容器中，则这些迭代器将无法访问它们。但是，下面的代码定义了一个由五个元素组成的列表，然后在每个循环迭代中添加另一个元素，并导致一个无限循环： #包括使用命名空间std；int main() { list ls；for(int i= 0；i< 5；i++) { ls.push_back(i)；} int idx = 0；for(列表：：iterator iter = ls.begin()；iter != ls.end()；iter++) { cout << " idx：“<< idx <<，*iter：”<< *iter << endl；ls.push_back(7)；idx++；} 但是，对向量做同样的操作会导致一个错误： #包括使用命名空间std；int main() {向量vec；for(int i= 0；i< 5；i++) { vec.push_back(i)；} int idx = 0；for(向量：：iterator iter = vec.begin()；iter != vec.end()；iter++) { cout << " idx：“<< idx <<，*iter：”<< *iter << endl；vec.push_back(7)；idx++；}
2. 我认为，当向量容器必须调整大小时，它的大小是2的幂，并且位于一个新的内存区域，这就是为什么如果向向量添加元素(因为迭代器不会传递到新的内存位置)，就不应该向向量定义迭代器。例如，我认为一个包含16个元素的向量，在调用push_back函数之后，将为32个元素分配空间，整个向量将被重新定位。但是，以下代码没有发生这种情况。我是否只是使用名称空间std；int main() {向量vec；for(int i= 0；i< 4；i++) { vec.push_back(i)；cout <<“地址vec：”<< &vec << "，容量：“<< vec.capacity() << endl；} for(int i= 0；i< 20；i++) { vec.push_back(i)；cout <<地址vec：“<< &vec << "，容量：”<< vec.capacity() << endl；}“

Answer 1

不同容器的迭代器具有不同的属性。Here are the iterator invalidation rules。

当您将列表循环推到上时，列表循环：所有以前的迭代器都仍然有效。显然，如果每次迭代器转发一个迭代器时还添加了一个新元素，那么您就永远不会到达终点。

向量循环：对于向量，一旦push_back导致新的大小超过旧容量，迭代器就无效。一旦发生这种情况，使用iter就是未定义的行为(您可能会崩溃)。

我认为当向量容器必须调整大小时，它会以2的幂进行调整，并且位于一个新的内存区域。

这是标准没有规定的。C++标准库的一些实现在容量超过旧容量时是向量容量的两倍，而其他实现则以不同的速率增长。

Answer 2

你第一个问题的答案载于你的第二个问题。

至于第二个问题，则是实现定义了向量如何分配内存。没有必要在每次耗尽内存时将内存的大小翻一番。

Answer 3

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

1. 对于std::list<T>，对元素的迭代器和指针/引用仍然有效，直到相应的节点被擦除或std::list<T>存在为止。
2. 对于std::vector<T>来说，有效性更复杂：
   1. Iterator和指针/引用的有效性是相同的(我将只使用下面的迭代器)。
   2. 当std::vector<T>需要调整其内部缓冲区的大小时，即当插入超出容量时，所有迭代器都失效。当超过容量和分配多少内存取决于实现(唯一的要求是容量成倍增长，2是一个合理的选择，但还有许多其他的选择)。
   3. 当插入到std::vector<T>中时，插入点之前的所有迭代器都保持有效，除非重新分配是必要的。
   4. 当从std::vector<T>中擦除时，所有经过擦除点的迭代器都失效。

​

其他容器具有不同的有效性约束(例如，std::deque<T>使迭代器无效，但可以使指针/引用有效)。