std::ranges::unique
Определён в заголовочном файле <algorithm> | ||
|---|---|---|
| Сигнатура вызова | ||
template< std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
std::indirect_equivalence_relation<std::projected<I, Proj>>
C = ranges::equal_to >
constexpr ranges::subrange<I>
unique( I first, S last, C comp = {}, Proj proj = {} );
| (1) | (начиная с C++20) |
template< ranges::forward_range R, class Proj = std::identity,
std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>>
C = ranges::equal_to >
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
unique( R&& r, C comp = {}, Proj proj = {} );
| (2) | (начиная с C++20) |
[first, last), и возвращает поддиапазон [ret, last), где ret — итератор за последним элементом нового конца диапазона.*(i - 1) и *i считаются эквивалентными, если std::invoke(comp, std::invoke(proj, *(i - 1)), std::invoke(proj, *i)) == true, где i — итератор в диапазоне [first + 1, last).r, как если бы в качестве first использовался ranges::begin(r), а в качестве last — ranges::end(r).Описанные на этой странице функциональные объекты, вызываемые как функции, являются функциональными объектами алгоритмов (неформально называемыми ниеблоидами), то есть:
- При вызове любого из них нельзя указывать явные списки аргументов шаблона.
- Ни один из них не виден при поиске, зависящем от аргументов.
- Если любой из них найден при обычном неквалифицированном поиске как имя слева от оператора вызова функции, поиск, зависящий от аргументов, подавляется.
Параметры
| first, last | - | пара итератор–сентинел, задающая диапазон обрабатываемых элементов |
| r | - | диапазон обрабатываемых элементов |
| comp | - | бинарный предикат для сравнения спроецированных элементов |
| proj | - | проекция, применяемая к элементам |
Возвращаемое значение
Возвращает {ret, last}, где ret — итератор за последним элементом нового конца диапазона.
Сложность
Для непустых диапазонов выполняется ровно ranges::distance(first, last) - 1 применений соответствующего предиката comp и не более чем вдвое больше применений любой проекции proj.
Примечания
Удаление выполняется сдвигом элементов диапазона (посредством перемещающего присваивания) таким образом, чтобы элементы, которые не нужно удалять, оказались в начале диапазона. Относительный порядок оставшихся элементов сохраняется, а физический размер контейнера не изменяется. Итераторы в [ret, last) (если таковые имеются) по-прежнему допускают разыменование, но сами элементы имеют неопределённые значения (согласно постусловию требования MoveAssignable).
После вызова ranges::unique иногда вызывают функцию-член контейнера erase, которая удаляет элементы с неопределёнными значениями и уменьшает физический размер контейнера до его нового логического размера. Эти два вызова вместе реализуют идиому Erase–remove.
Возможная реализация
struct unique_fn
{
template<std::permutable I, std::sentinel_for<I> S, class Proj = std::identity,
std::indirect_equivalence_relation<std::projected<I, Proj>>
C = ranges::equal_to>
constexpr ranges::subrange<I>
operator()(I first, S last, C comp = {}, Proj proj = {}) const
{
first = ranges::adjacent_find(first, last, comp, proj);
if (first == last)
return {first, first};
auto i {first};
++first;
while (++first != last)
if (!std::invoke(comp, std::invoke(proj, *i), std::invoke(proj, *first)))
*++i = ranges::iter_move(first);
return {++i, first};
}
template<ranges::forward_range R, class Proj = std::identity,
std::indirect_equivalence_relation<std::projected<ranges::iterator_t<R>, Proj>>
C = ranges::equal_to>
requires std::permutable<ranges::iterator_t<R>>
constexpr ranges::borrowed_subrange_t<R>
operator()(R&& r, C comp = {}, Proj proj = {}) const
{
return (*this)(ranges::begin(r), ranges::end(r),
std::move(comp), std::move(proj));
}
};
inline constexpr unique_fn unique {};
|
Пример
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>
struct id {
int i;
explicit id(int i) : i {i} {}
};
void print(id i, const auto& v)
{
std::cout << i.i << ") ";
std::ranges::for_each(v, [](auto const& e) { std::cout << e << ' '; });
std::cout << '\n';
}
int main()
{
// a vector containing several duplicated elements
std::vector<int> v {1, 2, 1, 1, 3, 3, 3, 4, 5, 4};
print(id {1}, v);
// remove consecutive (adjacent) duplicates
const auto ret = std::ranges::unique(v);
// v now holds {1 2 1 3 4 5 4 x x x}, where 'x' is indeterminate
v.erase(ret.begin(), ret.end());
print(id {2}, v);
// sort followed by unique, to remove all duplicates
std::ranges::sort(v); // {1 1 2 3 4 4 5}
print(id {3}, v);
const auto [first, last] = std::ranges::unique(v.begin(), v.end());
// v now holds {1 2 3 4 5 x x}, where 'x' is indeterminate
v.erase(first, last);
print(id {4}, v);
// unique with custom comparison and projection
std::vector<std::complex<int>> vc { {1, 1}, {-1, 2}, {-2, 3}, {2, 4}, {-3, 5} };
print(id {5}, vc);
const auto ret2 = std::ranges::unique(vc,
// consider two complex nums equal if their real parts are equal by module:
[](int x, int y) { return std::abs(x) == std::abs(y); }, // comp
[](std::complex<int> z) { return z.real(); } // proj
);
vc.erase(ret2.begin(), ret2.end());
print(id {6}, vc);
}
Вывод:
1) 1 2 1 1 3 3 3 4 5 4 2) 1 2 1 3 4 5 4 3) 1 1 2 3 4 4 5 4) 1 2 3 4 5 5) (1,1) (-1,2) (-2,3) (2,4) (-3,5) 6) (1,1) (-2,3) (-3,5)
См. также
|
(C++20) | создаёт копию части диапазона, не содержащую повторяющихся элементов, расположенных подряд (функциональный объект алгоритма) |
|
(C++20) | находит первые два соседних элемента, равных друг другу (или удовлетворяющих заданному предикату) (функциональный объект алгоритма) |
|
(C++20)(C++20) | удаляют элементы, удовлетворяющие определённым критериям (функциональный объект алгоритма) |
| удаляет повторяющиеся элементы, расположенные подряд, из диапазона (шаблон функции) |
|
| удаляет повторяющиеся элементы, расположенные подряд (открытая функция-член std::list<T,Allocator>) |
|
| удаляет повторяющиеся элементы, расположенные подряд (открытая функция-член std::forward_list<T,Allocator>) |
|
| удаляет повторяющиеся элементы, расположенные подряд (открытая функция-член std::hive<T,Allocator>) |
© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/ranges/unique