【C++】vectorのeraseをループ内で使うと落ちる・消し残る原因とは？｜「たまたま動く」コードを実測して、erase-removeで安全に消す書き方を整理

【C++】vectorのeraseをループ内で使うと落ちる・消し残る原因とは？｜「たまたま動く」コードを実測して、erase-removeで安全に消す書き方を整理 C++

偶数だけを消す処理を書きました。要素は5個、結果は1 3 5。思ったとおりに動いたので、そのまま先へ進みました。ところが、あとでテスト用のデータを1個増やしたら、同じコードがいきなりアクセス違反で落ちたのです。コードは1文字も変えていません。

「eraseをループの中で呼ぶ」書き方は、たまたま動くことがあるぶん、気づくのが遅れます。そこで、同じ書き方を、データだけ変えて、DebugとReleaseの両方で動かして確かめました。落ちる場合、消え残る場合、速度が出ない場合のそれぞれについて、実際の出力を載せます。

検証は、Visual Studio 2022付属のMSVC(19.44、x64)で行いました。

vectorのeraseとは？

vector::eraseとは、

・vectorから要素を取り除く関数。消した位置より後ろの要素を、1つずつ前へ詰めてくれる

です。ここで押さえておきたいことが2つあります。

  • 消した位置のイテレータは、使えなくなる。位置が指していた要素は、もう別の要素に入れ替わっているため(イテレータが「無効になる」と言う)
  • 戻り値は「消した要素の、次の要素」を指すイテレータ。無効になったitの代わりに、これを使う

この2つを知らないまま、「消したあとも++itで進める」「iを進める」という普通のループを書くと、問題が起きます。

実験①：イテレータのループで、eraseする

まず、いちばん書きがちな形です。偶数のとき、erase(it)で消して、そのあとループの++itで進めます。

▼e1_iter.cpp(要素は 1〜6)
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 3, 4, 5, 6 };

    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (*it % 2 == 0)
        {
            v.erase(it);   // 偶数を消す
        }
    }

    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}

これをReleaseビルド(/O2)で動かしました。

終了コード: 0xC0000005 (アクセス違反)
出力: (なし)

何も表示されないまま、アクセス違反で落ちました。理由は、手で追うと分かります。

  1. 2を消すと、itは、詰められた後の3を指す。ここで++itをすると、4へ進む(3は、確認されずに飛ばされる)
  2. 4を消すと、itは5を指す。++itで6へ進む
  3. 6を消すと、itはend()(最後の1つ先)を指す。そこで++itをすると、end()をさらに追い越してしまう。it != end()は、もう永遠に偽にならず、確保した範囲の外を読みに行く

範囲の外を読んだ結果は、決まっていません(未定義動作)。今回の環境では、アクセス違反になりました。アクセス違反の読み方は、アクセス違反(0xC0000005)の記事で詳しく書いています。

【重要】データを1個減らすと、同じコードが「正しく」動く

では、要素を1, 2, 3, 4, 5の5個にします。コードは、1文字も変えません。

結果: 1 3 5

Releaseでは、1 3 5と、正しい答えが出ました。最後の5の次が、ちょうどend()で止まるので、追い越さずに済んだからです。

ところが、同じ5個のデータを、デバッグビルド(/Od /MDd)で動かすと、結果が変わります。

vectorのイテレータを消した後に進めたとき、デバッグビルドで出たDebug Assertion Failedのダイアログ
デバッグビルドで出たダイアログ(要素が1〜6の版。1〜5の版でも同じ文面だった)
Debug Assertion Failed!
Program: C:\blogtest\vec\e1_iter_dbg.exe
File: C:\Program Files\Microsoft Visual Studio\2022\Enterprise\VC\Tools\MSVC\14.44.35207\include\vector
Line: 78
Expression: can't increment invalidated vector iterator
For information on how your program can cause an assertion
failure, see the Visual C++ documentation on asserts.
(Press Retry to debug the application)

デバッグビルドの標準ライブラリは、イテレータが無効になったあとで進められたことを検出して、can't increment invalidated vector iterator(無効になったイテレータは進められない)と止めてくれます。上のダイアログは6個版で出たものですが、5個版でも、同じ文面で止まりました。

つまり、このコードは、Releaseでは結果が合っていても、規則違反です。「合っている」のは、たまたま、end()を追い越さなかっただけです。データが変わると、いつでも落ちます。

実験②：インデックスのループで、eraseする

イテレータが危ないなら、インデックスで書けば安全だろう、と考えて、書き換えました。

