Skip to main content

std::ranges::unique_copy() algorithm

// (1)
constexpr unique_copy_result<I, O>
    unique_copy( I first, S last, O result, C comp = {}, Proj proj = {} );

// (2)
constexpr unique_copy_result<ranges::borrowed_iterator_t<R>, O>
    unique_copy( R&& r, O result, C comp = {}, Proj proj = {} );

The type of arguments are generic and have the following constraints:

  • I - std::input_iterator
  • S - std::sentinel_for<I>
  • O - std::weakly_incrementable
  • R - std::ranges::input_range
  • C:
    • (1) - std::indirect_equivalence_relation<std::projected<I, Proj>>
    • (2) - std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>>
  • Proj - (none)

The Proj and C template argument have the following default types std::identity, ranges::equal_to for all overloads.

Additionally, each overload has the following constraints:

  • (1):

    indirectly_copyable<I, O>
    && (forward_iterator<I>
        || (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>)
        || indirectly_copyable_storable<I, O>)

  • (2):

    indirectly_copyable<ranges::iterator_t<R>, O>
    && (forward_iterator<ranges::iterator_t<R>>
        || (input_iterator<O> && same_as<ranges::range_value_t<R>, iter_value_t<O>>)
        || indirectly_copyable_storable<ranges::iterator_t<R>, O>)

(The std:: namespace was omitted here for readability)

With helper types defined as follows:

template< class I, class O >
using unique_copy_result = ranges::in_out_result<I, O>;

  • (1) Copies the elements from the source range [first; last), to the destination range beginning at result in such a way that there are no consecutive equal elements.

    Only the first element of each group of equal elements is copied.

    Two consecutive elements *(i - 1) and *i are considered equivalent if std::invoke(comp, std::invoke(proj, *(i - 1)), std::invoke(proj, *i)) == true, where i is an iterator in the range [first + 1, last).

  • (2) Same as (1), but uses r as the range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

caution

The ranges [first; last) and [result; result + ranges::distance(first, last)) must not overlap.

Parameters​

first
last

The source range to process.

r

The source range to process.

result

Iterator to the destination range.

comp

The binary predicate to compare the projected elements with.

proj

The projection to apply to the elements.

Return value​

Given N as ranges::distance(first, last):

{
  last,
  result + N
}

Complexity​

Exactly N - 1 applications of the corresponding predicate comp and no more than twice as many applications of any projection proj.

Exceptions​

(none)

Possible implementation​

unique_copy(1) and unique_copy(2)
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 {};

Examples​

Main.cpp
#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),
        {}, // default comparator std::ranges::equal_to
        [](int x) { return std::abs(x); } // projection
    );
    print("v2: ", v2);
}
Output
s1: The      string    with many       spaces!
s2: The string with many spaces!
v1: -1 +1 +2 -2 -3 +3 -3
v2: -1 +2 -3
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.