pop_back() 真的会使 std::vector 上的所有迭代器无效吗？

https://stackoverflow.com/questions/62340

09-06-2019
|

题

std::vector<int> ints;

// ... fill ints with random values

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
    {
        *it = ints.back();
        ints.pop_back();
        continue;
    }
    it++;
}

该代码不起作用，因为当 pop_back() 叫做， it 无效。但我没有找到任何讨论迭代器失效的文档 std::vector::pop_back().

你有一些相关的链接吗？

解决方案

致电给 pop_back() 删除向量中的最后一个元素，因此该元素的迭代器无效。这 pop_back() 打电话确实不是使最后一个元素之前的项目的迭代器无效，只有重新分配才能做到这一点。来自 Josuttis 的《C++ 标准库参考》：

插入或删除元素无效引用的参考文献，指示器和迭代器，引用以下元素。如果插入导致重新分配，则它将使所有参考，迭代器和指针无效。

其他提示

这是直接来自神圣标准的答案：

23.2.4.2 载体满足容器和可逆容器（在 23.1 中的两个表中给出）和序列的所有要求，包括大多数可选序列要求（23.1.1）。

23.1.1.12表68 Expressiona.pop_back（）返回类型为操作语义a.擦除(--a.end())容器向量、列表、双端队列

请注意，a.pop_back 相当于a.erase(--a.end())。查看向量关于擦除的细节：

23.2.4.3.3 - 迭代器擦除（迭代器位置） - 效果 - 使擦除点之后的所有迭代器和引用无效

因此，一旦调用 pop_back，之前的最终元素（现在不再存在）的任何迭代器都会失效。

查看您的代码，问题在于，当您删除最后一个元素并且列表变空时，您仍然会增加它并离开列表的末尾。

（我使用 C++0x 工作草案中使用的编号方案，可以在这里获得

第 732 页的表 94 指出 pop_back（如果它存在于序列容器中）具有以下效果：

{ iterator tmp = a.end(); 
--tmp; 
a.erase(tmp); }

23.1.1 第 12 点指出：

除非另有说明（要么明确或通过其他函数定义函数），否则调用容器成员函数或将容器作为参数传递到库函数的函数不得无效或更改该容器中的对象的值。

两种访问 end() 作为应用前缀的方式都没有这样的效果，然而，erase() ：

23.2.6.4（关于 vector.erase() 第 4 点）：

效果：在擦除点或擦除点之后使迭代器和引用无效。

所以结论是：根据标准，pop_back() 只会使最后一个元素的迭代器无效。

这是 SGI 的 STL 文档中的引用（http://www.sgi.com/tech/stl/Vector.html):

[5] 当向量的内存被重新分配时，向量的迭代器将失效。此外，在向量中间插入或删除元素会使指向插入或删除点之后的元素的所有迭代器无效。因此，如果使用 Reserve() 预分配向量将使用的内存，并且所有插入和删除都位于向量的末尾，则可以防止向量的迭代器失效。

我认为 pop_back 只会使指向最后一个元素的迭代器和 end() 迭代器无效。我们确实需要查看代码失败的数据，以及它无法确定发生了什么的方式。据我所知，代码应该可以工作 - 此类代码中的常见问题是迭代器上的元素和 ++ 的删除发生在同一次迭代中，正如 @mikhaild 指出的那样。然而，在这段代码中，情况并非如此：调用 pop_back 时 it++ 不会发生。

当它指向最后一个元素并且最后一个元素小于 10 时，仍然可能会发生一些不好的事情。我们现在正在比较一个 无效的 它和结束（）。它可能仍然有效，但不能做出任何保证。

迭代器仅在重新分配存储时才会失效。谷歌是你的朋友：见脚注5.

您的代码由于其他原因无法正常工作。

pop_back() 仅使指向最后一个元素的迭代器无效。来自 C++ 标准库参考：

插入或删除元素无效引用的参考文献，指示器和迭代器，引用以下元素。如果插入导致重新分配，则它将使所有参考，迭代器和指针无效。

所以回答你的问题，不，它不会无效全部迭代器。

但是，在您的代码示例中，它可能会使 it 当它指向最后一个元素并且该值低于 10 时。在这种情况下，Visual Studio 调试 STL 会将迭代器标记为无效，并进一步检查它是否不等于 end() 将显示断言。

如果迭代器被实现为纯指针（就像它们可能在所有非调试 STL 向量情况下一样），那么您的代码应该可以正常工作。如果迭代器不仅仅是指针，那么您的代码无法正确处理删除最后一个元素的情况。

错误是，当“it”指向向量的最后一个元素并且该元素小于10时，则删除最后一个元素。现在“it”指向ints.end()，下一个“it++”将指针移动到ints.end()+1，所以现在“it”逃离了ints.end()，并且你得到了无限循环扫描所有你的记忆：）。

“官方规范”是 C++ 标准。如果您无法访问 C++03 的副本，您可以从委员会的网站获取 C++0x 的最新草案： http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf

容器要求的“操作语义”部分指定 pop_back() 等效于 { iterator i = end(); - 我;擦除（一）；}。用于擦除的 [vector.modifiers] 部分显示“效果：在擦除点或擦除点之后使迭代器和引用无效。”

如果你想要直觉参数，pop_back是无失败的（因为标准容器中的value_types的破坏不允许抛出异常），所以它不能做任何复制或分配（因为它们可以抛出），这意味着你可以猜测到被擦除元素的迭代器和结束迭代器无效，但其余部分则不然。

pop_back() 只会失效它如果它指向向量中的最后一项。因此，只要向量中的最后一个 int 小于 10，您的代码就会失败，如下所示：

*it = ints.back();// 将 *it 设置为已有的值
ints.pop_back();// 使迭代器无效
继续;// 循环并访问无效迭代器

您可能需要考虑使用擦除的返回值，而不是将后退元素交换到已删除的位置并弹回。对于序列，擦除返回一个迭代器，该迭代器指向要删除的元素之外的元素。请注意，此方法可能会导致比原始算法更多的复制。

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
        it = ints.erase( it );
    else
        ++it;
}

std::remove_if 也可能是一个替代解决方案。

struct LessThanTen { bool operator()( int n ) { return n < 10; } };

ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );

std::remove_if 是（就像我的第一个算法一样）稳定，所以它可能不是最有效的方法，但它很简洁。

查看信息这里 (cplusplus.com):

删除最后一个元素

删除向量中的最后一个元素，有效地将向量大小减少一并使所有迭代器和对其的引用无效。

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow

pop_back() 真的会使 std::vector 上的*所有*迭代器无效吗？

pop_back() 真的会使 std::vector 上的所有迭代器无效吗？