Как работает 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;
}

Линковка в C++: проблемы множественного определения (multiple definition)

Регулярно пишу на C++ - хочется порой писать и о C++. 
Давно я вообще ничего сюда не писал - самое время совместить приятное с полезным. И с C++:)

Среди всех проблем, которые могут возникнуть на пути запуска C++-программы, есть такие, которые понять сложнее всего, - ошибки линковки. Одну из таких я попытаюсь сейчас описать: это ошибка множественного определения символов (multiple definition).

Вот, скажем, есть такой (искусственнейший) пример:

// main.cpp

#include "ComplicatedHello.h"

int main()
{
    ComplicatedHello obj;
    obj.SayHello();
    obj.MakeHoldeeSay();
}

Есть объект, который может сказать Hello сам, а может попросить это сделать другой объект, который содержит в себе.

// ComplicatedHello.h

#pragma once

#include "SimpleHello.h"

class ComplicatedHello
{
public:
    void SayHello()
    {
        Hello();
    }

    void MakeHoldeeSay()
    {
        m_Holdee.SayHello();
    }
private:
    SimpleHello m_Holdee;
};

// SimpleHello.h

#pragma once

#include "Hello.h"

class SimpleHello
{
public:
    void SayHello()
    {
        Hello();
    }
};

И простой объект, и сложный используют для общения одну единственную функцию Hello() - в ней-то и будет вся соль.

// Hello.h

#pragma once

#include

void Hello()
{
    std::cout << "Hello\n";
}

И всё прекрасно. Прелесть этой версии в том, что тут только один .cpp файл - одна единица компиляции, с которой все остальные файлы связаны цепочкой включений. Включение (#include) являет собой простое копирование всего кода подключаемого заголовочного файла, и поэтому в конце получается этакий разросшийся main.cpp. Следовательно, при компиляции его (заголовки не компилируются в объектники - только разве что прекомпилируются, если сильно надо) создаётся только один объектный файл - main.o - какие уж тут проблемы линковки:)

А теперь сделаем код более бизнесовым - разделим ComplicatedHello как самый громоздкий файл в нашем проекте на интерфейс и реализацию. Получаем такое:

// ComplicatedHello.h

#pragma once

#include "SimpleHello.h"

class ComplicatedHello
{
public:
    void SayHello();
    void MakeHoldeeSay();

private:
    SimpleHello m_Holdee;
};

// ComplicatedHello.cpp

#include "ComplicatedHello.h"
#include "Hello.h"

void ComplicatedHello::SayHello()
{
    Hello();
}

void ComplicatedHello::MakeHoldeeSay()
{
    m_Holdee.SayHello();
} 

Только при сборке на этот раз появилась неприятность: линковщик выдал ошибку multiple definition of 'Hello()'. Он мог бы ещё добавить, что это нарушение одного из фундаментальных правил C++ - правила одного определения (http://en.wikipedia.org/wiki/One_Definition_Rule), но сдержался. Так ведь самое главное, что всё вроде как предусмотрено, чтобы это правило не нарушать: каждый заголовок защищён прагмой, никаких циклических зависимостей, даже code style выдержан - ну что тут может не нравиться...

Но если вернуться к единицам компиляции, то станет видно, что их теперь две: main и ComplicatedHello. Можно проследить, что окажется включено в каждую из них:

main <- ComplicatedHello.h <- SimpleHello.h <- Hello.h
ComplicatedHello <- SimpleHello.h <- Hello.h

Правило одного определения нарушается, потому что функция Hello() вместе со своим телом полностью лежит в заголовке и переходит в изначальном виде в оба объектника. По стандарту языка в каждой единице трансляции допускается (и, более того, необходимо) определение одной и той же функции, если она объявлена как inline (и ещё какое-то исключение для статических функций), а для обычных функций на всю программу должно быть только одно определение где-то в одном месте.
Действительно, если определить Hello() как inline, ошибка исчезает, но зачем менять сигнатуру из-за такой мелочи, когда можно всё сделать как следует? То есть сделать из Hello.h самостоятельную единицу компиляции (может, так, наоборот, и не следует в этом случае - просто так хочется):

// Hello.h (да, вот такой целый хэдер)

#pragma once

void Hello();

// Hello.cpp

#include "Hello.h"

#include

void Hello()
{
    std::cout << "Hello\n";
}

Тогда каждое включение заголовка приведёт к копированию прототипа функции Hello() (типа как написать extern void Hello() вместо каждого включения), что создаст ссылку на эту функцию в каждом объектнике, а уж линковщик самостоятельно найдёт для каждой ссылки тело функции в её собственном объектнике.

Кстати, заметили, что определение класса SimpleHello оказывается тоже в каждом объектнике по схеме выше? Можно не беспокоиться, для классов по стандарту это ок:)

Таким образом, хотел просто предупредить, что нельзя сильно увлекаться с наполнением заголовочных файлов: они должны содержать прототипы функций, ну или тела inline-функций - не более, потому что любое лишнее определение может повлечь за собой зловещие и очень малопонятные ошибки, какими изобилует линковщик.

Кстати, хорошая новость: я и сам почти поверил, что разобрался в этом всём. Успеееех=)