在迭代时从 std: : set 中删除元素

我需要遍历一个集合并删除满足预定义条件的元素。

这是我写的测试代码:

#include <set>
#include <algorithm>


void printElement(int value) {
std::cout << value << " ";
}


int main() {
int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::set<int> numbers(initNum, initNum + 10);
// print '0 1 2 3 4 5 6 7 8 9'
std::for_each(numbers.begin(), numbers.end(), printElement);


std::set<int>::iterator it = numbers.begin();


// iterate through the set and erase all even numbers
for (; it != numbers.end(); ++it) {
int n = *it;
if (n % 2 == 0) {
// wouldn't invalidate the iterator?
numbers.erase(it);
}
}


// print '1 3 5 7 9'
std::for_each(numbers.begin(), numbers.end(), printElement);


return 0;
}

起初，我认为在迭代过程中从集合中删除一个元素会使迭代器失效，for 循环中的增量会出现未定义行为。尽管如此，我执行了这个测试代码，一切都很顺利，我不能解释为什么。

我的问题是: 这是为 std 集定义的行为，还是这个实现是特定的？顺便说一下，我在 ubuntu10.04(32位版本)上使用的是 gcc4.3.3。

谢谢！

建议解决方案:

这是从集合中迭代和擦除元素的正确方法吗？

while(it != numbers.end()) {
int n = *it;
if (n % 2 == 0) {
// post-increment operator returns a copy, then increment
numbers.erase(it++);
} else {
// pre-increment operator increments, then return
++it;
}
}

编辑: 首选解决方案

我想到了一个对我来说更优雅的解决方案，尽管它的效果完全一样。

while(it != numbers.end()) {
// copy the current iterator then increment it
std::set<int>::iterator current = it++;
int n = *current;
if (n % 2 == 0) {
// don't invalidate iterator it, because it is already
// pointing to the next element
numbers.erase(current);
}
}

如果 while 中有几个测试条件，那么每个测试条件都必须递增迭代器。我更喜欢这段代码，因为迭代器是递增的 只在一个地方，使代码更少出错和更易读。

120313 次浏览
小开

这种行为是特定于实现的。为了保证迭代器的正确性，如果需要删除元素，应该使用“ it = numbers.delete (it) ;”语句，如果需要删除元素，则使用简单的附加迭代器。

小开
最佳答案

这取决于执行情况:

标准23.1.2.8:

插入成员不会影响迭代器和对容器的引用的有效性，擦除成员只会使对擦除元素的迭代器和引用无效。

也许你可以试试这个，这是标准配置:

for (auto it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
numbers.erase(it++);
}
else {
++it;
}
}

注意，+ + 是后缀，因此它传递要擦除的旧位置，但是由于操作符的原因，它首先跳转到一个较新的位置。

2015.10.27更新: C + + 11已经解决了这个缺陷。iterator erase (const_iterator position);返回一个迭代器到最后一个被移除的元素之后的元素(或者 set::end，如果最后一个元素被移除的话)。所以 C + + 11的风格是:

for (auto it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
it = numbers.erase(it);
}
else {
++it;
}
}
小开

你误解了“未定义行为”的意思。未定义行为并不意味着“如果你这样做，你的程序 abc0崩溃或产生意想不到的结果。”它的意思是“如果你这样做，你的程序 可以崩溃或产生意想不到的结果”，或做任何其他事情，这取决于你的编译器，你的操作系统，月相等。

如果某个程序执行时没有崩溃，并且按照您的预期运行，那么这就证明了它不是未定义行为。它所能证明的只是，在特定操作系统上使用特定编译器进行编译之后，它的行为碰巧和在特定运行中观察到的一样。

从集合中擦除一个元素会使到擦除元素的迭代器失效。使用无效的迭代器是未定义行为。只是碰巧观察到的行为是您在这个特定实例中想要的; 这并不意味着代码是正确的。

小开

如果您通过 valground 运行您的程序，您将看到一系列读取错误。换句话说，是的，迭代器是无效的，但是在你的例子中你很幸运(或者非常不幸，因为你没有看到未定义行为的负面影响)。一种解决方案是创建一个临时迭代器，递增临时值，删除目标迭代器，然后将目标设置为临时值。例如，按以下方式重写循环:

