26 Algorithms library [algorithms]

26.7 Mutating sequence operations [alg.modifying.operations]

26.7.9 Unique [alg.unique]

🔗
template<class ForwardIterator> constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last); template<class ExecutionPolicy, class ForwardIterator> ForwardIterator unique(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, BinaryPredicate pred); template<permutable I, sentinel_for<I> S, class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> constexpr subrange<I> ranges::unique(I first, S last, C comp = {}, Proj proj = {}); template<forward_range R, class Proj = identity, indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> requires permutable<iterator_t<R>> constexpr borrowed_subrange_t<R> ranges::unique(R&& r, C comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> requires permutable<I> subrange<I> ranges::unique(Ep&& exec, I first, S last, C comp = {}, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, class Proj = identity, indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> requires permutable<iterator_t<R>> borrowed_subrange_t<R> ranges::unique(Ep&& exec, R&& r, C comp = {}, Proj proj = {});
1
#
Let pred be equal_to{} for the overloads with no parameter pred, and let E be
  • (1.1)
    bool(pred(*(i - 1), *i)) for the overloads in namespace std;
  • (1.2)
    bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i))) for the overloads in namespace ranges.
2
#
Preconditions: For the overloads in namespace std, pred is an equivalence relation and the type of *first meets the Cpp17MoveAssignable requirements (Table 33).
3
#
Effects: For a nonempty range, eliminates all but the first element from every consecutive group of equivalent elements referred to by the iterator i in the range [first + 1, last) for which E is true.
4
#
Returns: Let j be the end of the resulting range.
Returns:
  • (4.1)
    j for the overloads in namespace std.
  • (4.2)
    {j, last} for the overloads in namespace ranges.
5
#
Complexity: For nonempty ranges, exactly (last - first) - 1 applications of the corresponding predicate and no more than twice as many applications of any projection.
🔗
template<class InputIterator, class OutputIterator> constexpr OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2> ForwardIterator2 unique_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result); template<class InputIterator, class OutputIterator, class BinaryPredicate> constexpr OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred); template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator2 unique_copy(ExecutionPolicy&& exec, ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 result, BinaryPredicate pred); template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> requires 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>) constexpr ranges::unique_copy_result<I, O> ranges::unique_copy(I first, S last, O result, C comp = {}, Proj proj = {}); template<input_range R, weakly_incrementable O, class Proj = identity, indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> requires indirectly_copyable<iterator_t<R>, O> && (forward_iterator<iterator_t<R>> || (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) || indirectly_copyable_storable<iterator_t<R>, O>) constexpr ranges::unique_copy_result<borrowed_iterator_t<R>, O> ranges::unique_copy(R&& r, O result, C comp = {}, Proj proj = {}); template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S, random_access_iterator O, sized_sentinel_for<O> OutS, class Proj = identity, indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to> requires indirectly_copyable<I, O> ranges::unique_copy_result<I, O> ranges::unique_copy(Ep&& exec, I first, S last, O result, OutS result_last, C comp = {}, Proj proj = {}); template<execution-policy Ep, sized-random-access-range R, sized-random-access-range OutR, class Proj = identity, indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to> requires indirectly_copyable<iterator_t<R>, iterator_t<OutR>> ranges::unique_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>> ranges::unique_copy(Ep&& exec, R&& r, OutR&& result_r, C comp = {}, Proj proj = {});
6
#
Let pred be equal_to{} for the overloads in namespace std with no parameter pred, and let E(i) be
  • (6.1)
    bool(pred(*i, *(i - 1))) for the overloads in namespace std;
  • (6.2)
    bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1)))) for the overloads in namespace ranges.
7
#
Let:
  • (7.1)
    M be the number of iterators i in the range [first + 1, last) for which E(i) is false;
  • (7.2)
    result_last be result + M + 1 for the overloads with no parameter result_last or result_r;
  • (7.3)
    N be .
8
#
Mandates: *first is writable ([iterator.requirements.general]) to result.
9
#
Preconditions:
  • (9.1)
    The ranges [first, last) and [result, result + N) do not overlap.
  • (9.2)
    For the overloads in namespace std:
    • (9.2.1)
      The comparison function is an equivalence relation.
    • (9.2.2)
      For the overloads with no ExecutionPolicy, let T be the value type of InputIterator.
      If InputIterator models forward_iterator ([iterator.concept.forward]), then there are no additional requirements for T.
      Otherwise, if OutputIterator meets the Cpp17ForwardIterator requirements and its value type is the same as T, then T meets the Cpp17CopyAssignable (Table 34) requirements.
      Otherwise, T meets both the Cpp17CopyConstructible (Table 32) and Cpp17CopyAssignable requirements.
[Note 1: 
For the parallel algorithm overloads in namespace std, there can be a performance cost if the value type of ForwardIterator1 does not meet both the Cpp17CopyConstructible and Cpp17CopyAssignable requirements.
For the parallel algorithm overloads in namespace ranges, there can be a performance cost if iter_value_t<I> does not model copyable.
— end note]
10
#
Effects: Copies only the first element from N consecutive groups of equivalent elements referred to by the iterator i in the range [first + 1, last) for which E(i) holds into the range [result, result + N).
11
#
Returns:
  • (11.1)
    result + N for the overloads in namespace std.
  • (11.2)
    {last, result + N} for the overloads in namespace ranges, if N is equal to .
  • (11.3)
    Otherwise, {j, result_last} for the overloads in namespace ranges, where j is the iterator in [first + 1, last) for which E(j) is false and there are exactly iterators i in [first + 1, j) for which E(i) is false.
12
#
Complexity: At most last - first - 1 applications of the corresponding predicate and no more than twice as many applications of any projection.