C++: 双方向リスト (list) の要素探索と削除操作時に注意すること
はじめに
リスト (list) 型のデータの中から目的のデータを探し、そのデータを削除操作する場合に注意が必要な場合があります。その注意点についてまとめています。
基本知識: データの線形探索
listクラスはfindメソッドを提供していないため、データを線形探索するためには以下の2通りのやり方があります。
- イテレータを利用する
-
std::find関数を利用する
イテレータを利用した線形探索
リストのbegin, endのメンバー関数を利用してイテレータをインクリメントしながら目的のデータを探す手法です。
std::list<int> lst;
lst.push_back(1);
lst.push_back(2);
lst.push_back(3);
int target = 1;
for (auto itr = lst.begin(); itr != lst.end(); itr++) {
if (*itr == target) {
std::cout << *itr << std::endl;
1
std::find関数を利用した線形探索
std::findを利用して上記と同様のことが可能です。
std::list<int> lst;
lst.push_back(1);
lst.push_back(2);
lst.push_back(3);
auto itr = std::find(lst.begin(), lst.end(), 1);
std::cout << *itr << std::endl;
1
注意するポイント
その1: データを削除する場合
イテレータを利用して逐次的にデータを探索しつつ、目的のデータを削除するようなケースにおいて注意が必要です。例えば、以下のように目的のデータをeraseメソッドで削除した後も継続してイテレータをインクリメントする場合、erase実行後のitrは削除された後のデータであるため不正な場所を示してしまい、思わないバグにつながる可能性があります（環境によっては問題なく動作する？）。
int target = 1;
for (auto itr = lst.begin(); itr != lst.end(); itr++) {
if (*itr == target) {
lst.erase(itr);
}
}
そのため、eraseをする場合には以下のようにeraseメソッドがリターンする次の要素を示したイテレータを利用する必要があります。
int target = 1;
for (auto itr = lst.begin(); itr != lst.end(); ) {
if (*itr == target) {
// erase は現在のイテレータの次の要素のイテレータを返す
itr = lst.erase(itr);
} else {
// erase しない場合のみインクリメント
itr++;
}
}
なお、本内容はリスト以外のコンテナを利用する場合においても同様のため、同じように気をつける必要があります。
その2: リバースイテレータを利用して逆順で探索してデータを削除する場合
例えば、昇順に並んでいるデータを逆順（大きい順）で後ろから探索し、目的のデータを削除する場合に通常のイテレータとな少し異なる操作をする必要があります。
通常のイテレータのイメージでreverse iteratorを使うとコンパイルエラーになります。eraseメソッドの仕様上、reverse_iterator型の変数を引数に渡すことが出来ません。つまりこのままでは無理ということです。
std::list<int> lst;
lst.push_back(1);
lst.push_back(2);
lst.push_back(3);
int target = 1;
// begin / end の代わりに rbegin / rend を利用する
for (auto itr = lst.rbegin(); itr != lst.rend(); ) {
if (*itr == target) {
itr = lst.erase(itr); // ここでコンパイルエラー
} else {
itr++;
}
}
a.cc:40:17: error: no matching member function for call to 'erase'
itr = lst.erase(itr);
~~~~^~~~~
/usr/include/c++/v1/list:1061:14: note: candidate function not viable: no known conversion from 'std::reverse_iterator<std::__list_iterator<int, void *>>' to 'std::list<int>::const_iterator' (aka '__list_const_iterator<int, void *>') for 1st argument
iterator erase(const_iterator __p);
^
/usr/include/c++/v1/list:1062:14: note: candidate function not viable: requires 2 arguments, but 1 was provided
iterator erase(const_iterator __f, const_iterator __l);
^
a.cc:40:11: error: no viable overloaded '='
itr = lst.erase(itr);
~~~ ^ ~~~~~~~~~~~~~~
/usr/include/c++/v1/iterator:775:27: note: candidate template ignored: could not match 'reverse_iterator' against '__list_iterator'
reverse_iterator& operator=(const reverse_iterator<_Up>& __u)
reverse_iterator を iterator に変換する
ではどうするか、reverse_iterator型を通常のiterator型に変換します。baseメソッドを利用することで型自体はiteratorに変換が可能ですが、以下の図のようにイテレータの位置関係が異なるため、変換後に位置を一つだけ前にずらす必要があります。
--(itr.base())
std::list<int> lst;
lst.push_back(1);
lst.push_back(2);
lst.push_back(3);
int target = 1;
for (auto itr = lst.rbegin(); itr != lst.rend(); ) {
if (*itr == target) {
lst.erase(--(itr.base()));
// ここで iterator から reverse_iterator に変換する方法は？
} else {
itr++;
}
}
Discussion