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

remove()とerase()は紛らわしい。

この２つの関数がやることは全然違う。

remove()は、"取り除く"という意味なので、指定した値を（意味のある）区間から取り除く。

erase()は、"消去する"という意味なので、指定した範囲のメモリを消去する。

　まず、remove()について詳しくみていく。以下の例を考える。

view plainprint?

1. int x[] = {1,2,3,4,3,6};  
2.   
3. int main() {  
4.   int sz = SIZE(x);  
5.   
6.   remove(x, x+sz, 3);  
7.   
8.   for (int i = 0; i < sz; i++)  
9.     cout << x[i] << endl;  
10. }  

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の実装)を抜粋すると、

view plainprint?

1. template<typename _InputIterator, typename _OutputIterator, typename _Tp>  
2.   _OutputIterator  
3.   remove_copy(_InputIterator __first, _InputIterator __last,  
4.        _OutputIterator __result, const _Tp& __value)  
5.   {  
6.     for ( ; __first != __last; ++__first)  
7.    if (!(*__first == __value))  
8.      {  
9.        *__result = *__first;  
10.        ++__result;  
11.      }  
12.     return __result;  
13.   }  

 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}までを表示させたければ、

view plainprint?

1. int x[] = {1,2,3,4,3,6};  
2.   
3. int main() {  
4.   int sz = SIZE(x);  
5.   
6.   int *p = x;  
7.   int *q = remove(x, x+sz, 3);  
8.   
9.   while (p != q)  
10.     cout << *p++ << endl;  
11. }  

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についても同様なので、

view plainprint?

1. vector<int> x;  
2.   
3. int main() {  
4.   x.push_back(1);  
5.   x.push_back(2);  
6.   x.push_back(3);  
7.   x.push_back(4);  
8.   x.push_back(3);  
9.   x.push_back(6);  
10.   
11.   vector<int>::iterator p = x.begin();  
12.   vector<int>::iterator q = remove(x.begin(), x.end(), 3);  
13.   
14.   while (p != q)  
15.     cout << *p++ << endl;  
16. }  

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()には、削除したいイテレーターの位置、またはその範囲を指定することができる。

view plainprint?

1. vector<int> x;  
2. int main() {  
3.   // 1 2 3 4 3 6  
4.   x.push_back(1);  
5.   x.push_back(2);  
6.   x.push_back(3);  
7.   x.push_back(4);  
8.   x.push_back(3);  
9.   x.push_back(6);  
10.   
11.   x.erase(x.begin()+2);    // erase x[2]  
12.   for (int i = 0; i < (int)x.size(); i++)  
13.     cout << x[i] << endl;     // 1 2 4 3 6  
14.   
15.   x.erase(x.begin()+1, x.begin()+4); // erase the elements [x[1], x[4])  
16.   for (int i = 0; i < (int)x.size(); i++)  
17.     cout << x[i] << endl;     // 1 6  
18. }  

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()を併用すると、値を取り除いて範囲外に出すのと、メモリからの消去がまとめて出来る。

view plainprint?

1. int main() {  
2.   vector<int> x;  
3.   
4.   x.push_back(1);  
5.   x.push_back(2);  
6.   x.push_back(3);  
7.   x.push_back(4);  
8.   x.push_back(3);  
9.   x.push_back(6);  
10.   
11.   x.erase(remove(x.begin(), x.end(), 3), x.end());  
12.   // 1 2 4 6  
13.   for (int i = 0; i < (int)x.size(); i++)  
14.     cout << x[i] << endl;  
15.   
16.   return 0;  
17. }  

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;
}

また、文字列から指定した文字を削除する関数は、以下のように書くことができる。

view plainprint?

1. void removeAll(string &s, char t) {  
2.   s.erase(remove(s.begin(), s.end(), t), s.end());  
3. }  

void removeAll(string &s, char t) {
  s.erase(remove(s.begin(), s.end(), t), s.end());
}