4

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

  1. 我认为，一旦您为 STL 容器（例如向量或列表）定义了迭代器，如果您将元素添加到容器中，那么这些迭代器将无法访问它们。但是下面的代码定义了一个包含五个元素的列表，然后在每次循环迭代中添加另一个元素并导致无限循环：

    #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++;
    }
}

    但是，对向量执行相同操作会导致错误：

    #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. 我认为当必须调整向量容器的大小时，它会以 2 的幂次方进行，并且位于新的内存区域，这就是为什么如果向向量添加元素时不应该为向量定义迭代器（因为迭代器不会被传递到新的内存位置）。例如，我认为一个包含 16 个元素的向量，在调用 push_back 函数后，将分配 32 个元素的空间，整个向量将被重新定位。但是，以下代码没有发生这种情况。我是不是弄错了？ 

    #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;
    }
}
4

3 回答 3

3

Different container's iterators have different properties. Here are the iterator invalidation rules.

The list loop: When you push onto a list all previous iterators still valid. You will never hit the end if every time you iterator forward one you also add a new element, obviously.

The vector loop: For a vector, your iterators are invalid once a push_back results in the new size exceeding the old capacity. As soon as this happens, using iter is undefined behavior (you will likely crash).

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

This is unspecified by the standard. Some implementations of the C++ standard library double the capacity of a vector when the size exceeds the old capacity, and others grow at different rates.

于 2013-12-24T20:50:31.200 回答
0

The answer on your first question is contained in the second your question.

As for the second question then it is implementation defined how the vector allocates the memory. It is not necessary that it will double the size of the memory each time when it is exhausted.

于 2013-12-24T20:50:18.513 回答
0

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

  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>保持迭代器无效但可以保持指针/引用有效）。

于 2013-12-24T20:53:43.620 回答