Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/algorithm/ranges/unique copy"

From cppreference.com
< cpp‎ | algorithm‎ | ranges
m (- ranges::, fmt)
m (→‎Possible implementation: -' ')
 
(5 intermediate revisions by 3 users not shown)
Line 2: Line 2:
 
{{cpp/algorithm/ranges/navbar}}
 
{{cpp/algorithm/ranges/navbar}}
 
{{dcl begin}}
 
{{dcl begin}}
−
{{dcl header | algorithm}}
+
{{dcl header|algorithm}}
−
{{dcl h | Call signature}}
+
{{dcl h|Call signature}}
−
{{dcl | num=1 | since=c++20 |1=
+
{{dcl|num=1|since=c++20|1=
 
template< std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,
 
template< std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,
 
           class Proj = std::identity,
 
           class Proj = std::identity,
 
           std::indirect_equivalence_relation<std::projected<I, Proj>> C = ranges::equal_to >
 
           std::indirect_equivalence_relation<std::projected<I, Proj>> C = ranges::equal_to >
−
requires std::indirectly_copyable<I, O> && (std::forward_iterator<I> {{!!}}
+
requires std::indirectly_copyable<I, O> && (std::forward_iterator<I> {{!!}}
 
             (std::input_iterator<O> && std::same_as<std::iter_value_t<I>,
 
             (std::input_iterator<O> && std::same_as<std::iter_value_t<I>,
−
                std::iter_value_t<O>>) {{!!}} std::indirectly_copyable_storable<I, O>)
+
                std::iter_value_t<O>>) {{!!}} std::indirectly_copyable_storable<I, O>)
 
constexpr unique_copy_result<I, O>
 
constexpr unique_copy_result<I, O>
−
          unique_copy( I first, S last, O result, C comp = {}, Proj proj = {} );
+
    unique_copy( I first, S last, O result, C comp = {}, Proj proj = {} );
 
}}
 
}}
−
{{dcl | num=2 | since=c++20 |1=
+
{{dcl|num=2|since=c++20|1=
 
template< ranges::input_range R, std::weakly_incrementable O, class Proj = std::identity,
 
template< ranges::input_range R, std::weakly_incrementable O, class Proj = std::identity,
 
           std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>,
 
           std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>,
−
            Proj>> C = ranges::equal_to >
+
              Proj>> C = ranges::equal_to >
−
requires std::indirectly_copyable<ranges::iterator_t<R>, O> &&
+
requires std::indirectly_copyable<ranges::iterator_t<R>, O> &&
−
              (std::forward_iterator<ranges::iterator_t<R>> {{!!}}
+
            (std::forward_iterator<ranges::iterator_t<R>> {{!!}}
−
              (std::input_iterator<O> && std::same_as<ranges::range_value_t<R>,
+
            (std::input_iterator<O> && std::same_as<ranges::range_value_t<R>,
−
                std::iter_value_t<O>>) {{!!}}
+
                std::iter_value_t<O>>) {{!!}}
−
              std::indirectly_copyable_storable<ranges::iterator_t<R>, O>)
+
            std::indirectly_copyable_storable<ranges::iterator_t<R>, O>)
 
constexpr unique_copy_result<ranges::borrowed_iterator_t<R>, O>
 
constexpr unique_copy_result<ranges::borrowed_iterator_t<R>, O>
−
          unique_copy( R&& r, O result, C comp = {}, Proj proj = {} );
+
    unique_copy( R&& r, O result, C comp = {}, Proj proj = {} );
 
}}
 
}}
−
{{dcl h | Helper types}}
+
{{dcl h|Helper types}}
−
{{dcl | num=3 | since=c++20 |1=
+
{{dcl|num=3|since=c++20|1=
−
template<class I, class O>
+
template< class I, class O >
−
  using unique_copy_result = ranges::in_out_result<I, O>;
+
using unique_copy_result = ranges::in_out_result<I, O>;
 
}}
 
}}
 
{{dcl end}}
 
{{dcl end}}
  
