179

我需要检查一组并删除符合预定义标准的元素。

这是我写的测试代码:

#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 循环中的增量将具有未定义的行为。尽管如此,我执行了这个测试代码并且一切顺利,我无法解释为什么。

我的问题: 这是标准集的定义行为还是此实现特定?顺便说一句,我在 ubuntu 10.04(32 位版本)上使用 gcc 4.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 内有多个测试条件,则每个测试条件都必须递增迭代器。我更喜欢这段代码,因为迭代器只在一个地方递增,使代码不易出错且更具可读性。

4

8 回答 8

211

这取决于实现:

标准 23.1.2.8:

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

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

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

请注意,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;
    }
}
于 2010-05-20T14:13:56.913 回答
22

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

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;                                                               
    }                                                                       
} 
于 2010-05-20T14:35:05.043 回答
8

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

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

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

于 2010-05-20T14:15:38.757 回答
5

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

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

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

于 2019-01-10T19:46:10.780 回答
2

只是警告一下,在双端队列容器的情况下,所有检查双端队列迭代器是否与 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;
    }
  }
}

输出:

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

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

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;
      }
    }
  }
}
于 2015-08-23T02:32:24.757 回答
1

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

于 2010-05-20T14:09:49.603 回答
1

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

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

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

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_bullets.end() 的对象可以被擦除,因为它们占用内存,但包含垃圾,因此在该范围内调用 'erase' 方法。

于 2019-01-10T19:24:48.230 回答
0

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

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();
}
于 2018-07-02T08:03:59.023 回答