代码之家 › 专栏 › 技术社区 › pedromanoel

迭代时从stl集删除元素

set iterator stl c++

124

pedromanoel · 技术社区 · 14 年前

我需要检查一个集合并删除符合预定义条件的元素。

这是我写的测试代码:

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

我的问题: 这是为标准集定义的行为还是具体的实现?顺便说一下,我在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中有多个测试条件,则每个条件都必须增加迭代器。我更喜欢这段代码,因为迭代器是递增的 只有一个地方 使代码不易出错,更具可读性。

8 回复 | 直到 5 年前

154

Verhagen 9 年前

这取决于实现:

标准23.1.2.8:

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

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

for (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 (it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}

Matt 14 年前

如果你通过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;                                                               
    }                                                                       
}

Tyler McHenry 14 年前

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

如果某个东西执行时没有崩溃,并且行为如您所期望的那样,那就是不证明它不是未定义的行为。它所证明的是,它的行为恰好与在特定操作系统上使用特定编译器编译后的特定运行所观察到的一样。

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

McKryak 9 年前

警告一下,对于deque容器,检查deque迭代器是否与numbers.end()相等的所有解决方案都可能在GCC4.8.4上失败。也就是说,删除deque元素通常会使指向数字的指针失效。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;
      }
    }
  }
}

Vitaly Bogdanov 14 年前

这种行为是特定于实现的。为了保证迭代器的正确性,如果需要删除元素,则应使用“it=numbers.erase(it);”语句,而在其他情况下,只需使用increment迭代器。

Anurag 6 年前

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

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

John Behm 5 年前

我想用stl方法 remove_if '来自可以帮助防止在尝试删除由迭代器包装的对象时出现一些奇怪的问题。

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

假设我们有某种容器,比如向量或一个名为m_项目符号的列表:

Bullet::Ptr is a shared_pr<Bullet>

’ it '是迭代器' 移除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());

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

Marshall Clow 5 年前

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

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

这对 vector , set , deque 等。见 cppReference 更多信息。