std::ranges::unique

来自cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法: std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
未初始化存储上的操作
划分操作
排序操作
(C++11)
二分搜索操作
集合操作(在已排序范围上)
堆操作
(C++11)
最小/最大操作
(C++11)
(C++17)

排列
数值运算
C 库
 
受约束算法
不修改序列的操作
修改序列的操作
划分操作
排序操作
二分搜索操作
集合操作(在已排序范围上)
堆操作
最小/最大操作
排列
未初始化存储上的操作
返回类型
 
定义于头文件 <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)

参阅

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