279 lines
16 KiB
Markdown
279 lines
16 KiB
Markdown
[alg.unique]
|
||
|
||
# 26 Algorithms library [[algorithms]](./#algorithms)
|
||
|
||
## 26.7 Mutating sequence operations [[alg.modifying.operations]](alg.modifying.operations#alg.unique)
|
||
|
||
### 26.7.9 Unique [alg.unique]
|
||
|
||
[ð](#lib: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](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<I> S, class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> C = ranges::equal_to>
|
||
constexpr subrange<I> ranges::unique(I first, S last, C comp = {}, Proj proj = {});
|
||
template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
|
||
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>>
|
||
constexpr borrowed_subrange_t<R>
|
||
ranges::unique(R&& r, C comp = {}, Proj proj = {});
|
||
|
||
template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<I> S,
|
||
class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> C = ranges::equal_to>
|
||
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<I>
|
||
subrange<I> ranges::unique(Ep&& exec, I first, S last, C comp = {}, Proj proj = {});
|
||
template<[execution-policy](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
|
||
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>>
|
||
borrowed_subrange_t<R> ranges::unique(Ep&& exec, R&& r, C comp = {}, Proj proj = {});
|
||
`
|
||
|
||
[1](#1)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7837)
|
||
|
||
Let pred be equal_to{} for the overloads with no parameter pred, and
|
||
let E be
|
||
|
||
- [(1.1)](#1.1)
|
||
|
||
bool(pred(*(i - 1), *i)) for the overloads in namespace std;
|
||
|
||
- [(1.2)](#1.2)
|
||
|
||
bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i))) for the overloads in namespace ranges[.](#1.sentence-1)
|
||
|
||
[2](#2)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7851)
|
||
|
||
*Preconditions*: For the overloads in namespace std,pred is an equivalence relation and
|
||
the type of *first meets
|
||
the [*Cpp17MoveAssignable*](utility.arg.requirements#:Cpp17MoveAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") requirements (Table [33](utility.arg.requirements#tab:cpp17.moveassignable "Table 33: Cpp17MoveAssignable requirements"))[.](#2.sentence-1)
|
||
|
||
[3](#3)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7858)
|
||
|
||
*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[.](#3.sentence-1)
|
||
|
||
[4](#4)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7865)
|
||
|
||
*Returns*: Let j be the end of the resulting range[.](#4.sentence-1)
|
||
|
||
Returns:
|
||
|
||
- [(4.1)](#4.1)
|
||
|
||
j for the overloads in namespace std[.](#4.1.sentence-1)
|
||
|
||
- [(4.2)](#4.2)
|
||
|
||
{j, last} for the overloads in namespace ranges[.](#4.2.sentence-1)
|
||
|
||
[5](#5)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7873)
|
||
|
||
*Complexity*: For nonempty ranges, exactly (last - first) - 1 applications
|
||
of the corresponding predicate and
|
||
no more than twice as many applications of any projection[.](#5.sentence-1)
|
||
|
||
[ð](#lib:unique_copy)
|
||
|
||
`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](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_iterator [iterator.concept.input]") I, [sentinel_for](iterator.concept.sentinel#concept:sentinel_for "24.3.4.7 Concept sentinel_for [iterator.concept.sentinel]")<I> S, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_incrementable [iterator.concept.winc]") O, class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> C = ranges::equal_to>
|
||
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]")<I, O> &&
|
||
([forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_iterator [iterator.concept.forward]")<I> ||
|
||
([input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_iterator [iterator.concept.input]")<O> && [same_as](concept.same#concept:same_as "18.4.2 Concept same_as [concept.same]")<iter_value_t<I>, iter_value_t<O>>) ||
|
||
[indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]")<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](range.refinements#concept:input_range "25.4.6 Other range refinements [range.refinements]") R, [weakly_incrementable](iterator.concept.winc#concept:weakly_incrementable "24.3.4.4 Concept weakly_incrementable [iterator.concept.winc]") O, class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
|
||
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]")<iterator_t<R>, O> &&
|
||
([forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_iterator [iterator.concept.forward]")<iterator_t<R>> ||
|
||
([input_iterator](iterator.concept.input#concept:input_iterator "24.3.4.9 Concept input_iterator [iterator.concept.input]")<O> && [same_as](concept.same#concept:same_as "18.4.2 Concept same_as [concept.same]")<range_value_t<R>, iter_value_t<O>>) ||
|
||
[indirectly_copyable_storable](alg.req.ind.copy#concept:indirectly_copyable_storable "24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]")<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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]") I, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<I> S,
|
||
[random_access_iterator](iterator.concept.random.access#concept:random_access_iterator "24.3.4.13 Concept random_access_iterator [iterator.concept.random.access]") O, [sized_sentinel_for](iterator.concept.sizedsentinel#concept:sized_sentinel_for "24.3.4.8 Concept sized_sentinel_for [iterator.concept.sizedsentinel]")<O> OutS, class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> C = ranges::equal_to>
|
||
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]")<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](algorithms.parallel.defns#concept:execution-policy "26.3.1 Preamble [algorithms.parallel.defns]") Ep, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") R, [sized-random-access-range](range.refinements#concept:sized-random-access-range "25.4.6 Other range refinements [range.refinements]") OutR,
|
||
class Proj = identity,
|
||
[indirect_equivalence_relation](indirectcallable.indirectinvocable#concept:indirect_equivalence_relation "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
|
||
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_copyable [alg.req.ind.copy]")<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](#6)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7937)
|
||
|
||
Let pred be equal_to{} for the overloads
|
||
in namespace std with no parameter pred, and
|
||
let E(i) be
|
||
|
||
- [(6.1)](#6.1)
|
||
|
||
bool(pred(*i, *(i - 1))) for the overloads in namespace std;
|
||
|
||
- [(6.2)](#6.2)
|
||
|
||
bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1)))) for the overloads in namespace ranges[.](#6.sentence-1)
|
||
|
||
[7](#7)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7951)
|
||
|
||
Let:
|
||
|
||
- [(7.1)](#7.1)
|
||
|
||
M be the number of iterators i in the range [first + 1, last)
|
||
for which E(i) is false;
|
||
|
||
- [(7.2)](#7.2)
|
||
|
||
result_last be result + M + 1 for the overloads with no parameter result_last or result_r;
|
||
|
||
- [(7.3)](#7.3)
|
||
|
||
N be min(M+1, result_last - result)[.](#7.sentence-1)
|
||
|
||
[8](#8)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7964)
|
||
|
||
*Mandates*: *first is writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General")) to result[.](#8.sentence-1)
|
||
|
||
[9](#9)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7968)
|
||
|
||
*Preconditions*:
|
||
|
||
- [(9.1)](#9.1)
|
||
|
||
The ranges [first, last) and [result, result + N)
|
||
do not overlap[.](#9.1.sentence-1)
|
||
|
||
- [(9.2)](#9.2)
|
||
|
||
For the overloads in namespace std:
|
||
* [(9.2.1)](#9.2.1)
|
||
|
||
The comparison function is an equivalence relation[.](#9.2.1.sentence-1)
|
||
|
||
* [(9.2.2)](#9.2.2)
|
||
|
||
For the overloads with no ExecutionPolicy,
|
||
let T be the value type of InputIterator[.](#9.2.2.sentence-1)
|
||
If InputIterator models [forward_iterator](iterator.concept.forward#concept:forward_iterator "24.3.4.11 Concept forward_iterator [iterator.concept.forward]") ([[iterator.concept.forward]](iterator.concept.forward "24.3.4.11 Concept forward_iterator")),
|
||
then there are no additional requirements for T[.](#9.2.2.sentence-2)
|
||
Otherwise, if OutputIterator meets
|
||
the [*Cpp17ForwardIterator*](forward.iterators#:Cpp17ForwardIterator "24.3.5.5 Forward iterators [forward.iterators]") requirements and
|
||
its value type is the same as T,
|
||
then T meets
|
||
the [*Cpp17CopyAssignable*](utility.arg.requirements#:Cpp17CopyAssignable "16.4.4.2 Template argument requirements [utility.arg.requirements]") (Table [34](utility.arg.requirements#tab:cpp17.copyassignable "Table 34: Cpp17CopyAssignable requirements (in addition to Cpp17MoveAssignable)")) requirements[.](#9.2.2.sentence-3)
|
||
Otherwise, T meets both
|
||
the *Cpp17CopyConstructible* (Table [32](utility.arg.requirements#tab:cpp17.copyconstructible "Table 32: Cpp17CopyConstructible requirements (in addition to Cpp17MoveConstructible)")) and *Cpp17CopyAssignable* requirements[.](#9.2.2.sentence-4)
|
||
|
||
[*Note [1](#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[.](#9.sentence-2)
|
||
|
||
For the parallel algorithm overloads in namespace ranges,
|
||
there can be a performance cost if iter_value_t<I> does not model [copyable](concepts.object#concept:copyable "18.6 Object concepts [concepts.object]")[.](#9.sentence-3)
|
||
|
||
â *end note*]
|
||
|
||
[10](#10)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8005)
|
||
|
||
*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)[.](#10.sentence-1)
|
||
|
||
[11](#11)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8012)
|
||
|
||
*Returns*:
|
||
|
||
- [(11.1)](#11.1)
|
||
|
||
result + N for the overloads in namespace std[.](#11.1.sentence-1)
|
||
|
||
- [(11.2)](#11.2)
|
||
|
||
{last, result + N} for the overloads in namespace ranges,
|
||
if N is equal to M+1[.](#11.2.sentence-1)
|
||
|
||
- [(11.3)](#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 Nâ1 iterators i in [first + 1, j)
|
||
for which E(i) is false[.](#11.3.sentence-1)
|
||
|
||
[12](#12)
|
||
|
||
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L8031)
|
||
|
||
*Complexity*: At most last - first - 1 applications
|
||
of the corresponding predicate
|
||
and no more than twice as many applications of any projection[.](#12.sentence-1)
|