迭代时从std :: set删除元素 [英] Deleting elements from std::set while iterating

问题描述

我需要遍历一组并删除符合预定义条件的元素.

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

起初，我认为在迭代过程中从集合中删除一个元素会使迭代器无效，并且for循环中的增量将具有未定义的行为.即使我执行了此测试代码，但一切顺利，而且我无法解释原因.

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.

我的问题: 这是标准集的已定义行为还是此实现特定?顺便说一下，我正在Ubuntu 10.04(32位版本)上使用gcc 4.3.3.

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.

谢谢！

建议的解决方案:

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

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

首选解决方案

我想到了一个对我来说似乎更优雅的解决方案，即使它完全一样.

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.

推荐答案

这取决于实现:

标准23.1.2.8:

Standard 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.

2015.10.27更新: C ++ 11解决了该缺陷. iterator erase (const_iterator position);将迭代器返回到最后删除的元素之后的元素(如果删除了最后一个元素，则返回set::end).所以C ++ 11样式是:

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:

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

这篇关于迭代时从std :: set删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！