改善版 reverse_iterator 使用中のerase()の仕方

2010年5月の記事にコメントいただいた

reverse_iterator使用時のerase()の仕方 - 自習室

この記事に、メモリ衝突が起きるよ、というコメントをいただきました。

自分がこの記事を書く際に使ったコードが見当たらなかったので、改めてそれらしく書いてみました。確かに、イテレータの進め方など結構気を遣わないと、直ぐ見つからないところを叩いたりしてしまうクソコードでした。

不理解だったところ

reverse_iterator が、通常の iterator のアダプター(特定の目的のためにラップして使いやすくする)オブジェクトだ、ということを理解しておりませんでした。

このページの一番上の図と説明が分かりやすい。

std::reverse_iterator - cppreference.com

Reverse iterator stores an iterator to the next element than the one it actually refers to
リバースイテレータは、そのリバースイテレータが指している要素の(正順での)一個先を指している(正順)イテレータを保持している

と書いてある。関係性を式で表すとこうなる

&*r == &*(i-1)

そうすると確かに、erase のために、現在見ている reverse_iterator に対応する iterator を取得しようと思ったら、 base() で対応するイテレータを取得した後、一個戻す、が仕様上正しい操作だ、という気がしてきます。

hogelist.erase(--(hoge_ri.base()));

ここまでの内容を図解したのが下の図。

標準iteratorとしてerase()したあと、リバースイテレータはどこを指しているのか？

この点は自分もいろいろ混乱したので、図解します。

上でも書いたように、リバースイテレータは通常のイテレータのアダプタというかラッパなので、本体であるイテレータが指すものから上記関係式で導き出される対象を指しています。erase()した結果、通常イテレータの場所は変化していませんが、それに対応するリバースイテレータが、リスト上では一個前に進んだことになります。

従って、ri++ で(逆向きに)進んでいたとしたら、erase() した時には、ri は自動的に次の要素を指しているので、ri++ は不要、と言うことになります。

サンプルコード

charとint をメンバに持つクラスHogeのlistを作り、その中からユーザのキーボード入力で指定されたintの値を持つhogeを一個ずつ消していく、という内容です。このサンプルでは、特にリバースである必然性はありません。

そもそも2010年の元記事でリバースイテレータを使った理由は、OpenGLで描画をしながら、不要になったオブジェクトを消す、と言う操作を、1回の反復操作で行いたい、というものでした。OpenGLでは後から描いた物が先に描いた物の手前に上書きされるので、リストの作り方次第では、逆順に描画をコールしたいケースが発生します。

全文はこちら

リバースイテレータでリストを回しながら、 時折 erase を行う

大事なとこだけ抜粋します

while(hoge_ri != hogelist.rend())
        {
            if(hoge_ri->check(value)) //当該Hogeインスタンスが value と同値のメンバを持っていたら
            {
                hogelist.erase(--(hoge_ri.base())); // 消す(と同時に進んでいる)
                cout << "###erase### " << value << endl;
            }
            else
            {
                hoge_ri->print(); // 持ってなかったら標準出力して
                hoge_ri++;  //進める
            }
        }

先述の注意点の通り、消したときは、hoge_ri を ++ しておりません。

最後に

そもそもリバースイテレータを必要としない構造で書いた方が、可読性も上がるし良いよなーと思いました。