为什么即使没有内存重新分配，在 for 循环中调用 push_back 也是不安全的？

Question

当我阅读这篇文章时 post:

我明白，在 for 循环中调用 push_back 是不安全的，因为：

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

那么，我假设如果我保证不超过容量，那就安全了....

但显然不是，下面的所有实现都会在第一次调用 push_back 后崩溃（使用 Visual Studio），即使我可以看到容量在循环中保持不变（所以我假设向量不重新分配其内存）：

版本 1:

std::vector<int> v1{ 3, 4, 5 };
v1.reserve( v1.size()*2 );
size_t c1 = v1.capacity();
for ( auto val : v1 )
{
    v1.push_back( val );
    c1 = v1.capacity();
}

版本 2:

std::vector<int> v2{ 3, 4, 5 };
v2.reserve( v2.size()*2 );
size_t c2 = v2.capacity();
auto curEnd = v2.end();
for ( auto iter = v2.begin(); iter != curEnd; ++iter )
{
    v2.push_back( *iter );
    c2 = v2.capacity();
}

版本 3:

std::vector<int> v3{ 3, 4, 5 };
v3.reserve( v3.size()*2 );
size_t c3 = v3.capacity();
for ( auto iter = v3.begin(); iter != v3.end(); ++iter )
{
    v3.push_back( *iter );
    c3 = v3.capacity();
}

是什么导致这些代码崩溃？

Answer 1

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

在这两种情况下，结束迭代器仅在变量中存储一次，因此一旦添加元素，该迭代器就无效，使用它是未定义的行为。

您需要在每次循环迭代中获取新的结束迭代器，就像您在版本 3 中所做的那样。但是那个也会崩溃！

出于完全相同的原因。您的循环实际上是无限的，并且永远不会停止为对象分配内存。因为容量不是无限的，你将得到重新分配，然后你有未定义的行为。

您总是在向向量中添加一个元素，并且由于循环在遍历每个元素时停止，所以它永远不会停止。有点像

int end = 1;
for (int i = 0; i < end; ++i) // infinite!
  ++end;

如果您想再次添加这三个元素，您始终可以使用基于索引的循环。甚至更多，前提是您预留了足够的存储空间。 :)

Answer 2

你的前两个版本都有同样的问题。缓存的尾后迭代器在第一次插入后失效，使任何后续使用成为 UB。是的，甚至只是对比一下。

您的第三个示例崩溃了，因为它最终尝试重新插入新插入的元素。所以它最终需要重新分配，最终导致更多的 UB。

正确的基于迭代器的方法是直到最后一个结束。但直到最后，假设向量不为空。

std::vector<int> v{ 3, 4, 5 };
v.reserve( v.size()*2 );

auto it = v.begin(), end = v.end();
--end;
do {
  v.push_back(*it);
} while (it++ != end); // Check against current position, but increment still

Answer 3

我强调的同一句话：

If the new size() is greater than capacity() then all iterators and references (including the past-the-end iterator) are invalidated. Otherwise only the past-the-end iterator is invalidated.

Version2 的

curEnd 是尾后迭代器，因此无效。 Version1 在语法糖下做了类似的事情。

版本 3 将继续迭代新插入的元素，直到重新分配发生。即使没有重新分配，它也会无限循环，直到所有内存耗尽。

通过存储旧大小（count）修改 Version3 的简单解决方案，并循环直到 begin + count

std::vector<int> v3{ 3, 4, 5 };
auto count = v3.size();
v3.reserve( v3.size()*2 );
size_t c3 = v3.capacity();
for ( auto iter = v3.begin(); iter != v3.begin() + count; ++iter )
{
    v3.push_back( *iter );
    c3 = v3.capacity();
}

另一种是使用老式的索引循环。

为什么即使没有内存重新分配，在 for 循环中调用 push_back 也是不安全的？

Why is it unsafe to call push_back in a for loop even when there is no memory reallocation?

c++

for-loop

push-back