iteratorの再利用について

質問

コンテナの内容を変えた後に内容を変える前のiteratorを使用することはできないと聞きました。ので、連続して何らかのコンテナ内のデータを変更しつつ、探索する場合にも、iteratorは最初から探索を始めないといけないと思っています。
例えば以下のように

#include <stdio.h>
#include <list>

struct data
{
int value;
data(int value)
{this->value = value;}
};

typedef std::list<data> DataList;
typedef std::list<data>::iterator DataIterator;

bool EraseValue(DataList*dataList, int value)
{
DataIterator iterator= dataList->begin();
while(iterator != dataList->end())
{
if(iterator->value == value)
{
dataList->erase(iterator);
return true;
}
iterator++;
}
return false;
}

int main()
{
//データを入れる
DataList dataList;
for(int i=0;i<10; i++)
dataList.push_back(data(i));

//指定のデータを探し、消す
int Value[] = {4,5,7};
EraseValue(&dataList, Value[0]);
EraseValue(&dataList, Value[1]);
EraseValue(&dataList, Value[2]);

//結果表示
DataIterator iterator = dataList.begin();
while(iterator != dataList.end())
{
printf("%d\n",iterator->value);
iterator++;
}

return 0;
}

ここで、新しい値の探索を始めるたびに、最初から探索をはじめる部分が無駄であると思っています。探索するデータは、上の例のように、必ず前回探したものの後にあることはわかっているとして、これより効率のよい方法はないでしょうか？自分の中での理想は、削除したiteratorの直前に使った(削除されていない)iteratorの位置から探索を始めるのがいい思っているのですが、これはどうやらできないこと(やってはいけないこと？)の様です。
コンテナをstd::listに限定した場合でも構いません。
ご教授よろしくお願いします。

回答No.2

i-kujou · ベストアンサー

http://ff.pekori.to/wiki/index.php?C%2B%2B%2Fiterator

ここに要素の削除によるイテレーターの無効化について情報が乗っています。
std::listに限って言えば要素が削除された場合、無効になるイテレーターは削除対象の要素を示していたイテレーターのみです。

> 必ず前回探したものの後にあることはわかっている

場合ならば以下のようにしても良いと思います。

bool EraseValue(DataList*dataList, int* value, size_t erasenum)
{
DataIterator iterator= dataList->begin();
while(iterator != dataList->end() && erasenum > 0)
{
if(iterator->value == value)
{
DataIterator tmp = iterator; // 削除対象を見つけたのでイテレーターを保存
++iterator; // 次のイテレーターに移動
dataList->erase(tmp); // 削除。この時点でtmpは無効だが、iteratorは利用可能

++value; // 次の削除対象に移す
--erasenum; // 削除数を減らす
}
else
{
iterator++;
}
}
return false;
}

お礼

迅速な返答ありがとうございます。
疑問が完全に氷解しました。ありがとうございます。
自分の環境では、直前のものを使うのに成功していたのですが、"たまたま"かどうか裏が取れなかったので、使用していませんでした。

回答No.1

sakusaker7

コンテナから任意の要素を消したいという話なら、
remove_ifを使えばいいと思うのですが何か問題があるのでしょうか?

STL Algorithm詳解 - 置き換え、削除
http://www.wakhok.ac.jp/~sumi/stl/manual/remove.html

お礼

返答ありがとうございます。
当方、まだまだ未熟で、STLのalgorithmなどは、一度も使ったことがありません。こんな便利なことができるのですね。
是非試してみます。