📴

std::vectorの要素のうち特定の条件に合致するものを削除する

に公開
C++
cpp20
tech

C++ でstd::vectorのようなコンテナから特定の条件を果たす要素を削除したい場合はどうしますか？
例えば、数字が入っているstd::vectorからすべての偶数の要素を削除したい時はどうしますか？
まずはforループを使うと思います。

std::vector<int> numbers{3, 20, 14, 2, 5, 90};

for (int i = 0; i < numbers.size(); ++i)
{
    if (numbers[i] % 2 == 0)
    {
        numbers.erase(numbers.begin() + i);
    }
}

for (const auto number : numbers)
{
    std::cout << number << std::endl;
}

でもこれだと、{3, 14, 5}が残ってしまいます。なんで？
i == 1の時に20を削除すると、numbersの構造が変わって{3, 14, 2, 5, 90}になり、次i == 2になると、14を飛ばして2をチェックすることになります。

ここでたまに見かけるのは、以下の小技です。

for (int i = numbers.size(); i >= 0; --i)
{
    if (numbers[i] % 2 == 0)
    {
        numbers.erase(numbers.begin() + i);
    }
}

後ろから削除していくと、要素を飛ばしたりするリスクはないです。これが一番簡単で分かりやすいという人もいると思います。
因みにイテレーターを使うとどうなりますか？

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

これだと、プログラムが SIGSEGV でクラッシュします。なぜかとうと、eraseをコールした後は、削除された要素を指していたitはもう使えなくなってしまいます。なのに、++itで次のイテレーターに移ろうとすると、クラッシュします。
なので、イテレーターを使う時は、以下のように削除しない場合は++itで次の要素に移って、削除する場合はeraseの戻り値である削除後の次のイテレーターをitに代入した方がいいです。これだと、クラッシュせずに済みます。

// for文中の++itは無くなってます
for (auto it = numbers.begin(); it != numbers.end();)
{
    if (*it % 2 == 0)
    {
        it = numbers.erase(it);
    }
    else
    {
        ++it;
    }
}

でも上記のようなリスクがあるため、やはり基本的にforループでstd::vectorを回す時は、そのstd::vectorから要素を削除したり追加したりしない方がいいです。
ここで私のお勧めは、forループを使わずにErase-remove idiomという名のeraseとstd::remove_ifのコンビネーション技を使うことです。

numbers.erase( // 要素の削除にはerase()が必要
    std::remove_if(
        numbers.begin(), numbers.end(),
        [](const auto& number) { return number % 2 == 0; }
    ),
    numbers.end()
);

C++20 からはこの2つの動作を一気にやってくれるstd::erase_ifという関数が追加されて、ようやく以下のように1つの関数でできるようになりました。

std::erase_if (numbers, [](auto const& number) { return number % 2 == 0; });

なんで最初からこういう関数を用意してくれなかったのでしょうね・・・。

|cpp記事一覧へのリンク|

Discussion