[C++] listの中間要素の削除はvectorより遅い場合がある、という勘違い

※割と駄文です。

やはり中間要素の挿入や削除をしたい場合はlistを使った方が無難らしい

そりゃそうだろう、という声が聞こえてきそうですが、そもそものきっかけはとある海外のベンチマークテストの記事でした。

• C++ benchmark – std::vector VS std::list VS std::deque

この記事の中に「8バイトのデータを一定数格納した各コンテナから要素を1000個Random Removeしたときの速度（ms）差」として以下のグラフが記載されています。

このグラフを鵜呑みにして、中間要素の削除が必要な場面でもdequeやvectorを使用していたのですが、最近listじゃないと遅くなるパターンに遭遇しました。

Submission #136682542 - Codeforces
（ソースが汚くてすいません…）

長いので一部抜粋＆見やすくなるように編集します。

// 問題のlist
std::list<int> remove_list(a.begin(), a.end());
    
for (auto it = remove_list.begin(); it != remove_list.end();) {
    if (*it == i)
        remove_list.erase(it++);     // ここで中間要素の削除を行なっている
    else ++it;
}

上記のコードは、listをdequeに変更すると実行時間超過でジャッジを通らなくなります。

元記事の本文を読み直してみるとわかるのですが、「挿入、削除する箇所の選択はO(n)の線型探索を用いて決めている」と書いてあり、1回の挿入or削除ごとに全要素間のイテレーションを行ってテストしていることがわかります。
listのイテレーションはdequeに比べてやや遅いことが記載されている¹ので、上記のグラフは挿入・削除回数分のイテレーションの速度差を加味した上でのベンチマークである、ということになります。
前述のコード例では1回しかイテレーションを行っていません。実際にこの条件でdequeの3倍以上の速度が出ているので²、グラフをそのまま適用して「listの中間要素の削除は8バイト以下だとdequeより遅い」とするのは誤りである、と考えた方が良さそうです。

まとめ

こう言う記事は本文までちゃんと読まないとダメですね。
今読み返してみたらコメント欄で指摘されてるし…

1. 実際にlistのイテレーションはvectorやdequeに比べて多少遅いです。といっても実用にならないほどではないですが。 ↩

2. Codeforcesのこの問題における実行時間制限は1秒です。 ↩