▼e2_index.cpp(要素は 1, 2, 4, 6, 7, 8)
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 4, 6, 7, 8 };

    for (size_t i = 0; i < v.size(); ++i)
    {
        if (v[i] % 2 == 0)
        {
            v.erase(v.begin() + i);   // 偶数を消す
        }
    }

    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}
結果: 1 4 7

落ちはしませんが、4が消えずに残りました。2を消すと、後ろの4が、2のいた位置(i)に詰められます。その直後に++iをするので、詰められた4は、一度も確認されません。DebugとReleaseのどちらでも、同じ1 4 7でした。

こちらは、未定義動作ではなく、ただの論理バグです。そのぶん、エラーも警告も出ません。連続した偶数がたまたま無いデータでは、正しく動いてしまいます。

直し方①：eraseの戻り値を受け取る

消したときは、戻り値をitに代入して、進めない。消さなかったときだけ、進めます。

▼e3_fixed.cpp
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 4, 6, 7, 8 };

    for (auto it = v.begin(); it != v.end(); )
    {
        if (*it % 2 == 0)
        {
            it = v.erase(it);   // 消したら、次の要素を指す戻り値を受け取る(++しない)
        }
        else
        {
            ++it;               // 消さなかったときだけ進める
        }
    }

    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}
結果: 1 7

1 7と、期待どおりでした。デバッグビルドでも、結果は同じで、ダイアログは出ませんでした。連続した偶数(2, 4, 6)も、きちんと消えています。

この書き方は、for文の3つ目の++itを、あえて空にしておくのが特徴です。範囲for(for (auto& x : v))は、イテレータを隠してしまうので、この直し方が使えません。要素を消すループには、範囲forを使わない、と覚えておくと安全です。

直し方②：erase-removeイディオムで、まとめて消す

もっとすっきりした書き方もあります。std::remove_ifで、残したい要素を前に詰めてから、eraseで余った後ろを、1回だけ消す方法です。

▼e4_remove.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 4, 6, 7, 8 };

    v.erase(std::remove_if(v.begin(), v.end(),
                           [](int x) { return x % 2 == 0; }),
            v.end());

    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}
結果: 1 7

同じ1 7になりました。1つ、勘違いしやすい点があります。remove_ifは、要素を消してはいません。実際に、remove_ifのあとで、vectorの大きさを表示してみました。

▼e7_size.cpp
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 4, 6, 7, 8 };

    auto newEnd = std::remove_if(v.begin(), v.end(),
                                 [](int x) { return x % 2 == 0; });
    std::cout << "remove_if のあと  size = " << v.size()
              << " , 残す範囲の長さ = " << (newEnd - v.begin()) << "\n";

    v.erase(newEnd, v.end());
    std::cout << "erase のあと      size = " << v.size() << "\n";
}
remove_if のあと  size = 6 , 残す範囲の長さ = 2
erase のあと      size = 2

remove_ifを呼んだあとも、sizeは6のままです。戻り値は「残す要素の終わりの位置」(長さ2)で、そのあとのeraseで、初めてsizeが2になりました。remove_ifだけ呼んでeraseを忘れるのは、よくある間違いです。

直し方③：C++20なら、erase_ifが1行で済む

C++20では、この2段階を1行で書けるstd::erase_ifが追加されています。

▼e5_erase_if.cpp(/std:c++20でビルド)
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 2, 4, 6, 7, 8 };

    std::erase_if(v, [](int x) { return x % 2 == 0; });   // C++20

    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}
結果: 1 7

同じ結果でした。C++20が使える環境なら、これが一番短くて、間違えにくい書き方です。

速度の差：消す要素が多いと、ループのeraseは遅くなる

「ループの中で、1つずつeraseするのは、遅いのでは？」という疑問も、確かめました。vectorの半分(偶数)を消すのに、2つの方法でかかる時間を、要素数を変えて測りました。

▼e6_bench.cpp
#include <algorithm>
#include <chrono>
#include <cstdio>
#include <vector>

static double ms(std::chrono::steady_clock::time_point a, std::chrono::steady_clock::time_point b)
{
    return std::chrono::duration<double, std::milli>(b - a).count();
}

