迭代时从STL集中删除元素

Question

我需要浏览一个集合并删除符合预定义条件的元素.

这是我写的测试代码:

#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集的定义行为还是特定于此实现？顺便说一句,我在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内有多个测试条件,则每个测试条件都必须递增迭代器.我更喜欢这个代码,因为迭代器只在一个地方递增,使得代码不易出错且更易读.

Answer 1

这取决于实现:

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

Answer 2

如果你通过valgrind运行你的程序,你会看到一堆读错误.换句话说,是的,迭代器正在失效,但你在你的例子中变得幸运(或者真的很不幸,因为你没有看到未定义行为的负面影响).对此的一个解决方案是创建临时迭代器,增加临时值,删除目标迭代器,然后将目标设置为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;                                                               
    }                                                                       
} 

Answer 3

你误解了"未定义的行为"的含义.未定义的行为并不意味着"如果您这样做,您的程序将崩溃或产生意外结果." 这意味着"如果你这样做,你的程序可能会崩溃或产生意想不到的结果",或者做任何其他事情,具体取决于你的编译器,你的操作系统,月亮的阶段等等.

如果某些事情在没有崩溃的情况下执行并且按照您的预期行为,那么这并不能证明它不是未定义的行为.所有证明的是,在特定操作系统上使用特定编译器进行编译之后,其行为恰好与特定运行一样.

从集合中删除元素会使迭代器无效,从而使删除的元素无效.使用无效的迭代器是未定义的行为.事实恰恰相反,观察到的行为就是你在这个特定情况下的意图; 这并不意味着代码是正确的.

Answer 4

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

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

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