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

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

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

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