Как работает std::unique

Среди простых и очень естественных алгоритмов есть такие, которые можно описать парой слов, однако прежде чем один такой действительно выйдет из-под рук, можно вспомнить все смертоносные заклинания, которым только учили в Хогвартсе. Двоичный поиск, быстрое возведение в степень, алгоритм Евклида - всем известные вещи о пяти строках кода, которые, тем не менее, не принято писать правильно с первого раза.

Вот, а я расскажу о совсем скучном алгоритме, который отбирает уникальные элементы в последовательности. Точнее, для каждого отрезка равных элементов этой последовательности он оставляет только первый:

[1 1 1 1 1 1 2 2 3 4 4 4 4 4 2 3 5 6 7 7 7 7 8 1] -> [1 2 3 4 2 3 5 6 7 8 1]

Самый главный плюс его в том, что на эту спорную деятельность он не отнимет много вашего времени - один проход по массиву, или O(n).

Казалось бы, проверить соседние элементы и, если они равны, удалить правый и пойти дальше, закончив работу ровно за один проход. Однако, хоть проход и действительно будет один, компьютер по завершении работы будет смотреть вам в глаза виновато: ему потребуется гораздо больше времени, чем O(n), потому что исходная последовательность может располагаться в непрерывной области памяти, из которой нельзя удалять, и единственный выход - сдвигать элементы... И вообще, хватит оправдываться - удалять нельзя! Вот такие новые условия задачи: элементы удалять нельзя, только менять их значения.

А как насчёт того, чтобы рассматривать отрезки с одинаковыми значениями один за другим? Вот так:

[1 1 1 1 1 1 | 2 2 | 3 | 4 4 4 4 4 | 2 | 3 | 5 | 6 | 7 7 7 7 | 8 | 1]

Тогда всё, о чём нам надо будет заботиться, - это 1) находить начало очередного отрезка, 2) находить его конец и начало следующего, 3) после шага 2 каждый раз копировать не более одного элемента.

Вот, скажем, определились границы первого отрезка 1 1 1 1 1 1 | 2. По условию задачи ото всех элементов начиная со второй единицы нужно избавиться, поэтому сразу же копируем двойку на место второй единицы: 1 2 1 1 1 1 | 2. Но что делать с оставшимися единицами, которые всё путают?

А сделаем вот так: 1 | 2 2 2 2 2 2 ... - теперь всё выглядит намного лучше: есть канонический (из одного элемента) отрезок с единицей, есть отрезок из двоек, конец которого ещё предстоит найти, и больше ничего лишнего. Только откуда все эти двойки? Там же вверху было чё-то про одно копирование максимум... А двоек и нет: мы их видим, потому что [нас только что отключили от Матрицы] мы так хотим: ведь правда, что происходит с теми оставшимися единицами, нам всё равно настолько, что мы спокойно можем назвать их двойками и с облегчением идти дальше. Неприятный осадок, который остаётся в таком случае, - это что такой подход работает, пока мы не настигнем конца последовательности: за последним исправленным отрезком будет твориться хаос из дублей и мешанины, которой от нашего алгоритма пользователь совсем не ожидал. Хорошая новость: unique возвращает позицию нового конца последовательности, начиная с которой дальше будет твориться хаос, и это нормально.

Итак, алгоритм ещё раз:

1. заводим два маркера: на начало отрезка равных элементов - equal_begin - и на позицию за концом - equal_end (изначально это первые два элемента последовательности), и отдельно переменную длины позиции - equal_distance;
2. пока не коснёмся equal_end конца последовательности, повторяем шаг 3

3. проверяем позицию за концом: если её элемент равен начальному, то это ещё не за концом - сдвигаем equal_end, инкрементируем equal_distance; если же не равен, смотрим, канонический ли это отрезок (равен ли equal_distance единице), и в зависимости от этого либо просто сдвигаем оба маркера, либо сдвигаем только equal_begin, копируем туда значение по equal_end и двигаем его. В обоих случаях длина текущего отрезка не меняется.
4. возвращаем позицию за equal_begin

Важное замечание: входная последовательность подаётся по правилам STL: {начальный элемент, элемент за концом}.

И код на C++ для лабораторок:

template<typename It>
It uniq(It begin, It end)
{
    It range_end(begin);
    ++range_end;
    size_t equal_distance(1);
    while (range_end != end)
    {
        // current segment still going
        if (*range_end == *begin)
        {
            ++range_end;
            ++equal_distance;
        }
        // the next segment begins
        else
        {
            if (equal_distance > 1)
            {
                *(++begin) = *(range_end++);              
            }
            else
            {
                ++begin;
                ++range_end;
            }
        }
    }
    return ++begin;
}