vectorから重複要素を削除する

これを解いているときに「vectorから重複を削除する方法忘れちゃった～」となったので復習した。
atcoder.jp

方法1 : sort -> unique + erase

• 重複要素を線形探索するために sort しておく。
• unique で隣接する重複要素を除いた要素を先頭に集める。
• unique の戻り値は重複なし範囲の末尾の次を指すイテレータなので、そこから終端まで erase すればよい。

方法2 : vector -> set -> vector

• set は重複を許さない順序付き集合なので、変換すると重複要素が消える。

https://wandbox.org/permlink/2p17qBxT5AtVkymO

コード例

#include <algorithm>  // unique
#include <iostream>   // cin, cout, endl
#include <set>        // set
#include <vector>     // vector, erase

using namespace std;

void printVec(vector<int> v) {
  int len = v.size();
  for (int i = 0; i < len; i++) {
    cout << v[i];
    if (i < len - 1) {
      cout << ' ';
    } else {
      cout << endl;
    }
  }
}

int main() {
  vector<int> vec = {1, 2, 3, 6, 2, 6, 8, 0, 10, 11, 10, 10, 12, 2, 1};
  cout << "Initial                 : ";
  printVec(vec);

  auto vec1 = vec;
  auto vec2 = vec;

  // sort + unique + erase
  sort(vec1.begin(), vec1.end());
  vec1.erase(unique(vec1.begin(), vec1.end()), vec1.end());
  cout << "sort -> unique + erase  : ";
  printVec(vec1);

  // vector -> set -> vector
  set<int> vec_to_set(vec2.begin(), vec2.end());
  vector<int> set_to_vec(vec_to_set.begin(), vec_to_set.end());
  cout << "vector -> set -> vector : ";
  printVec(set_to_vec);

  return 0;
}

Initial                 : 1 2 3 6 2 6 8 0 10 11 10 10 12 2 1
sort -> unique + erase  : 0 1 2 3 6 8 10 11 12
vector -> set -> vector : 0 1 2 3 6 8 10 11 12