−
@1@ Copies the elements from the source range {{tt|[first, last)}}, to the destination range beginning at {{tt|result}} in such a way that there are no consecutive equal elements. Only the first element of each group of equal elements is copied.
+
@1@ Copies the elements from the source range {{range|first|last}}, to the destination range beginning at {{c|result}} in such a way that there are no consecutive equal elements. Only the first element of each group of equal elements is copied.
  
−
@@ ''Precondition:'' the ranges {{tt|[first, last)}} and {{tt|[result, result + N)}} do not overlap, where {{c|1= N = ranges::distance(first, last).}}
+
@@ The ranges {{range|first|last}} and {{range|result|result + N}} must not overlap. {{c|1= N = ranges::distance(first, last)}}.
  
−
@@ Two consequtive elements {{tt|*(i - 1)}} and {{tt|*i}} are considered equivalent if {{c|1=std::invoke(comp, std::invoke(proj, *(i - 1)), std::invoke(proj, *i)) == true}}, where {{tt|i}} is an iterator in the range {{tt|[first + 1, last)}}.
+
@@ Two consecutive elements {{c|*(i - 1)}} and {{c|*i}} are considered equivalent if {{c|1=std::invoke(comp, std::invoke(proj, *(i - 1)), std::invoke(proj, *i)) == true}}, where {{tt|i}} is an iterator in the range {{range|first + 1|last}}.
  
−
@2@ Same as {{v|1}}, but uses {{tt|r}} as the range, as if using {{c|ranges::begin(r)}} as {{tt|first}}, and {{c|ranges::end(r)}} as {{tt|last}}.
+
@2@ Same as {{v|1}}, but uses {{c|r}} as the range, as if using {{c|ranges::begin(r)}} as {{c|first}}, and {{c|ranges::end(r)}} as {{c|last}}.
  
 
{{cpp/ranges/niebloid}}
 
{{cpp/ranges/niebloid}}
Line 45: Line 45:
 
===Parameters===
 
===Parameters===
 
{{par begin}}
 
{{par begin}}
−
{{par | first, last | the source range of elements}}
+
{{par|first, last|the source range of elements}}
−
{{par | r | the source range of elements}}
+
{{par|r|the source range of elements}}
−
{{par | result | the destination range of elements}}
+
{{par|result|the destination range of elements}}
−
{{par | comp | the binary predicate to compare the projected elements}}
+
{{par|comp|the binary predicate to compare the projected elements}}
−
{{par | proj | the projection to apply to the elements.}}
+
{{par|proj|the projection to apply to the elements}}
 
{{par end}}
 
{{par end}}
  
 
===Return value===
 
===Return value===
−
Returns an object {{tt|{last, result + N}.}}
+
{{c|{last, result + N} }}
  
 
===Complexity===
 
===Complexity===
−
Exactly {{tt|N - 1}} applications of the corresponding predicate {{tt|comp}} and no more that twice as many applications of any projection {{tt|proj}}.
+
Exactly {{c|N - 1}} applications of the corresponding predicate {{c|comp}} and no more than twice as many applications of any projection {{c|proj}}.
  
 
===Possible implementation===
 
