std::ranges::remove, std::ranges::remove_if
Определено в заголовочном файле <algorithm> | ||
|---|---|---|
| Сигнатура вызова | ||
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) |
(начиная с C++20) (до 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 = {} );
| (начиная с 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) |
(начиная с C++20) (до 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 = {} );
| (начиная с 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) | (начиная с 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) | (начиная с C++20) |
Удаляет из диапазона [first, last) все элементы, удовлетворяющие заданным критериям, и возвращает поддиапазон [ret, last), где ret — итератор за последним элементом нового конца диапазона.
value, используя для сравнения std::invoke(proj, *i) == value.std::invoke(pred, std::invoke(proj, *i)) возвращает true.r, как если бы в качестве first использовался ranges::begin(r), а в качестве last — ranges::end(r).Удаление выполняется путём сдвига элементов диапазона (с помощью перемещающего присваивания) таким образом, чтобы элементы, которые не нужно удалять, оказались в начале диапазона. Относительный порядок оставшихся элементов сохраняется, а физический размер контейнера не изменяется. Итераторы, указывающие на элементы между новым логическим концом и физическим концом диапазона, по-прежнему допускают разыменование, однако сами элементы имеют неуказанные значения (согласно постусловию требования MoveAssignable).
Описанные на этой странице сущности, подобные функциям, являются функциональными объектами алгоритмов (неформально называемыми niebloids), то есть:
- При вызове любой из них нельзя указать явный список аргументов шаблона.
- Ни одна из них не видна при поиске с учётом аргументов.
- Если какая-либо из них найдена при обычном поиске неквалифицированного имени в качестве имени слева от оператора вызова функции, поиск с учётом аргументов подавляется.
Параметры
| first, last | - | пара итератора и сентинела, задающая диапазон обрабатываемых элементов |
| r | - | диапазон обрабатываемых элементов |
| value | - | значение элементов, которые нужно удалить |
| pred | - | предикат, применяемый к спроецированным элементам |
| proj | - | проекция, применяемая к элементам |
Возвращаемое значение
{ret, last}, где [first, ret) — результирующий поддиапазон после удаления, а все элементы поддиапазона [ret, last) находятся в допустимом, но неуказанном состоянии, то есть [ret, last) — поддиапазон, который следует стереть.
Сложность
Ровно N вызовов соответствующего предиката и любой проекции, где N = ranges::distance(first, last), и не более N - 1 операций перемещения.
Примечания
За вызовом ranges::remove обычно следует вызов функции-члена контейнера erase, которая стирает элементы с неуказанными значениями и уменьшает физический размер контейнера до нового логического размера. Эти два вызова вместе составляют так называемый идиому erase-remove, которую можно реализовать с помощью свободной функции std::erase, имеющей перегрузки для всех стандартных последовательных контейнеров, или std::erase_if, имеющей перегрузки для всех стандартных контейнеров.
Одноимённые функции-члены контейнеров list::remove, list::remove_if, forward_list::remove и forward_list::remove_if стирают удалённые элементы.
Эти алгоритмы обычно нельзя использовать с ассоциативными контейнерами, такими как std::set и std::map, поскольку их типы итераторов не разыменовываются в типы, удовлетворяющие требованию MoveAssignable (ключи в этих контейнерах нельзя изменять).
Поскольку ranges::remove принимает value по ссылке, поведение может быть неожиданным, если это ссылка на элемент диапазона [first, last).
Возможная реализация
| remove (1,2) |
|---|
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::end(r), value, std::move(proj));
}
};
inline constexpr remove_fn remove {};
|
| remove_if (3,4) |
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::end(r), pred, std::move(proj));
}
};
inline constexpr remove_if_fn remove_if {};
|
Примечания
| Макрос проверки поддержки возможностей | Значение | Стандарт | Возможность |
|---|---|---|---|
__cpp_lib_algorithm_default_value_type | 202403 | (C++26) | Инициализация списком для алгоритмов (1,2) |
Пример
#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}}));
}
Возможный вывод:
"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
См. также
|
(C++20)(C++20) | копирует диапазон элементов, пропуская те, которые удовлетворяют заданным критериям (функциональный объект алгоритма) |
|
(C++20) | удаляет повторяющиеся подряд элементы в диапазоне (функциональный объект алгоритма) |
| удаляет элементы, удовлетворяющие заданным критериям (шаблон функции) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/remove
