В интернете много различных видео, в которых визуализируются алгоритмы. Как правило, такая визуализация делается под определенный алгоритм, и код отрисовки соединен с кодом самого алгоритма. Мне пришла идея отделить визуализацию алгоритма от его исполнения. Тогда можно будет визуализировать любой алгоритм. В том числе алгоритмы стандартной библиотеки С++. Я нашёл способ сделать это, и вот что у меня получилось.

Алгоритмы

std::accumulate и std::reduce

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

std::shuffle

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

std::merge

std::merge из двух отсортированных последовательностей формирует новую отстортированную последовательность. Данный алгоритм используется, например, в сортировке слиянием.

std::rotate

Работа алгоритма std::rotate выглядит довольно любопытно. std::rotate "вращает" элементы контейнера в левом направлении так, что заданный в качестве параметра элемент становится первым.

std::lower_bound и std::upper_bound

Алгоритмы std::lower_bound и std::upper_bound являются реализацией бинарного поиска. std::lower_bound возвращает итератор на первый элемент, равный искомому. Второй - на первый элемент, больший заданному. Оба итератора можно получить с помощью алгоритма std::equal_range.

std::remove

Видео выше демонстрирует работу std::remove. Удаляемому значению соответствует самая высокая линия. Алгоритм не удаляет элементы контейнера, поскольку имеет доступ только к итераторам. Элементы, которые должны остаться после удаления, перемещаются в начало. Само удаление может быть выполнено посредством метода erase контейнера (remove-erase idiom).

std::sort и std::sort_heap

Сравнение работы std::sort и std::sort_heap (предварительно строится пирамида с помощью алгоритма std::make_heap). В продемонстрированном примере std::sort работает заметно быстрее.

std::reverse_copy

std::reverse_copy копирует элементы контейнера в другой контейнер в обратном порядке.

std::next_permutation

Алгоритм std::next_permutation для генерации перестановок использует лексиграфичский порядок элементов. На приведенном видео продемонстрированы перестановки массива из 4-х элементов. Алгоритм применен std::next_permutation применен последовательно 23 раза.

Это все лишь несколько алгоритмов стандартной библиотеки C++. С полным списком можно ознакомиться по ссылке: https://en.cppreference.com/w/cpp/algorithm. Пишите в комментариях, визуализацию каких ещё алгоритмов вы бы хотели увидеть?

Как это работает

Ключевой идеей, позволяющей визуализировать произвольные алгортимы, является декорирование итератора. Полученный декоратор логирует доступ к контейнеру. Однако, мне не удалось найти способов отличить чтение от записи, используя информацию о вызове методов итератора.

// Отправляет информацию о вызываемых методах исходного итератора обработчику.
template <typename OriginalIterator>
class NotifyingIterator {
public:
    using iterator_category = typename OriginalIterator::iterator_category;
    using value_type = typename OriginalIterator::value_type;
    using difference_type = typename OriginalIterator::difference_type;
    using pointer = typename OriginalIterator::pointer;
    using reference = typename OriginalIterator::reference;

    /*
        ...
        здесь переопределeны методы исходного итератора
        ...
    */

    // Доступ к элементу контейнера будет трактован как чтение или запись
    reference operator * () {
        sendMessage("reference operator * ()");
        sendAccessEvent();
        return *current_;
    }
    
    void sendAccessEvent() const {
        difference_type pos = getOffset();
        assert(pos >= 0);
        Access event(pos);
        handler_.handle(event);
    }

private:    
    IEventHandler& handler_;
    OriginalIterator begin_;
    OriginalIterator current_;
};

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

template <typename Container>
class EventInterpreter: public IEventHandler {
public:
    /*
         ...
    */
    void handle(Event& event) override {
        if (event.getType() != Event::Access)
            return;
        if (recordingIsPaused_ )
            return;
        // Каждая запись и чтение имеет временную отметку. 
        // Приостанавливаем время, чтобы процесс обработки событий не влиял на тайминг.
        pause_guard pause(*stopwatch_);
        // Проверяем, изменился ли контейнер и интерпретируем изменения как операции записи.
        checkWriting();
	    // Сохраняем информацию о доступе к элементу контейнера
        addAccess(static_cast<Access&>(event));
    }
private:
    /*
         ...
    */
    Script script_;
    Container copy_;
    std::shared_ptr<Container> original_;
    std::shared_ptr<Stopwatch> stopwatch_;
};

Важной особенностью решения является отделение визуализации и логирования. Логирование алгоритма происходит до его визуализации. Результат сохраняется в файл. Далее этот файл загружается отдельной программой, отвечающей только за "проигрывание" полученного лог-файла. Пример такого файла:

std::sort_heap
24,24,22,20,20,21,21,4,8,12,10,9,20,18,18,2,1,5,4,4,4,3,8,2,3,1,8,4,18,14
932,access,29
1563,access,0
2074,write,29,24
3096,access,2
3587,access,1
4269,access,1
4920,access,0
5712,access,4
...

При наличии лог-файла визуализация не составляет труда. Во второй строке указаны исходные данные контейнера. Далее операции чтения или записи. В первом столбце указаны: временная отметка (наносекунды), тип операции, позиция и новое значение, если это запись.

С полным исходным кодом можно ознакомиться по ссылке