std::ranges::unique_copy, std::ranges::unique_copy_result

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

排列
数值运算
未初始化存储上的操作
(C++17)
(C++17)
(C++17)
C 库
 
受约束算法
不修改序列的操作
修改序列的操作
划分操作
排序操作
二分搜索操作
集合操作(在已排序范围上)
堆操作
最小/最大操作
排列
未初始化存储上的操作
返回类型
 
在标头 <algorithm> 定义
调用签名
template< std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,

          class Proj = std::identity,
          std::indirect_equivalence_relation<std::projected<I, Proj>> C = ranges::equal_to >
requires  std::indirectly_copyable<I, O> && (std::forward_iterator<I> ||
             (std::input_iterator<O> && std::same_as<std::iter_value_t<I>,
                std::iter_value_t<O>>) || std::indirectly_copyable_storable<I, O>)
constexpr unique_copy_result<I, O>

          unique_copy( I first, S last, O result, C comp = {}, Proj proj = {} );
(1) (C++20 起)
template< ranges::input_range R, std::weakly_incrementable O, class Proj = std::identity,

          std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>,
            Proj>> C = ranges::equal_to >
requires  std::indirectly_copyable<ranges::iterator_t<R>, O> &&
              (std::forward_iterator<ranges::iterator_t<R>> ||
              (std::input_iterator<O> && std::same_as<ranges::range_value_t<R>,
                std::iter_value_t<O>>) ||
              std::indirectly_copyable_storable<ranges::iterator_t<R>, O>)
constexpr unique_copy_result<ranges::borrowed_iterator_t<R>, O>

          unique_copy( R&& r, O result, C comp = {}, Proj proj = {} );
(2) (C++20 起)
辅助类型
template<class I, class O>
  using unique_copy_result = ranges::in_out_result<I, O>;
(3) (C++20 起)
1) 从源范围 [first, last) 复制元素到始于 result 的目标范围,使得无连续的元素比较相等。只复制每群相等元素中的第一个。
范围 [first, last)[result, result + N) 必须不重叠。 N = ranges::distance(first, last).
认为二个连续元素 *(i - 1)*i 比较相等,若 std::invoke(comp, std::invoke(proj, *(i - 1)), std::invoke(proj, *i)) == true ,其中 i 为范围 [first + 1, last) 中的迭代器。
2)(1) ,但以 r 为源范围,如同以 ranges::begin(r)first 并以 ranges::end(r)last

此页面上描述的仿函数实体是 niebloid,即:

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

参数

first, last - 源元素范围
r - 源元素范围
result - 目标元素范围
comp - 比较投影后元素的谓词
proj - 应用到谓词的投影

返回值

{last, result + N}

复杂度

准确应用 N - 1 次对应的谓词 comp 并应用不多于其次数二倍的投影 proj

可能的实现

参阅 libstdc++MSVC STL (及第三方库: cmcstl2NanoRangerange-v3 )中的实现。

struct unique_copy_fn {
  template<std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,
         class Proj = std::identity,
         std::indirect_equivalence_relation<std::projected<I, Proj>> C = ranges::equal_to>
    requires std::indirectly_copyable<I, O> && (std::forward_iterator<I> or
               (std::input_iterator<O> && std::same_as<std::iter_value_t<I>,
                 std::iter_value_t<O>>) or std::indirectly_copyable_storable<I, O>)
      constexpr ranges::unique_copy_result<I, O>
        operator() ( I first, S last, O result, C comp = {}, Proj proj = {} ) const {
            if (!(first == last)) {
                std::iter_value_t<I> value = *first;
                *result = value;
                ++result;
                while (!(++first == last)) {
                    auto&& value2 = *first;
                    if (!std::invoke(comp, std::invoke(proj, value2),
                             std::invoke(proj, value))) {
                        value = std::forward<decltype(value2)>(value2);
                        *result = value;
                        ++result;
                    }
                }
            }
 
            return {std::move(first), std::move(result)};
        }
 
  template<ranges::input_range R, std::weakly_incrementable O, class Proj = std::identity,
           std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>,
             Proj>> C = ranges::equal_to>
    requires std::indirectly_copyable<ranges::iterator_t<R>, O> &&
               (std::forward_iterator<ranges::iterator_t<R>> or
               (std::input_iterator<O> && std::same_as<ranges::range_value_t<R>,
                 std::iter_value_t<O>>) ||
               std::indirectly_copyable_storable<ranges::iterator_t<R>, O>)
      constexpr ranges::unique_copy_result<ranges::borrowed_iterator_t<R>, O>
        operator() ( R&& r, O result, C comp = {}, Proj proj = {} ) const {
            return (*this)(ranges::begin(r), ranges::end(r), std::move(result),
                           std::move(comp), std::move(proj));
        }
};
 
inline constexpr unique_copy_fn unique_copy{};

示例

#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <list>
#include <string>
#include <type_traits>
 
void print(const auto& rem, const auto& v) {
    using V = std::remove_cvref_t<decltype(v)>;
    constexpr bool sep {std::is_same_v<typename V::value_type, int>};
    std::cout << rem << std::showpos;
    for (const auto& e : v) std::cout << e << (sep ? " " : "");
    std::cout << '\n';
}
 
int main()
{
    std::string s1 {"The      string    with many       spaces!"};
    print("s1: ", s1);
 
    std::string s2;
    std::ranges::unique_copy(
        s1.begin(), s1.end(), std::back_inserter(s2),
        [](char c1, char c2){ return c1 == ' ' && c2 == ' '; }
    );
    print("s2: ", s2);
 
 
    const auto v1 = { -1, +1, +2, -2, -3, +3, -3, };
    print("v1: ", v1);
    std::list<int> v2;
    std::ranges::unique_copy(
        v1, std::back_inserter(v2),
        {}, // 默认比较器 std::ranges::equal_to
        [](int x) { return std::abs(x); } // 投影
    );
    print("v2: ", v2);
}

输出:

s1: The      string    with many       spaces!
s2: The string with many spaces!
v1: -1 +1 +2 -2 -3 +3 -3 
v2: -1 +2 -3

参阅

移除范围中的连续重复元素
(niebloid)
将某一范围的元素复制到一个新的位置
(niebloid)
查找首对相邻的相同(或满足给定谓词的)元素
(niebloid)
创建某范围的不含连续重复元素的副本
(函数模板)