std::set<int>::iterator it = numbers.begin();
std::set<int>::iterator tmp;


// iterate through the set and erase all even numbers
for ( ; it != numbers.end(); )
{
int n = *it;
if (n % 2 == 0)
{
tmp = it;
++tmp;
numbers.erase(it);
it = tmp;
}
else
{
++it;
}
}
小开

提醒一下，在 deque 容器的情况下，所有检查 deque 迭代器与 numbers.end ()相等的解决方案在 gcc 4.8.4上都可能失败。也就是说，擦除 deque 的一个元素通常会使 numbers.end ()的指针失效:

#include <iostream>
#include <deque>


using namespace std;
int main()
{


deque<int> numbers;


numbers.push_back(0);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
//numbers.push_back(4);


deque<int>::iterator  it_end = numbers.end();


for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
cout << "Erasing element: " << *it << "\n";
numbers.erase(it++);
if (it_end == numbers.end()) {
cout << "it_end is still pointing to numbers.end()\n";
} else {
cout << "it_end is not anymore pointing to numbers.end()\n";
}
}
else {
cout << "Skipping element: " << *it << "\n";
++it;
}
}
}

产出:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

注意，虽然 deque 转换在这个特殊情况下是正确的，但是结束指针在这个过程中是无效的。随着规模的变化，这种错误变得更加明显:

int main()
{


deque<int> numbers;


numbers.push_back(0);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(4);


deque<int>::iterator  it_end = numbers.end();


for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
if (*it % 2 == 0) {
cout << "Erasing element: " << *it << "\n";
numbers.erase(it++);
if (it_end == numbers.end()) {
cout << "it_end is still pointing to numbers.end()\n";
} else {
cout << "it_end is not anymore pointing to numbers.end()\n";
}
}
else {
cout << "Skipping element: " << *it << "\n";
++it;
}
}
}

产出:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

以下是解决这个问题的方法之一:

#include <iostream>
#include <deque>


using namespace std;
int main()
{


deque<int> numbers;
bool done_iterating = false;


numbers.push_back(0);
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(4);


if (!numbers.empty()) {
deque<int>::iterator it = numbers.begin();
while (!done_iterating) {
if (it + 1 == numbers.end()) {
done_iterating = true;
}
if (*it % 2 == 0) {
cout << "Erasing element: " << *it << "\n";
numbers.erase(it++);
}
else {
cout << "Skipping element: " << *it << "\n";
++it;
}
}
}
}
小开

我遇到了同样的老问题，并发现下面的代码更多的 可以理解，这是在每上述解决方案的方式。

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
// Use your member
std::cout<<(*beginIt)<<std::endl;


// delete the object
delete (*beginIt);


// erase item from vector
listOfInts.erase(beginIt );


// re-calculate the begin
beginIt = listOfInts.begin();
}
小开

我认为使用 STL 方法‘ remove_if’from 可以帮助避免在尝试删除迭代器包装的对象时出现一些奇怪的问题。

这种解决方案可能效率较低。

假设我们有一个容器，比如向量或者一个名为 m _ Bullet 的列表:

Bullet::Ptr is a shared_pr<Bullet>

‘ it’是‘ remove_if’返回的迭代器，第三个参数是在容器的每个元素上执行的 lambda 函数。因为容器包含 Bullet::Ptr，lambda 函数需要将该类型(或对该类型的引用)作为参数传递。

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
// dead bullets need to be removed from the container
if (!bullet->isAlive()) {
// lambda function returns true, thus this element is 'removed'
return true;
}
else{
// in the other case, that the bullet is still alive and we can do
// stuff with it, like rendering and what not.
bullet->render(); // while checking, we do render work at the same time
// then we could either do another check or directly say that we don't
// want the bullet to be removed.
return false;
}
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still
// exist and needs to be removed if you do not want to manually fill it later
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

‘ remove_if’删除 lambda 函数返回 true 的容器，并将该内容移到容器的开头。“ it”指向一个可被视为垃圾的未定义对象。对象从“ it”到 m _ Bullet。End ()可以被擦除，因为它们占用内存，但包含垃圾，因此在该范围内调用“擦除”方法。

小开

C + + 20将有“统一容器删除”功能，你可以写:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

这对于 vector、 set、 deque等都适用。 有关更多信息，请参见 参考文献。


提交答案