Search on the blog

2011年8月3日水曜日

知ってると便利なSTL(9) remove, erase

remove()とerase()は紛らわしい。
この2つの関数がやることは全然違う。

remove()は、"取り除く"という意味なので、指定した値を(意味のある)区間から取り除く。
erase()は、"消去する"という意味なので、指定した範囲のメモリを消去する。

 まず、remove()について詳しくみていく。以下の例を考える。
int x[] = {1,2,3,4,3,6};

int main() {
int sz = SIZE(x);

remove(x, x+sz, 3);

for (int i = 0; i < sz; i++)
cout << x[i] << endl;
}
この例では、{1, 2, 3, 4, 3, 6}から、3を取り除く。実際にやるのは、x[0]から、x + szまでを走査して、3じゃない値だけをx[0], x[1], ..にコピーし直している。
よって、表示されるのは、{1, 2, 4, 6, 3, 6}となる。

参考までに、この部分のソース(gccの実装)を抜粋すると、
 template<typename _InputIterator, typename _OutputIterator, typename _Tp>
_OutputIterator
remove_copy(_InputIterator __first, _InputIterator __last,
_OutputIterator __result, const _Tp& __value)
{
for ( ; __first != __last; ++__first)
if (!(*__first == __value))
{
*__result = *__first;
++__result;
}
return __result;
}
という感じ。

remove()は、不要な値を除いてコピーをし終えた位置のイテレーターを返すので、上記の例で、{1,2,4,6}までを表示させたければ、
int x[] = {1,2,3,4,3,6};

int main() {
int sz = SIZE(x);

int *p = x;
int *q = remove(x, x+sz, 3);

while (p != q)
cout << *p++ << endl;
}
と書けばよい。vectorについても同様なので、

vector<int> x;

int main() {
x.push_back(1);
x.push_back(2);
x.push_back(3);
x.push_back(4);
x.push_back(3);
x.push_back(6);

vector<int>::iterator p = x.begin();
vector<int>::iterator q = remove(x.begin(), x.end(), 3);

while (p != q)
cout << *p++ << endl;
}
と書くと、remove後のコンテナ内の値を表示させることができる。この時点では、コンテナのサイズや終端イテレーターの位置は更新されていないことに注意。x.end()は、x[5]の次の位置を指している。

 実際に、メモリ上から値を削除して、コンテナのサイズや終端イテレーターの位置を更新したい場合は、erase()を使う。

erase()には、削除したいイテレーターの位置、またはその範囲を指定することができる。
vector<int> x;
int main() {
// 1 2 3 4 3 6
x.push_back(1);
x.push_back(2);
x.push_back(3);
x.push_back(4);
x.push_back(3);
x.push_back(6);

x.erase(x.begin()+2); // erase x[2]
for (int i = 0; i < (int)x.size(); i++)
cout << x[i] << endl; // 1 2 4 3 6

x.erase(x.begin()+1, x.begin()+4); // erase the elements [x[1], x[4])
for (int i = 0; i < (int)x.size(); i++)
cout << x[i] << endl; // 1 6
}
という具合。
以下のように、remove()とerase()を併用すると、値を取り除いて範囲外に出すのと、メモリからの消去がまとめて出来る。

int main() {
vector<int> x;

x.push_back(1);
x.push_back(2);
x.push_back(3);
x.push_back(4);
x.push_back(3);
x.push_back(6);

x.erase(remove(x.begin(), x.end(), 3), x.end());
// 1 2 4 6
for (int i = 0; i < (int)x.size(); i++)
cout << x[i] << endl;

return 0;
}
また、文字列から指定した文字を削除する関数は、以下のように書くことができる。
void removeAll(string &s, char t) {
s.erase(remove(s.begin(), s.end(), t), s.end());
}

0 件のコメント:

コメントを投稿