std::ranges::remove, std::ranges::remove_if
From cppreference.com
| Defined in header <algorithm>
|
||
| Call signature |
||
template< std::permutable I, std::sentinel_for<I> S,
class T, class Proj = std::identity >
requires std::indirect_binary_predicate
<ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr ranges::subrange<I>
remove( I first, S last, const T& value, Proj proj = {} );
|
(1) | (since C++20) (until C++26) |
template< std::permutable I, std::sentinel_for<I> S,
class Proj = std::identity,
class T = std::projected_value_t<I, Proj> >
requires std::indirect_binary_predicate
<ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr ranges::subrange<I>
remove( I first, S last, const T& value, Proj proj = {} );
|
(since C++26) | |
template< ranges::forward_range R,
class T, class Proj = std::identity >
requires std::permutable<ranges::iterator_t<R>> &&
std::indirect_binary_predicate
<ranges::equal_to,
std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr ranges::borrowed_subrange_t<R>
remove( R&& r, const T& value, Proj proj = {} );
|
(2) | (since C++20) (until C++26) |
template< ranges::forward_range R,
class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
requires std::permutable<ranges::iterator_t<R>> &&
std::indirect_binary_predicate
<ranges::equal_to,
std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr ranges::borrowed_subrange_t<R>
remove( R&& r, const T& value, Proj proj = {} );
|
(since C++26) | |
template< std::permutable I, std::sentinel_for<I> S,
class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
constexpr ranges::subrange<I>
remove_if( I first, S last, Pred pred, Proj proj = {} );
|
(3) | (since C++20) |
template< ranges::forward_range R,
class Proj = std::identity,
std::indirect_unary_predicate
<std::projected<ranges::iterator_t<R>, Proj>> Pred >
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
remove_if( R&& r, Pred pred, Proj proj = {} );
|
(4) | (since C++20) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I, std::sized_sentinel_for<I> S,
class Proj = std::identity,
class T = std::projected_value_t<I, Proj> >
requires std::permutable<I> &&
std::indirect_binary_predicate
<ranges::equal_to, std::projected<I, Proj>, const T*>
ranges::subrange<I>
remove( Ep&& policy, I first, S last, const T& value, Proj proj = {} );
|
(5) | (since C++26) |
template< /*execution-policy*/ Ep,
/*sized-random-access-range*/ R,
class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj> >
requires std::permutable<ranges::iterator_t<R>> &&
std::indirect_binary_predicate
<ranges::equal_to,
std::projected<ranges::iterator_t<R>, Proj>, const T*>
ranges::borrowed_subrange_t<R>
remove( Ep&& policy, R&& r, const T& value, Proj proj = {} );
|
(6) | (since C++26) |
template< /*execution-policy*/ Ep,
std::random_access_iterator I, std::sized_sentinel_for<I> S,
class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred >
requires std::permutable<I>
ranges::subrange<I>
remove_if( Ep&& policy, I first, S last, Pred pred, Proj proj = {} );
|
(7) | (since C++26) |
template< /*execution-policy*/ Ep,
/*sized-random-access-range*/ R,
class Proj = std::identity,
std::indirect_unary_predicate
<std::projected<ranges::iterator_t<R>, Proj>> Pred >
requires std::permutable<ranges::iterator_t<R>>
ranges::borrowed_subrange_t<R>
remove_if( Ep&& policy, R&& r, Pred pred, Proj proj = {} );
|
(8) | (since C++26) |
For the definition of /*execution-policy*/, see this page; for the definition of /*sized-random-access-range*/, see this page.
Removes all elements (projected by proj) satisfying specific criteria from the target range [first, last) or r.
1,2)
remove removes all elements that are equal to value (using operator==).3,4)
remove_if removes all elements for which predicate p returns true.5-8) Same as (1-4), but executed according to
policy.Removing is done by partitioning the elements in the target range. Given the partition point result, all elements that are not to be removed 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
resulthas 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:
- Explicit template argument lists cannot be specified when calling any of them.
- None of them are visible to argument-dependent lookup.
- When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.
Parameters
| first, last | - | the iterator-sentinel pair defining the target range |
| r | - | the target range |
| value | - | the value of elements to remove |
| pred | - | 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 N\)N comparisons with
value using operator==, and the same number of applications of proj.3,4) Exactly \(\scriptsize N\)N applications of
pred and proj.5,6) \(\scriptsize \mathcal{O}(N)\)(N) comparisons with
value using operator==, and the same number of applications of proj.7,8) \(\scriptsize \mathcal{O}(N)\)(N) applications of
pred and proj.Exceptions
5-8) 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::remove or ranges::remove_if 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.
The same effect can also be achieved by the following non-member functions:
- std::erase, which has overloads for all standard sequence containers.
- std::erase_if, which has overloads for all standard containers.
The similarly-named container member functions list::remove, list::remove_if, forward_list::remove, and forward_list::remove_if erase the removed elements.
These algorithms cannot be used with associative containers such as std::set and std::map because their iterator types do not dereference to MoveAssignable types (the keys in these containers are not modifiable).
Because ranges::remove takes value by reference, it can have unexpected behavior if it is a reference to an element of the target range.
| Feature-test macro | Value | Std | Feature |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type |
202403 |
(C++26) | List-initialization for algorithms (1,2) |
Possible implementation
| remove |
|---|
struct remove_fn
{
template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
class T = std::projected_value_t<I, Proj>>
requires std::indirect_binary_predicate
<ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr ranges::subrange<I>
operator()(I first, S last, const T& value, Proj proj = {}) const
{
first = ranges::find(std::move(first), last, value, proj);
if (first != last)
{
for (I i{std::next(first)}; i != last; ++i)
if (value != std::invoke(proj, *i))
{
*first = ranges::iter_move(i);
++first;
}
}
return {first, last};
}
template<ranges::forward_range R, class Proj = std::identity,
class T = std::projected_value_t<ranges::iterator_t<R>, Proj>>
requires std::permutable<ranges::iterator_t<R>> &&
std::indirect_binary_predicate
<ranges::equal_to,
std::projected<ranges::iterator_t<R>, Proj>, const T*>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, const T& value, Proj proj = {}) const
{
return (*this)(ranges::begin(r),
ranges::next(ranges::begin(r), ranges::end(r)),
value, std::move(proj));
}
};
inline constexpr remove_fn remove{};
|
| remove_if |
struct remove_if_fn
{
template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
std::indirect_unary_predicate<std::projected<I, Proj>> Pred>
constexpr ranges::subrange<I>
operator()(I first, S last, Pred pred, Proj proj = {}) const
{
first = ranges::find_if(std::move(first), last, pred, proj);
if (first != last)
{
for (I i{std::next(first)}; i != last; ++i)
if (!std::invoke(pred, std::invoke(proj, *i)))
{
*first = ranges::iter_move(i);
++first;
}
}
return {first, last};
}
template<ranges::forward_range R, class Proj = std::identity,
std::indirect_unary_predicate
<std::projected<ranges::iterator_t<R>, Proj>> Pred>
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, Pred pred, Proj proj = {}) const
{
return (*this)(ranges::begin(r),
ranges::next(ranges::begin(r), ranges::end(r)),
pred, std::move(proj));
}
};
inline constexpr remove_if_fn remove_if{};
|
Example
Run this code
#include <algorithm>
#include <cassert>
#include <complex>
#include <cctype>
#include <iomanip>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>
int main()
{
std::string v1{"No - Diagnostic - Required"};
std::cout << std::quoted(v1) << " (v1, size: " << v1.size() << ")\n";
const auto ret = std::ranges::remove(v1, ' ');
std::cout << std::quoted(v1) << " (v1 after remove, size: " << v1.size() << ")\n";
std::cout << ' ' << std::string(std::distance(v1.begin(), ret.begin()), '^') << '\n';
v1.erase(ret.begin(), ret.end());
std::cout << std::quoted(v1) << " (v1 after erase, size: " << v1.size() << ")\n\n";
// remove_if with custom unary predicate:
auto rm = [](char c) { return !std::isupper(c); };
std::string v2{"Substitution Failure Is Not An Error"};
std::cout << std::quoted(v2) << " (v2, size: " << v2.size() << ")\n";
const auto [first, last] = std::ranges::remove_if(v2, rm);
std::cout << std::quoted(v2) << " (v2 after remove_if, size: " << v2.size() << ")\n";
std::cout << ' ' << std::string(std::distance(v2.begin(), first), '^') << '\n';
v2.erase(first, last);
std::cout << std::quoted(v2) << " (v2 after erase, size: " << v2.size() << ")\n\n";
// creating a view into a container that is modified by remove_if:
for (std::string s : {"Small Object Optimization", "Non-Type Template Parameter"})
std::cout << std::quoted(s) << " => "
<< std::string_view{begin(s), std::ranges::remove_if(s, rm).begin()} << '\n';
std::vector<std::complex<double>> nums{{2, 2}, {1, 3}, {4, 8}};
#ifdef __cpp_lib_algorithm_default_value_type
auto e = std::ranges::remove(nums, {1, 3}); // T gets deduced
#else
auto e = std::ranges::remove(nums, std::complex<double>{1, 3});
#endif
nums.erase(e.begin(), e.end());
assert((nums == std::vector<std::complex<double>>{{2, 2}, {4, 8}}));
}
Possible output:
"No _ Diagnostic _ Required" (v1, size: 26)
"No_Diagnostic_Requiredired" (v1 after remove, size: 26)
^^^^^^^^^^^^^^^^^^^^^^
"No_Diagnostic_Required" (v1 after erase, size: 22)
"Substitution Failure Is Not An Error" (v2, size: 36)
"SFINAEtution Failure Is Not An Error" (v2 after remove_if, size: 36)
^^^^^^
"SFINAE" (v2 after erase, size: 6)
"Small Object Optimization" => SOO
"Non-Type Template Parameter" => NTTP
See also
| removes elements satisfying specific criteria (function template) | |
(C++20)(C++20) |
copies a range of elements omitting those that satisfy specific criteria (algorithm function object) |
(C++20) |
removes consecutive duplicate elements in a range (algorithm function object) |