等値と等価とunique

C++
等値(equality)
a == b
等価(equivalence)
!(a < b) && !(b < a)

任意の要素に対してこれらの結果が一致する場合、単にsetに入れていけばユニークな集合ができあがるが、異なる場合は std::unique を使う。

ただし、std::unique を使うには、等値である可能性があるものは必ずソートした状態で隣接していなければならない。

典型的なものとしては、doubleの誤差を考慮する場合がある。

struct Hoge {
  double a;
  bool operator<(const Hoge &x) const {
    return a < x.a;
  }
  bool operator==(const Hoge &x) const {
    return abs(a - x.a) < EPS;
  }
};

std::unique の基本的な使い方

  • sort する
  • unique する
  • erase する
vector<Hoge> v;
vector<Hoge>::iterator it;
...
sort(v.begin(), v.end());
it = unique(v.begin(), v.end());
cout << "unique numbers: " << distance(v.begin(), it) << endl;
v.erase(it, v.end());