Spec-Zone.ru › C++

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)
1) Удаляет все элементы, кроме первого, из каждой последовательной группы эквивалентных элементов из диапазона [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).
2) То же, что (1), но использует r в качестве диапазона, как если бы использовалось ranges::begin(r) в качестве first, и ranges::end(r) в качестве last.

Функциональные сущности, описанные на этой странице, являются неблоидами, то есть:

  • Явные списки аргументов шаблона не могут быть указаны при их вызове.
  • Ни один из них не виден для поиска аргументов по зависимости.
  • При обнаружении любого из них обычным поиском без квалификатора в качестве имени слева от оператора вызова функции, поиск аргументов по зависимости запрещен.

На практике они могут быть реализованы как объекты функций или с помощью специальных расширений компилятора.

Параметры

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)

См. также

ranges::unique_copy
(C++20)
создаёт копию диапазона элементов, не содержащую последовательных дубликатов
(неблоид)
ranges::adjacent_find
(C++20)
находит первые два смежных элемента, которые равны (или удовлетворяют заданному предикату)
(неблоид)
ranges::removeranges::remove_if
(C++20)(C++20)
удаляет элементы, удовлетворяющие определённым критериям
(неблоид)
unique
удаляет последовательные дублирующие элементы в диапазоне
(шаблон функции)
unique
удаляет последовательные дублирующие элементы
(публичный член-функция std::list<T,Allocator>)
unique
удаляет последовательные дублирующие элементы
(публичный член-функция std::forward_list<T,Allocator>)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/w/cpp/algorithm/ranges/unique

Spec-Zone.ru

Настройки Оффлайн Что нового Помощь О нас
Spec-Zone .ru
спецификации, руководства, описания, API