===Possible implementation===
−
<!-- See also the implementations in [https://github.com/gcc-mirror/gcc/blob/.../#L... libstdc++], and [libc++], and [ms open-stl], and [nano-ranges], and [v3-ranges], and [stl2]... -->
+
See also the implementations in [https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/ranges_algo.h#L1198-L1276 libstdc++] and [https://github.com/microsoft/STL/blob/472161105d596192194d4715ccad307c6c163b4a/stl/inc/algorithm#L4022-L4113 MSVC STL] (and third-party libraries: [https://github.com/CaseyCarter/cmcstl2/blob/master/include/stl2/detail/algorithm/unique_copy.hpp cmcstl2], [https://github.com/tcbrindle/NanoRange/blob/master/include/nanorange/algorithm/unique_copy.hpp NanoRange], and [https://github.com/ericniebler/range-v3/blob/master/include/range/v3/algorithm/unique_copy.hpp range-v3]).
−
{{eq fun| 1=
+
{{eq fun|1=
−
struct unique_copy_fn {
+
struct unique_copy_fn
−
  template<std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,
+
{
−
        class Proj = std::identity,
+
    template<std::input_iterator I, std::sentinel_for<I> S, std::weakly_incrementable O,
−
        std::indirect_equivalence_relation<std::projected<I, Proj>> C = ranges::equal_to>
+
            class Proj = std::identity,
−
     requires std::indirectly_copyable<I, O> && (std::forward_iterator<I> or
+
            std::indirect_equivalence_relation<std::projected<I,
−
              (std::input_iterator<O> && std::same_as<std::iter_value_t<I>,
+
                Proj>> C = ranges::equal_to>
−
                std::iter_value_t<O>>) or std::indirectly_copyable_storable<I, O>)
+
     requires std::indirectly_copyable<I, O> && (std::forward_iterator<I> {{!!}}
−
      constexpr ranges::unique_copy_result<I, O>
+
                (std::input_iterator<O> && std::same_as<std::iter_value_t<I>,
−
         operator() ( I first, S last, O result, C comp = {}, Proj proj = {} ) const {
+
                    std::iter_value_t<O>>) {{!!}} std::indirectly_copyable_storable<I, O>)
−
            if (!(first == last)) {
+
    constexpr ranges::unique_copy_result<I, O>
−
                std::iter_value_t<I> value = *first;
+
         operator()(I first, S last, O result, C comp = {}, Proj proj = {}) const
−
                *result = value;
+
    {
−
                ++result;
+
        if (!(first == last))
−
                while (!(++first == last)) {
+
        {
−
                    auto&& value2 = *first;
+
            std::iter_value_t<I> value = *first;
−
                    if (!std::invoke(comp, std::invoke(proj, value2),
+
            *result = value;
−
                            std::invoke(proj, value))) {
+
            ++result;
−
                        value = std::forward<decltype(value2)>(value2);
+
            while (!(++first == last))
−
                        *result = value;
+
            {
−
                        ++result;
+
                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,
+
        return {std::move(first), std::move(result)};
−
          std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>,
+
    }
−
            Proj>> C = ranges::equal_to>
+
 
 +
    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> &&
 
     requires std::indirectly_copyable<ranges::iterator_t<R>, O> &&
−
              (std::forward_iterator<ranges::iterator_t<R>> or
+
                (std::forward_iterator<ranges::iterator_t<R>> {{!!}}
−
              (std::input_iterator<O> && std::same_as<ranges::range_value_t<R>,
+
                (std::input_iterator<O> && std::same_as<ranges::range_value_t<R>,
−
                std::iter_value_t<O>>) {{!!}}
+
                    std::iter_value_t<O>>) {{!!}}
−
              std::indirectly_copyable_storable<ranges::iterator_t<R>, O>)
+
                std::indirectly_copyable_storable<ranges::iterator_t<R>, O>)
−
      constexpr ranges::unique_copy_result<ranges::borrowed_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 {
+
         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));
+
        return (*this)(ranges::begin(r), ranges::end(r), std::move(result),
−
        }
+
                      std::move(comp), std::move(proj));
 +
    }
 
};
 
};
  
−
inline constexpr unique_copy_fn unique_copy{};
+
inline constexpr unique_copy_fn unique_copy {};
 
}}
 
}}
  
 
===Example===
 
===Example===
−
{{example|code=
+
{{example
 +
|code=
 
#include <algorithm>
 
#include <algorithm>
 
#include <cmath>
 
#include <cmath>
Line 116: Line 124:
 
#include <type_traits>
 
#include <type_traits>
  
−
void print(const auto& rem, const auto& v) {
+
void print(const auto& rem, const auto& v)
 +
{
 
     using V = std::remove_cvref_t<decltype(v)>;
 
     using V = std::remove_cvref_t<decltype(v)>;
−
     constexpr bool sep {std::is_same_v<typename V::value_type, int>};
+
     constexpr bool sep{std::is_same_v<typename V::value_type, int>};
 
     std::cout << rem << std::showpos;
 
     std::cout << rem << std::showpos;
−
     for (const auto& e : v) std::cout << e << (sep ? " " : "");
+
     for (const auto& e : v)
 +
        std::cout << e << (sep ? " " : "");
 
     std::cout << '\n';
 
     std::cout << '\n';
 
}
 
}
Line 126: Line 136:
 
int main()
 
int main()
 
{
 
{
−
     std::string s1 {"The      string    with many      spaces!"};
+
     std::string s1{"The      string    with many      spaces!"};
 
     print("s1: ", s1);
 
     print("s1: ", s1);
  
Line 132: Line 142:
 
     std::ranges::unique_copy(
 
     std::ranges::unique_copy(
 
         s1.begin(), s1.end(), std::back_inserter(s2),
 
         s1.begin(), s1.end(), std::back_inserter(s2),
−
         [](char c1, char c2){ return c1 == ' ' && c2 == ' '; }
+
         [](char c1, char c2) { return c1 == ' ' && c2 == ' '; }
 
     );
 
     );
 
     print("s2: ", s2);
 
     print("s2: ", s2);
  
−
 
+
     const auto v1 = {-1, +1, +2, -2, -3, +3, -3};
−
     const auto v1 = { -1, +1, +2, -2, -3, +3, -3, };
+
 
     print("v1: ", v1);
 
     print("v1: ", v1);
 
     std::list<int> v2;
 
     std::list<int> v2;
Line 156: Line 165:
 
===See also===
 
===See also===
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/algorithm/ranges/dsc unique}}
+
{{dsc inc|cpp/algorithm/ranges/dsc unique}}
−
{{dsc inc | cpp/algorithm/ranges/dsc copy}}
+
{{dsc inc|cpp/algorithm/ranges/dsc copy}}
−
{{dsc inc | cpp/algorithm/ranges/dsc adjacent_find}}
+
{{dsc inc|cpp/algorithm/ranges/dsc adjacent_find}}
−
{{dsc inc | cpp/algorithm/dsc unique_copy}}
+
{{dsc inc|cpp/algorithm/dsc unique_copy}}
 
{{dsc end}}
 
{{dsc end}}
  
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
 
{{langlinks|de|es|fr|it|ja|pt|ru|zh}}

Latest revision as of 17:07, 26 October 2023

 
C++
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
(C++11)                (C++11)(C++11)

Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17)(C++11)
(C++20)(C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
(C++11)
(C++17)
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
 
Constrained algorithms
All names in this menu belong to namespace std::ranges
Non-modifying sequence operations
Modifying sequence operations
Partitioning operations
Sorting operations
Binary search operations (on sorted ranges)
       
       
    
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
       
       
Permutation operations
Fold operations
Numeric operations
(C++23)            
Operations on uninitialized storage
Return types
 
Defined in header <algorithm>
Call signature
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) (since 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) (since C++20)
Helper types
template< class I, class O >
using unique_copy_result = ranges::in_out_result<I, O>;
 (3) (since C++20)
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.
The ranges [first, last) and [result, result + N) must not overlap. N = ranges::distance(first, last).
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, that is:

In practice, they may be implemented as function objects, or with special compiler extensions.

Contents

[edit] Parameters

first, last - the source range of elements
r - the source range of elements
result - the destination range of elements
comp - the binary predicate to compare the projected elements
proj - the projection to apply to the elements

[edit] Return value

{last, result + N}

[edit] Complexity

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

[edit] Possible implementation

See also the implementations in libstdc++ and MSVC STL (and third-party libraries: cmcstl2, NanoRange, and range-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> ||
                 (std::input_iterator<O> && std::same_as<std::iter_value_t<I>,
                     std::iter_value_t<O>>) || 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>> ||
                 (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 {};

[edit] Example

Run this code
#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

[edit] See also

(C++20)
 removes consecutive duplicate elements in a range
(niebloid)[edit]
(C++20)(C++20)
 copies a range of elements to a new location
(niebloid)[edit]
(C++20)
 finds the first two adjacent items that are equal (or satisfy a given predicate)
(niebloid)[edit]
creates a copy of some range of elements that contains no consecutive duplicates
(function template) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/algorithm/ranges/unique_copy&oldid=161497"