std::ranges::unique

在标头 `<algorithm>` 定义

调用签名
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 = {} );	(1)	(C++20 起)
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 = {} );	(2)	(C++20 起)

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 。

此页面上描述的仿函数实体是 niebloid，即：

调用它们中的任何一个时不能显式指定模板实参。
它们都不对实参依赖查找可见。
在通过函数调用运算符左侧的名字进行无限定查找，找到它们之一时，禁止实参依赖查找。

实际上，它们能以函数对象，或者某些特殊编译器扩展实现。

参数

first, last	-	要处理的元素范围
r	-	要处理的元素范围
comp	-	比较投影后元素的二元谓词
proj	-	应用到元素的投影

返回值

返回 {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 = std::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()
{
    // 含数个重复元素的 vector
    std::vector<int> v{1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
 
    print(id{1}, v);
 
    // 移除连续（相接）的副本
    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);
 
    // sort 后随 unique ，移除所有副本
    std::ranges::sort(v); // {1 1 2 3 4 4 5}
    print(id{3}, v);
 
    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);
 
    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)

参阅

ranges::unique_copy (C++20)	创建某范围的不含连续重复元素的副本 (niebloid)
ranges::adjacent_find (C++20)	查找首对相邻的相同（或满足给定谓词的）元素 (niebloid)
ranges::removeranges::remove_if (C++20)(C++20)	移除满足特定判别标准的元素 (niebloid)
unique	移除范围内的连续重复元素 (函数模板)
unique	删除连续的重复元素 (`std::list<T,Allocator>` 的公开成员函数)
unique (C++11)	删除连续的重复元素 (`std::forward_list<T,Allocator>` 的公开成员函数)

编译器支持
自立实现与有宿主实现
语言
标准库
标准库标头
具名要求
功能特性测试宏 (C++20)
语言支持库
概念库 (C++20)
元编程库 (C++11)
诊断库
通用工具库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
并发支持库 (C++11)
技术规范
符号索引
外部库

Xi Xu's More Things

std::ranges::unique

参数

返回值

复杂度

注解

可能的实现

示例

参阅

导航