std::ranges::unique() 算法

自 C++20 起

简化

// (1)
constexpr ranges::subrange<I>
    unique( I first, S last, C comp = {}, Proj proj = {} );

// (2)
constexpr ranges::borrowed_subrange_t<R>
    unique( R&& r, C comp = {}, Proj proj = {} );

参数类型是泛型的，并具有以下约束

• I - std::permutable
• S - std::sentinel_for<I>
• R - std::ranges::forward_range
• C:
  • (1) - std::indirect_equivalence_relation<std::projected<I, Proj>>
  • (2) - std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>>
• Proj - (无)

对于所有重载，Proj 和 C 模板参数具有以下默认类型：std::identity，ranges::equal_to。

此外，每个重载都有以下约束

• (2) - std::permutable<ranges::iterator_t<R>>

详细

// (1)
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>
    unique( I first, S last, C comp = {}, Proj proj = {} );

// (2)
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>
    unique( R&& r, C comp = {}, Proj proj = {} );

• (1) 从范围 [first; last) 中每个连续的等价元素组中消除除第一个元素之外的所有元素，并返回子范围 [ret; last)，其中 ret 是范围新末尾的过尾迭代器。

  如果 std::invoke(comp, std::invoke(proj, *(i - 1)), std::invoke(proj, *i)) == true，则认为两个连续元素 *(i - 1) 和 *i 等价，其中 i 是范围 [first + 1; last) 中的迭代器。

• (2) 与 (1) 相同，但使用 r 作为范围，如同使用 ranges::begin(r) 作为 first 和 ranges::end(r) 作为 last。

本页描述的函数类实体是niebloids。

参数

first last	要处理的元素范围。
r	要处理的元素范围。
comp	用于比较投影元素的二元谓词。
proj	要应用于元素的投影。

返回值

返回

{
  ret,
  last
}

其中 ret 是范围新末尾的过尾迭代器。

复杂度

对于非空范围，精确执行 ranges::distance(first, last) - 1 次相应谓词 comp 的应用，且任何投影 proj 的应用不超过两倍。

异常

(无)

可能的实现

unique(1) 和 unique(2)

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 {};

备注

删除通过移动赋值来实现，将范围中的元素移动，使得不被删除的元素出现在范围的开头。保留剩余元素的相对顺序，并且容器的“物理”大小保持不变。

范围 [ret; last) 中的迭代器（如果有）仍然可以解引用，但元素本身的值未指定（根据 MoveAssignable 后置条件）。

对 ranges::unique 的调用有时会接着调用容器的 erase 成员函数，该函数会擦除未指定的值并将容器的“物理”大小缩小以匹配其新的“逻辑”大小。这两个调用共同构成了 Erase–remove idiom（擦除-移除习语）。

示例

Main.cpp

#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()
{
    // a vector containing several duplicated elements
    std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4};

    print(id {1}, v);

    // remove consecutive (adjacent) duplicates
    const auto ret = std::ranges::unique(v);
    // v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
    v.erase(ret.begin(), ret.end());
    print(id {2}, v);

    // sort followed by unique, to remove all duplicates
    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 now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
    v.erase(first, last);
    print(id {4}, v);

    // unique with custom comparison and projection
    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,
        // consider two complex nums equal if their real parts are equal by module:
        [](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)