如何知道`std::vector::begin()`变得无效？

Question

下面的代码片段可以在cppreference中看到。

为什么第三次插入vecotr时

std::vector::begin()

无效。我认为当向量被重新分配时，

std::vector::begin()

变得无效。

C++ 标准中是否严格定义了重新分配？如果没有，似乎每次在演示代码中调用

std::vector::begin()

时都应该调用

insert()

。

#include <iostream>
#include <iterator>
#include <vector>
 
void print(int id, const std::vector<int>& container)
{
    std::cout << id << ". ";
    for (const int x : container)
        std::cout << x << ' ';
    std::cout << '\n';
}
 
int main ()
{
    std::vector<int> c1(3, 100);
    print(1, c1);
 
    auto it = c1.begin();
    it = c1.insert(it, 200);
    print(2, c1);
 
    c1.insert(it, 2, 300);  //ME: why begin() still valid?
    print(3, c1);
 
    // `it` no longer valid, get a new one:
    it = c1.begin();
 
    std::vector<int> c2(2, 400);
    c1.insert(std::next(it, 2), c2.begin(), c2.end());
    print(4, c1);
 
    int arr[] = {501, 502, 503};
    c1.insert(c1.begin(), arr, arr + std::size(arr));
    print(5, c1);
 
    c1.insert(c1.end(), {601, 602, 603});
    print(6, c1);
}

Answer 1

C++ 标准中是否严格定义了重新分配？

定义了

std::vector

允许重新分配，但没有规定何时重新分配。您只需在添加新数据之前调用

reserve

或

resize

即可。如果新数据需要重新分配，算法通常是复制分配的内存，意味着 2,4,8,16...

您只需查看 Iterator invalidation 部分中的

std::vector

即可了解迭代器何时失效。

Answer 2

为什么第三次插入vecotr时

std::vector::begin()

无效。

std::vector::begin

并非无效。不过，之前存储的迭代器可能会在任何时候调用

insert

时失效。

C++ 标准中是否严格定义了重新分配？

不。这是一个实施细节。虽然很明显，c++ 标准指定了

std::vector

，但必须进行重新分配。并且插入元素对时间复杂度的要求是实现不能在每次插入时重新分配。因此，每次插入都可能使迭代器无效。

std::vector::begin()

每次在演示代码中调用 insert() 时都应该调用。

不。

it

在代码中多次使用。插入元素时，迭代器

it

总是会在再次使用之前用有效的迭代器进行更新。