1. ホーム
  2. c++

[解決済み] イテレート中にstd::setから要素を削除する

2022-04-21 15:41:35

質問

私はセットを通過して、事前に定義された基準を満たす要素を削除する必要があります。

これは、私が書いたテストコードです。

#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(32bit版)で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;
    }
}

編集:PREFERED SOLUTION(優先的解決策

私は、まったく同じことをするにもかかわらず、よりエレガントに思える解決策を思いつきました。

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の中にいくつかのテスト条件がある場合、その一つ一つがイテレータをインクリメントしなければなりません。私はこのコードの方が、イテレータがインクリメントされるので好きです。 一箇所だけ そのため、エラーが起こりにくく、読みやすいコードになっています。

解決方法は?

これは実装に依存します。

規格23.1.2.8。

挿入メンバは、イテレータ及びコンテナへの参照の有効性に影響を及ぼしてはならず、消去メンバは、消去された要素へのイテレータ及び参照のみを無効としなければならない。

たぶん、これを試してみてください -- これは標準に準拠しています。

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

it++はpostfixなので、消去するために古い位置を渡しますが、演算子の関係でまず新しい位置にジャンプすることに注意してください。

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