std::ranges:: unique

このページで説明されている関数ライクなエンティティは、 アルゴリズム関数オブジェクト （非公式には niebloids として知られる）です。すなわち：

• 明示的なテンプレート引数リストは、いずれかを呼び出す際に指定できません。
• いずれも 実引数依存の名前探索 では可視になりません。
• いずれかが関数呼び出し演算子の左側の名前として 通常の非修飾名前探索 によって見つかった場合、 実引数依存の名前探索 は抑制されます。

パラメータ

戻り値

戻り値は { ret, last } で、 ret は範囲の新しい終端を指すpast-the-endイテレータです。

計算量

空でない範囲の場合、対応する述語 comp の適用は正確に ranges:: distance ( first, last ) - 1 回であり、任意の射影 proj の適用はその2倍を超えない。

注記

削除は、範囲内の要素を移動代入によってシフトすることで行われ、削除されない要素が範囲の先頭に現れるようにします。残る要素の相対的な順序は保持され、コンテナの 物理的な サイズは変更されません。 [ ret , last ) 内のイテレータ（存在する場合）は依然としてデリファレンス可能ですが、要素自体は未規定の値を持ちます（ MoveAssignable の事後条件に従います）。

ranges::unique への呼び出しは、時としてコンテナの erase メンバ関数の呼び出しに続けられます。これにより未規定の値が削除され、コンテナの 物理的 サイズが新しい 論理的 サイズに合うように縮小されます。これら2つの呼び出しを組み合わせることで、 Erase–remove イディオム を実現します。

実装例

struct unique_fn
{
    template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
             std::indirect_equivalence_relation<std::projected<I, Proj>>
                 C = ranges::equal_to>
    constexpr ranges::subrange<I>
        operator()(I first, S last, C comp = {}, Proj proj = {}) const
    {
        first = ranges::adjacent_find(first, last, comp, proj);
        if (first == last)
            return {first, first};
        auto i {first};
        ++first;
        while (++first != last)
            if (!std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *first)))
                *++i = ranges::iter_move(first);
        return {++i, first};
    }
    template<ranges::forward_range R, class Proj = std::identity,
             std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>>
                 C = ranges::equal_to>
    requires std::permutable<ranges::iterator_t<R>>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, C comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(comp), std::move(proj));
    }
};
inline constexpr unique_fn unique {};

例

#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
struct id {
    int i;
    explicit id(int i) : i {i} {}
};
void print(id i, const auto& v)
{
    std::cout << i.i << ") ";
    std::ranges::for_each(v, [](auto const& e) { std::cout << e << ' '; });
    std::cout << '\n';
}
int main()
{
    // 重複要素を含むベクトル
    std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
    print(id {1}, v);
    // 連続する重複要素を削除
    const auto ret = std::ranges::unique(v);
    // vは現在 {1 2 1 3 4 5 4 x x x} を保持（'x'は不定値）
    v.erase(ret.begin(), ret.end());
    print(id {2}, v);
    // ソート後にuniqueを適用して全ての重複を削除
    std::ranges::sort(v); // {1 1 2 3 4 4 5}
    print(id {3}, v);
    const auto [first, last] = std::ranges::unique(v.begin(), v.end());
    // vは現在 {1 2 3 4 5 x x} を保持（'x'は不定値）
    v.erase(first, last);
    print(id {4}, v);
    // カスタム比較と射影を用いたunique
    std::vector<std::complex<int>> vc { {1, 1}, {-1, 2}, {-2, 3}, {2, 4}, {-3, 5} };
    print(id {5}, vc);
    const auto ret2 = std::ranges::unique(vc,
        // 実部の絶対値が等しい場合に複素数を等価とみなす：
        [](int x, int y) { return std::abs(x) == std::abs(y); }, // comp
        [](std::complex<int> z) { return z.real(); }             // proj
    );
    vc.erase(ret2.begin(), ret2.end());
    print(id {6}, vc);
}

1) 1 2 1 1 3 3 3 4 5 4
2) 1 2 1 3 4 5 4
3) 1 1 2 3 4 4 5
4) 1 2 3 4 5
5) (1,1) (-1,2) (-2,3) (2,4) (-3,5)
6) (1,1) (-2,3) (-3,5)

関連項目