depish/cppdraft_translate
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
cppdraft_translate/cppdraft/alg/remove.md
Leonov Artur (Depish) 043225d523 Init
2025-10-25 03:02:53 +03:00

340 lines
22 KiB
Markdown
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

[alg.remove]
# 26 Algorithms library [[algorithms]](./#algorithms)
## 26.7 Mutating sequence operations [[alg.modifying.operations]](alg.modifying.operations#alg.remove)
### 26.7.8 Remove [alg.remove]
[🔗](#lib:remove)
`template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
constexpr ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ExecutionPolicy, class ForwardIterator,
class T = iterator_traits<ForwardIterator>::value_type>
ForwardIterator remove(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class Predicate>
constexpr ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
template<class ExecutionPolicy, class ForwardIterator, class Predicate>
ForwardIterator remove_if(ExecutionPolicy&& exec,
ForwardIterator first, ForwardIterator last,
Predicate 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,
class T = projected_value_t<I, Proj>>
requires [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T*>
constexpr subrange<I> ranges::remove(I first, S last, const T& value, Proj proj = {});
template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
class T = projected_value_t<iterator_t<R>, Proj>>
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>> &&
[indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr borrowed_subrange_t<R>
ranges::remove(R&& r, const T& value, 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, class T = projected_value_t<I, Proj>>
requires [indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T*>
subrange<I>
ranges::remove(Ep&& exec, I first, S last, const T& value, 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,
class T = projected_value_t<iterator_t<R>, Proj>>
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>> &&
[indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
borrowed_subrange_t<R>
ranges::remove(Ep&& exec, R&& r, const T& value, Proj proj = {});
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_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
constexpr subrange<I> ranges::remove_if(I first, S last, Pred pred, Proj proj = {});
template<[forward_range](range.refinements#concept:forward_range "25.4.6 Other range refinements [range.refinements]") R, class Proj = identity,
[indirect_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
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::remove_if(R&& r, Pred pred, 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_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
subrange<I>
ranges::remove_if(Ep&& exec, I first, S last, Pred pred, 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_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
requires [permutable](alg.req.permutable#concept:permutable "24.3.7.6 Concept permutable [alg.req.permutable]")<iterator_t<R>>
borrowed_subrange_t<R>
ranges::remove_if(Ep&& exec, R&& r, Pred pred, Proj proj = {});
`
[1](#1)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7594)
Let E be
- [(1.1)](#1.1)
bool(*i == value) for remove;
- [(1.2)](#1.2)
bool(pred(*i)) for remove_if;
- [(1.3)](#1.3)
bool(invoke(proj, *i) == value) for ranges​::​remove;
- [(1.4)](#1.4)
bool(invoke(pred, invoke(proj, *i))) for ranges​::​remove_if[.](#1.sentence-1)
[2](#2)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7603)
*Preconditions*: For the algorithms in namespace std,
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#L7609)
*Effects*: Eliminates all the elements referred to by iterator i in the range [first, last) for which E holds[.](#3.sentence-1)
[4](#4)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7614)
*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#L7622)
*Complexity*: Exactly last - first applications
of the corresponding predicate and any projection[.](#5.sentence-1)
[6](#6)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7627)
*Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#6.sentence-1)
[7](#7)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7631)
[*Note [1](#note-1)*:
Each element in the range [ret, last),
where ret is the returned value,
has a valid but unspecified state,
because the algorithms can eliminate elements
by moving from elements that were originally in that range[.](#7.sentence-1)
— *end note*]
[🔗](#lib:remove_copy)
`template<class InputIterator, class OutputIterator,
class T = iterator_traits<InputIterator>::value_type>
constexpr OutputIterator
remove_copy(InputIterator first, InputIterator last,
OutputIterator result, const T& value);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class T = iterator_traits<ForwardIterator1>::value_type>
ForwardIterator2
remove_copy(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, const T& value);
template<class InputIterator, class OutputIterator, class Predicate>
constexpr OutputIterator
remove_copy_if(InputIterator first, InputIterator last,
OutputIterator result, Predicate pred);
template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
class Predicate>
ForwardIterator2
remove_copy_if(ExecutionPolicy&& exec,
ForwardIterator1 first, ForwardIterator1 last,
ForwardIterator2 result, Predicate 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, class T = projected_value_t<I, Proj>>
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O> &&
[indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T*>
constexpr ranges::remove_copy_result<I, O>
ranges::remove_copy(I first, S last, O result, const T& value, 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,
class T = projected_value_t<iterator_t<R>, Proj>>
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> &&
[indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
constexpr ranges::remove_copy_result<borrowed_iterator_t<R>, O>
ranges::remove_copy(R&& r, O result, const T& value, 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, class T = projected_value_t<I, Proj>>
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O> &&
[indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to, projected<I, Proj>, const T*>
ranges::remove_copy_result<I, O>
ranges::remove_copy(Ep&& exec, I first, S last, O result, OutS result_last,
const T& value, 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, class T = projected_value_t<iterator_t<R>, Proj>>
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>> &&
[indirect_binary_predicate](indirectcallable.indirectinvocable#concept:indirect_binary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<ranges::equal_to,
projected<iterator_t<R>, Proj>, const T*>
ranges::remove_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
ranges::remove_copy(Ep&& exec, R&& r, OutR&& result_r, const T& value, Proj proj = {});
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_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O>
constexpr ranges::remove_copy_if_result<I, O>
ranges::remove_copy_if(I first, S last, O result, Pred pred, 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_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
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>
constexpr ranges::remove_copy_if_result<borrowed_iterator_t<R>, O>
ranges::remove_copy_if(R&& r, O result, Pred pred, 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_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<I, Proj>> Pred>
requires [indirectly_copyable](alg.req.ind.copy#concept:indirectly_copyable "24.3.7.3 Concept indirectly_­copyable [alg.req.ind.copy]")<I, O>
ranges::remove_copy_if_result<I, O>
ranges::remove_copy_if(Ep&& exec, I first, S last, O result, OutS result_last,
Pred pred, 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_unary_predicate](indirectcallable.indirectinvocable#concept:indirect_unary_predicate "24.3.6.3 Indirect callables [indirectcallable.indirectinvocable]")<projected<iterator_t<R>, Proj>> Pred>
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::remove_copy_if_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR>>
ranges::remove_copy_if(Ep&& exec, R&& r, OutR&& result_r, Pred pred, Proj proj = {});
`
[8](#8)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7723)
Let E(i) be
- [(8.1)](#8.1)
bool(*i == value) for remove_copy;
- [(8.2)](#8.2)
bool(pred(*i)) for remove_copy_if;
- [(8.3)](#8.3)
bool(invoke(proj, *i) == value) for ranges​::​remove_copy;
- [(8.4)](#8.4)
bool(invoke(pred, invoke(proj, *i))) for ranges​::​remove_copy_if[.](#8.sentence-1)
[9](#9)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7732)
Let:
- [(9.1)](#9.1)
M be the number of iterators i in [first, last)
for which E(i) is false;
- [(9.2)](#9.2)
result_last be result + M for the overloads with no parameter result_last or result_r;
- [(9.3)](#9.3)
N be min(M, result_last - result)[.](#9.sentence-1)
[10](#10)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7745)
*Mandates*: *first is writable ([[iterator.requirements.general]](iterator.requirements.general "24.3.1 General")) to result[.](#10.sentence-1)
[11](#11)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7749)
*Preconditions*: The ranges [first, last) and [result, result + N)
do not overlap[.](#11.sentence-1)
[*Note [2](#note-2)*:
For the parallel algorithm overloads in namespace std,
there can be a performance cost
if iterator_traits<ForwardIterator1>​::​value_type does not meet
the *Cpp17MoveConstructible* (Table [31](utility.arg.requirements#tab:cpp17.moveconstructible "Table 31: Cpp17MoveConstructible requirements")) requirements[.](#11.sentence-2)
For the parallel algorithm overloads in namespace ranges,
there can be a performance cost
if iter_value_t<I> does not model [move_constructible](concept.moveconstructible#concept:move_constructible "18.4.13 Concept move_­constructible [concept.moveconstructible]")[.](#11.sentence-3)
— *end note*]
[12](#12)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7763)
*Effects*: Copies the first N elements referred to by the iterator i in the range [first, last) for which E(i) is false into the range [result, result + N)[.](#12.sentence-1)
[13](#13)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7769)
*Returns*:
- [(13.1)](#13.1)
result + N,
for the algorithms in namespace std[.](#13.1.sentence-1)
- [(13.2)](#13.2)
{last, result + N},
for the algorithms in namespace ranges,
if N is equal to M[.](#13.2.sentence-1)
- [(13.3)](#13.3)
Otherwise, {j, result_last},
for the algorithms in namespace ranges,
where j is the iterator in [first, last)
for which E(j) is false and there are exactly N iterators i in [first, j)
for which E(i) is false[.](#13.3.sentence-1)
[14](#14)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7788)
*Complexity*: At most last - first applications
of the corresponding predicate and any projection[.](#14.sentence-1)
[15](#15)
[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/algorithms.tex#L7793)
*Remarks*: Stable ([[algorithm.stable]](algorithm.stable "16.4.6.8 Requirements for stable algorithms"))[.](#15.sentence-1)
Reference in New Issue View Git Blame Copy Permalink