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

Deleting elements from std::set while iterating

提问by pedromanoel

I need to go through a set and remove elements that meet a predefined criteria.

我需要通过一个集合并删除满足预定义标准的元素。

This is the test code I wrote:

这是我写的测试代码：

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

At first, I thought that erasing an element from the set while iterating through it would invalidate the iterator, and the increment at the for loop would have undefined behavior. Even though, I executed this test code and all went well, and I can't explain why.

起初，我认为在迭代时从集合中删除一个元素会使迭代器无效，并且 for 循环中的增量会有未定义的行为。尽管如此，我执行了这个测试代码并且一切顺利，我无法解释为什么。

My question:Is this the defined behavior for std sets or is this implementation specific? I am using gcc 4.3.3 on ubuntu 10.04 (32-bit version), by the way.

我的问题：这是标准集的定义行为还是特定于该实现？顺便说一下，我在 ubuntu 10.04（32 位版本）上使用 gcc 4.3.3。

Thanks!

谢谢！

Proposed solution:

建议的解决方案：

Is this a correct way to iterate and erase elements from the set?

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

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

Edit: PREFERED SOLUTION

编辑：首选解决方案

I came around a solution that seems more elegant to me, even though it does exactly the same.

我找到了一个对我来说似乎更优雅的解决方案，即使它的作用完全相同。

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);
    }
}

If there are several test conditions inside the while, each one of them must increment the iterator. I like this code better because the iterator is incremented only in one place, making the code less error-prone and more readable.

如果 while 中有多个测试条件，则每个测试条件都必须增加迭代器。我更喜欢这段代码，因为迭代器只在一处递增，使代码不易出错且更具可读性。

回答by Kornel Kisielewicz

This is implementation dependent:

这是依赖于实现的：

Standard 23.1.2.8:

标准 23.1.2.8：

The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

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

Maybe you could try this -- this is standard conforming:

也许你可以试试这个——这是符合标准的：

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

Note that it++ is postfix, hence it passes the old position to erase, but first jumps to a newer one due to the operator.

请注意，it++ 是后缀，因此它通过旧位置进行擦除，但由于运算符的原因首先跳转到新位置。

2015.10.27 update:C++11 has resolved the defect. iterator erase (const_iterator position);return an iterator to the element that follows the last element removed (or set::end, if the last element was removed). So C++11 style is:

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

回答by Matt

If you run your program through valgrind, you'll see a bunch of read errors. In other words, yes, the iterators are being invalidated, but you're getting lucky in your example (or really unlucky, as you're not seeing the negative effects of undefined behavior). One solution to this is to create a temporary iterator, increment the temp, delete the target iterator, then set the target to the temp. For example, re-write your loop as follows:

如果你通过 valgrind 运行你的程序，你会看到一堆读取错误。换句话说，是的，迭代器正在失效，但是在您的示例中您很幸运（或者真的很不幸，因为您没有看到未定义行为的负面影响）。对此的一种解决方案是创建一个临时迭代器，增加临时值，删除目标迭代器，然后将目标设置为临时值。例如，按如下方式重新编写循环：

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

回答by Tyler McHenry

You misunderstand what "undefined behavior" means. Undefined behavior does not mean "if you do this, your program willcrash or produce unexpected results." It means "if you do this, your program couldcrash or produce unexpected results", or do anything else, depending on your compiler, your operating system, the phase of the moon, etc.

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

If something executes without crashing and behaves as you expect it to, that is notproof that it is not undefined behavior. All it proves is that its behavior happened to be as observed for that particular run after compiling with that particular compiler on that particular operating system.

如果某些东西在没有崩溃的情况下执行并且按照您的预期运行，这并不能证明它不是未定义的行为。它所证明的只是它的行为恰好与在该特定操作系统上使用该特定编译器编译后针对该特定运行观察到的一样。

Erasing an element from a set invalidates the iterator to the erased element. Using an invalidated iterator is undefined behavior. It just so happened that the observed behavior was what you intended in this particular instance; it does not mean that the code is correct.

从集合中删除一个元素会使到被删除元素的迭代器失效。使用无效的迭代器是未定义的行为。恰巧观察到的行为正是您在此特定情况下的意图；这并不意味着代码是正确的。

回答by McKryak

Just to warn, that in case of a deque container, all solutions that check for the deque iterator equality to numbers.end() will likely fail on gcc 4.8.4. Namely, erasing an element of the deque generally invalidates pointer to numbers.end():

只是提醒一下，在双端队列容器的情况下，所有检查双端队列迭代器是否与 numbers.end() 相等的解决方案都可能在 gcc 4.8.4 上失败。即，擦除双端队列的元素通常会使指向 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;
    }
  }
}

Output:

输出：

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()

Note that while the deque transformation is correct in this particular case, the end pointer has been invalidated along the way. With the deque of a different size the error is more apparent:

请注意，虽然在这种特殊情况下双端队列转换是正确的，但在此过程中结束指针已失效。对于不同大小的双端队列，错误更加明显：

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

Output:

输出：

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)

Here is one of the ways to fix this:

这是解决此问题的方法之一：

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

回答by Marshall Clow

C++20 will have "uniform container erasure", and you'll be able to write:

C++20 将具有“统一容器擦除”，您将能够编写：

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

And that will work for vector, set, deque, etc. See cppReferencefor more info.

这将适用于vector、set、deque等。有关更多信息，请参阅cppReference。

回答by John Behm

I think using the STL method 'remove_if' from could help to prevent some weird issue when trying to attempt to delete the object that is wrapped by the iterator.

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

This solution may be less efficient.

此解决方案可能效率较低。

Let's say we have some kind of container, like vector or a list called m_bullets:

假设我们有某种容器，例如向量或名为 m_bullets 的列表：

Bullet::Ptr is a shared_pr<Bullet>

'it' is the iterator that 'remove_if' returns, the third argument is a lambda function that is executed on every element of the container. Because the container contains Bullet::Ptr, the lambda function needs to get that type(or a reference to that type) passed as an argument.

' 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' removes the container where the lambda function returned true and shifts that content to the beginning of the container. The 'it' points to an undefined object that can be considered garbage. Objects from 'it' to m_bullets.end() can be erased, as they occupy memory, but contain garbage, thus the 'erase' method is called on that range.

' remove_if' 删除 lambda 函数返回 true 的容器并将该内容移到容器的开头。' it' 指向可被视为垃圾的未定义对象。从 'it' 到 m_bullets.end() 的对象可以被擦除，因为它们占用内存，但包含垃圾，因此在该范围内调用 'erase' 方法。

回答by Vitaly Bogdanov

This behaviour is implementation specific. To guarantee the correctness of the iterator you should use "it = numbers.erase(it);" statement if you need to delete the element and simply incerement iterator in other case.

此行为是特定于实现的。为了保证迭代器的正确性，你应该使用“it = numbers.erase(it);” 如果您需要删除元素并在其他情况下简单地增加迭代器，则声明。

回答by Anurag

I came across same old issue and found below code more understandablewhich is in a way per above solutions.

我遇到了同样的老问题，发现下面的代码更容易理解，这在某种程度上是上述解决方案。

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();
}