Пространства имён
Варианты
Действия

std::unique

Материал из cppreference.com
< cpp‎ | algorithm
 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека C
 
Определено в заголовочном файле <algorithm>
template< class ForwardIt >
ForwardIt unique( ForwardIt first, ForwardIt last );
(1)
template< class ForwardIt, class BinaryPredicate >
ForwardIt unique( ForwardIt first, ForwardIt last, BinaryPredicate p );
(2)

Удаляет все последовательно повторяющиеся элементы из диапазона [first, last) и возвращает итератор на элемент, следующий за последним элементом нового диапазона. Первая версия использует operator== для сравнения элементов, вторая версия использует предоставленный бинарный предикат p.

Удаление производится путем сдвига диапазона таким образом, что элементы которые должны быть удалены будут перезаписаны. Относительный порядок элементов сохраняется и настоящий размер контейнера не изменяется. Итераторы, указывающие на элементы после нового диапазона становятся недействительными, а значение этих элементов становится неопределённым. Вызов функции unique обычно продолжает вызов метода erase у контейнера, который удаляет неопределённые значения.

Содержание

[править] Параметры

first, last - диапазон элементов для обработки
p - бинарный предикат, который возвращает ​true если элементы следует считать равными.

Определение функции предиката должно быть эквивалентно следующему:

 bool pred(const Type1 &a, const Type2 &b);

Определение не должно обязательно содержать const &, но функция не должна модифицировать принимаемые объекты.
Типы Type1 и Type2 должны быть таковы, что объект типа ForwardIt может быть разыменован и затем неявно преобразован в оба из них.

Требования к типам
-
ForwardIt должен соответствовать требованиям ForwardIterator.
-
The type of dereferenced ForwardIt must meet the requirements of MoveAssignable.

[править] Возвращаемое значение

ForwardIterator на новый конец диапазона

[править] Сложность

Для непустых диапазонов ровно std::distance(first,last) - 1 применений соответствующего предиката.

[править] Возможная реализация

Первый вариант
template<class ForwardIt>
ForwardIt unique(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return last;
 
    ForwardIt result = first;
    while (++first != last) {
        if (!(*result == *first)) {
            *(++result) = *first;
        }
    }
    return ++result;
}
Второй вариант
template<class ForwardIt, class BinaryPredicate>
ForwardIt unique(ForwardIt first, ForwardIt last,
                       BinaryPredicate p)
{
    if (first == last)
        return last;
 
    ForwardIt result = first;
    while (++first != last) {
        if (!p(*result, *first)) {
            *(++result) = *first;
        }
    }
    return ++result;
}

[править] Пример

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cctype>
 
int main() 
{
    // удаление повторяющихся элементов (обычное использование)
    std::vector<int> v{1,2,3,1,2,3,3,4,5,4,5,6,7};
    std::sort(v.begin(), v.end()); // 1 1 2 2 3 3 3 4 4 5 5 6 7 
    auto last = std::unique(v.begin(), v.end());
    // v сейчас содержит {1 2 3 4 5 6 7 x x x x x x}, где 'x' обозначает неопределённый элемент
    v.erase(last, v.end()); 
    for (int i : v)
      std::cout << i << " ";
    std::cout << "\n";
 
    // удаление последовательных повторяющихся пробелов
    std::string s = "wanna go    to      space?";
    auto end = std::unique(s.begin(), s.end(), [](char l, char r){
        return std::isspace(l) && std::isspace(r) && l == r;
    });
    // s сейчас содержит "wanna go to space?xxxxxxxx", где 'x' обозначает неопределённый символ
    std::cout << std::string(s.begin(), end) << '\n';
}

Вывод:

1 2 3 4 5 6 7
wanna go to space?

[править] См. также

Ищет в диапазоне два одинаковых смежных элемента
(шаблон функции) [править]
создает копию некоторого диапазона элементов, который не содержит последовательных дубликатов
(шаблон функции) [править]