[tips][cpp] std:: unique

std:: unique

cppで配列vから重複を許さないソート済み配列vを生成したい場合は、この二行で良い。

#define all(a) a.begin(), a.end()とする。

1. sort(all(v));
2. v.erase(unique(all(v)), v.end());

詳説

cpp tipsです。標準ライブラリの気になったポイントをメモします。
関数概要は"イテレータ範囲 [first, last) から重複した要素を除ける"です。

• 隣り合った要素のうち重複するもののみ取り除いた配列を生成する
• 生成した配列を元の配列に対して先頭から順番に上書きする
• 先頭に集められた重複なし範囲の末尾の次を指すイテレータが返る

このため、uniqueが返した戻り値のイテレータを使用して、重複したままの要素を削除する必要があります。auto res = unique()とすると、区間$[res, end())$が重複したままの配列がそのままなので、erase()で取り除きます。

全ての重複要素を取り除きたい場合は、sortしてsortしたものに対してこの処理を行えば良いです。

例えばこの処理。

#include <iostream>
#include <vector>
#include <algorithm>
#define all(a) a.begin(), a.end()
void print(const char *tag, const std::vector<int> &v) {
  std::cout << tag << " : ";
  bool first = true;
  for (int x : v) {
    if (first) {
      first = false;
    } else {
      std::cout << ',';
    }
    std::cout << x;
  }
  std::cout << std::endl;
}

int main(){
    std::vector<int> v = {2, 5, 3, 3, 1, 2, 4, 2, 1, 1, 4, 4, 3, 3, 3};
    decltype(v)::iterator result = std::unique(v.begin(), v.end());
    print("unsorted unique; before remove", v);
}

とすると、隣り合った要素が重複していた場合、それを取り除く処理を行なった数値たちがまず先頭から順番に配置され、残りはそのままになります。

unsorted unique; before remove : 2,5,3,1,2,4,2,1,4,3,4,4,3,3,3

• 重複したもののうち、隣り合うもののみが取り除かれ先頭に配置される
• 残りはそのままである

ことがわかります。

次の処理で全ての重複要素を取り除きます。

    std::vector<int> v = {2, 5, 3, 3, 1, 2, 4, 2, 1, 1, 4, 4, 3, 3, 3};
    std::sort(all(v));
    decltype(v)::iterator result = std::unique(v.begin(), v.end());

    // 不要になった要素を削除
    v.erase(result, v.end());

できました。

sorted unique : 1,2,3,4,5

参考

https://cpprefjp.github.io/reference/algorithm/unique.html
https://cpprefjp.github.io/reference/vector/vector/erase.html