[ Web Proxy ]
URL:
Viewing: https://cppreference.com/cpp/algorithm/ranges/unique [Back]  [Original]

std::ranges::unique - cppreference.com
cppreference.com
Namespaces
Variants

std::ranges::unique

From cppreference.com
 
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Non-modifying sequence operations    
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(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
(C++11)    

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
Permutation operations


 
Constrained algorithms
All names in this menu belong to namespace std::ranges
Non-modifying sequence operations
Fold operations (Helper templates)
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
Specialized <memory> algorithms
Return types
 
Defined in header <algorithm>
Call signature
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) (since 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) (since C++20)
template< /*execution-policy*/ Ep,
          std::random_access_iterator I, std::sized_sentinel_for<I> S,
          class Proj = std::identity,
          std::indirect_equivalence_relation
              <std::projected<I, Proj>> C = ranges::equal_to >
    requires std::permutable<I>
ranges::subrange<I>
    unique( Ep&& policy, I first, S last, C comp = {}, Proj proj = {} );
(3) (since C++26)
template< /*execution-policy*/ Ep,
          /*sized-random-access-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>>
ranges::borrowed_subrange_t<R>
    unique( Ep&& policy, R&& r, C comp = {}, Proj proj = {} );
(4) (since C++26)

For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.

1,2) Removes all except the first element from every group of consecutive equivalent elements from the target range [firstlast) or r. Elements (projected by proj) are compared using the given binary predicate comp.
3,4) Same as (1,2), but executed according to policy.

Removing is done by partitioning the elements in the target range. Given the partition point result, the leading elements of every group appear before result, while other elements can only appear since result.

  • The underlying sequence of the target range is not shortened by the removing operation.
  • Elements are shifted by move assignment.
  • All iterators in the target range are still dereferenceable, and each element starting from result has a valid but unspecified state.
  • The removing operation is stable: the relative order of the elements not to be removed stays the same.

The function-like entities described on this page are algorithm function objects (informally known as niebloids), that is:

Parameters

first, last - the iterator-sentinel pair defining the target range
r - the target range
comp - the predicate to be applied to the (projected) elements
proj - the projection to be applied to the elements
policy - the execution policy to use

Return value

A subrange starting from the iterator result mentioned above and ends at the end of the target range.

Complexity

Given \(\scriptsize N\)N as ranges::distance(first, last) or ranges::distance(r):

1,2) Exactly \(\scriptsize \max(0,N-1)\)max(0,N-1) applications of comp, and at most twice as many applications of proj.
3,4) \(\scriptsize \mathcal{O}(N)\)(N) applications of comp, and at most twice as many applications of proj.

Exceptions

3,4) During the execution process:
  • If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
  • If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).

Notes

A call to ranges::unique is typically followed by a call to a container's erase member function to actually remove elements from the container. These two invocations together constitute a so-called erase-remove idiom.

Possible implementation

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 = ranges::iter_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::next(ranges::begin(r), ranges::end(r)),
                       std::move(comp), std::move(proj));
    }
};

inline constexpr unique_fn unique{};

Example

#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, [](const auto& e) { std::cout << e << ' '; });
    std::cout << '\n';
}

int main()
{
    // a vector containing several duplicated elements
    std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
    
    print(id{1}, v);
    
    // remove consecutive (adjacent) duplicates
    const auto ret = std::ranges::unique(v);
    // v now holds {1 2 1 3 4 5 4 x x x}, where x is indeterminate
    v.erase(ret.begin(), ret.end());
    print(id{2}, v);
    
    // sort followed by unique, to remove all duplicates
    std::ranges::sort(v); // {1 1 2 3 4 4 5}
    print(id{3}, v);
    
    const auto [first, last] = std::ranges::unique(v.begin(), v.end());
    // v now holds {1 2 3 4 5 x x}, where x is indeterminate
    v.erase(first, last);
    print(id{4}, v);
    
    // unique with custom comparison and projection
    std::vector<std::complex<int>> vc {{1, 1}, {-1, 2}, {-2, 3}, {2, 4}, {-3, 5}};
    print(id{5}, vc);
    
    const auto ret2 = std::ranges::unique(vc,
        // consider two complex nums equal if their real parts are equal by module:
        [](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);
}

Output:

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)

See also

removes consecutive duplicate elements in a range
(function template) [edit]
creates a copy of some range of elements that contains no consecutive duplicates
(algorithm function object)[edit]
finds the first two adjacent items that are equal (or satisfy a given predicate)
(algorithm function object)[edit]
removes elements satisfying specific criteria
(algorithm function object)[edit]
removes consecutive duplicate elements
(public member function of std::list<T,Allocator>) [edit]
removes consecutive duplicate elements
(public member function of std::forward_list<T,Allocator>) [edit]
removes consecutive duplicate elements
(public member function of std::hive<T,Allocator>) [edit]

Web Proxy Viewer  |  New URL  |  Original Page