std::ranges:: unique

本页面描述的函数式实体是 算法函数对象 （非正式称为 niebloids ），即：

• 在调用其中任何一个时，都不能指定显式模板实参列表。
• 它们对 实参依赖查找 均不可见。
• 当通过 常规非限定查找 将其中任何一个作为函数调用运算符左侧的名称找到时，会抑制 实参依赖查找 。

参数

返回值

返回 { ret, last } ，其中 ret 是指向范围新末尾的尾后迭代器。

复杂度

对于非空范围，恰好需要 ranges:: distance ( first, last ) - 1 次对应谓词 comp 的应用，以及不超过任何投影 proj 应用次数的两倍。

注释

移除操作通过（借助移动赋值）移动区间内的元素来实现，使得不需要被移除的元素出现在区间的起始位置。保留元素的相对顺序保持不变，且容器的 物理 大小不变。位于 [ ret , last ) 区间内的迭代器（如果存在）仍然可解引用，但元素本身具有未指定的值（符合 MoveAssignable 的后置条件）。

对 ranges::unique 的调用有时会紧随容器 erase 成员函数的调用，该操作会擦除未指定的值并将容器的 物理 大小缩减至与其新 逻辑 大小相匹配。这两个调用共同实现了 擦除-删除 惯用法 。

可能的实现

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)

参见