int main()
{
    const int sizes[] = { 25000, 50000, 100000, 200000 };
    std::printf("%-8s %-20s %-20s\n", "要素数", "ループでerase(ms)", "remove_if(ms)");
    for (int n : sizes)
    {
        std::vector<int> a(n);
        for (int i = 0; i < n; ++i) a[i] = i;   // 半分が偶数
        std::vector<int> b = a;

        auto t0 = std::chrono::steady_clock::now();
        for (auto it = a.begin(); it != a.end(); )
        {
            if (*it % 2 == 0) it = a.erase(it); else ++it;
        }
        auto t1 = std::chrono::steady_clock::now();

        b.erase(std::remove_if(b.begin(), b.end(), [](int x) { return x % 2 == 0; }), b.end());
        auto t2 = std::chrono::steady_clock::now();

        std::printf("%-8d %-20.3f %-20.3f (残り %zu / %zu)\n", n, ms(t0, t1), ms(t1, t2), a.size(), b.size());
    }
}
要素数 ループでerase(ms) remove_if(ms)       
25000    10.411               0.009                (残り 12500 / 12500)
50000    45.468               0.019                (残り 25000 / 25000)
100000   189.684              0.038                (残り 50000 / 50000)
200000   771.905              0.096                (残り 100000 / 100000)
要素を半分消すのにかかった時間。ループの中でeraseする書き方と、remove_ifでまとめて消す書き方の比較
縦軸は対数。要素数が2倍になるたびに、ループerase側は約4倍に増えた
要素数ループでeraseremove_if + erase差
25,00010.4 ms0.009 ms約1,200倍
50,00045.5 ms0.019 ms約2,400倍
100,000189.7 ms0.038 ms約5,000倍
200,000771.9 ms0.096 ms約8,000倍
各要素数で1回ずつ計測。同じ環境でも、実行のたびに数値は少し変わる

ループでeraseする側は、要素数が2倍になるたびに、時間が約4倍になりました(10.4 → 45.5 → 189.7 → 771.9ミリ秒)。1回eraseするたびに、後ろの要素を全部1つずつ前へ詰めるからです。消す個数と、詰める量の両方が要素数に比例するので、全体が2乗で増えます。

一方、remove_ifは、1回なぞるだけで、要素を前へ詰め終えます。20万個でも、0.1ミリ秒を切りました。ゲームのように、1フレーム(60FPSなら約16.7ミリ秒)の中で、多数の弾や敵を消す場面では、この差が効いてきます。

vectorの要素を消すときの、よくある失敗例と対処法

①消したあとも、++itで進めてしまう

今回の実験①の原因です。消したときは、it = v.erase(it)で戻り値を受け取って、++しません。

②範囲forの中で、eraseする

範囲forの内部では、イテレータを++で進める処理が、自動で書かれています。消した直後にその++が走るので、①と同じ問題が、避けられません。範囲forは、読むだけのループに使います。

③remove_ifだけ呼んで、eraseを忘れる

実験で見たとおり、remove_ifだけでは、vectorの大きさは変わりません。v.erase(remove_if(...), v.end())の形で、必ずセットにします。C++20なら、std::erase_ifを使えば、忘れようがありません。

④「Releaseで動いたから」と、そのままにする

実験①のとおり、Releaseで正しい結果が出ても、規則違反のコードは、データが変わると落ちます。デバッグビルドで、一度は動かしておくと、can't increment invalidated vector iteratorのように、原因を教えてくれます。

注意点

  • eraseは、消した位置以降のイテレータを、無効にする。戻り値(次の要素)を使う
  • 消したときに++itすると、要素を飛ばし、最後はend()を追い越す。今回の環境ではアクセス違反になった
  • データによっては、Releaseで正しい結果が出る。それでも未定義動作なので、デバッグビルドでは止まる
  • インデックスのループで、消した直後に++iすると、連続した要素が消え残る(エラーは出ない)
  • remove_ifは、消さずに詰めるだけ。eraseと組み合わせる。C++20のstd::erase_ifなら1行
  • 今回の検証は、vector<int>とMSVC 19.44(x64)だけで行った。listやmapなどのeraseは試していない

この記事の要点

  • ループの中のeraseは、イテレータでも、インデックスでも、そのまま++すると壊れる
  • イテレータ版は、end()を追い越して、今回の環境ではアクセス違反になった。データ次第で、たまたま正しく動くこともある
  • インデックス版は、落ちないが、4のような要素が消え残った
  • 直し方は、戻り値を受け取るか、remove_ifとerase(C++20ならerase_if)
  • 20万要素の半分を消すのに、ループでeraseすると約770ミリ秒、remove_ifなら約0.1ミリ秒だった

「たまたま動く」コードほど、あとで原因を探すのに手間がかかります。要素を消すループを書くときは、eraseと++をセットで書かない、という癖をつけておくと、あとが楽になります。

あわせて読みたい