Неклассические контейнеры в C++08.05.2022 17:32

Устройство одного из контейнеров, описанного в статье

Контейнер — это объект, используемый для хранения других объектов. Контейнер берет на себя управление всей памятью, которые эти объекты занимают.

В стандартную библиотеку C++ входит несколько контейнеров. Кроме этого, в Open Source есть несколько контейнеров, которые покрывают больше юзкейсов. Я опишу устройство интересных контейнеров вне STL1 и их отличия от классических контейнеров.

Условно контейнеры можно разделить на две группы — последовательные (sequence) и ассоциативные (associative). Это деление я использую из-за того, что они слишком сильно отличаются между собой. В этой статье я рассматриваю только последовательные контейнеры. Но, возможно, когда-то в будущем напишу про ассоциативные контейнеры…

Управление памятью

Чтобы объект мог существовать, ему нужно выделить память, где будут находиться значения его полей. В стандартных приложениях память берется из стека (stack) или из кучи (heap). В общем, это совершенно прописные понятия, но их хорошо бы представлять себе для понимания этой публикации.

Выделение памяти на стеке (stack allocation) это увеличение указателя стека на захардкоженное значение. Выделение памяти на куче (heap allocation) это может быть системный вызов, могут использоваться кастомные аллокаторы со сложной логикой (как tcmalloc, jemalloc), memory pools — много чего происходит «под капотом».

Разница в скорости между двумя видами аллокации отличается на порядки, можно посмотреть на инфографике:

stack allocation займет единицы CPU-операций, heap allocation может занять тысячи, но это зависит от аллокатора — heap allocation можно сделать крайне быстрым. Про самодельные аллокаторы можно почитать на Хабре2.

Реализация STL и неклассических контейнеров

Стандарт C++ описывает только интерфейс контейнеров и требования на какие-то вещи (скорость операций, какие-нибудь гарантии и т.д.)

У STL есть несколько реализаций. Одни и те же контейнеры в разных реализациях обычно не очень сильно отличаются друг от друга. Сейчас есть три популярные реализации STL от команд Clang, GCC и Microsoft.

Читать реализации сложно, потому что один и тот же код должен уметь компилироваться под все стандарты, поэтому там есть мешанина из #ifdef-ов и жуткого кода

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 allocator() _NOEXCEPT = default;

Код для неклассических контейнеров обычно читается проще. Многие библиотеки компилируются под определенный стандарт и/или могут менять интерфейс (в STL это невозможно).

std: array

std::array3 это простейший контейнер. Его семантика ничем не отличается от обычного массива T[N]. Эти объекты лежат на стеке. Ни добавлять, ни удалять объекты нельзя, их ровно N.

Особенность std::array (а точнее, массива T[N]) в том, что все объекты, которые в нем находятся, инициализируются немедленно и сразу готовы к употреблению.

После добавления объекта; size = 6, capacity = 8; изменяется end

У вектора есть метод .size(), это количество реальных объектов; и .capacity(), это количество объектов, под которые зарезервирована память.

Пустой вектор ничего не аллоцирует (begin = end = end_cap = nullptr), то есть имеет size и capacity равные .

При добавлении нового объекта, если он «не влезает», то сначала запрашивается память под max(1, 2 * capacity) объектов и старые объекты перемещаются в новую память. Размер вектора растет в последовательности .

size = capacity = 8, перед добавлением объекта нужна реаллокацияcapacity растет с 8 до 16

Объекты из старой памяти нужно переместить в новую память, и потом освободить старую память. Перемещать объекты можно разными способами — чуть позже я опишу, каким образом можно выбрать наиболее оптимальный. Сейчас можно презентовать кастомную реализацию вектора.

folly: fbvector — улучшенный аналог std: vector

Folly это опенсорсная C++-библиотека всяких полезных штук. Там есть реализация своего вектора — folly::fbvector с документацией10.

Основное отличие от std::vector — capacity увеличивается не в раза, а в  раза. В документации приводится подробное объяснение, почему это намного лучше — такой коэффициент более cache-friendly.

Также контейнер умеет подстраиваться под аллокатор jemalloc (если он включен) и более оптимально аллоцировать память специально под него.

Еще одна оптимизация связана с перемещением объектов из старой памяти в новую память во время реаллокации вектора. Для CPU объект — это просто набор байтов. Если эти байты физически переместить в другое место, то в подавляющем большинстве случаев объект останется юзабельным. Такие объекты можно называть relocatable.

Вот пример не-relocatable объекта, потому что одно поле указывает на другое поле:

    class Ew {
      char buffer[1024];
      char * pointerInsideBuffer;
    public:
      Ew() : pointerInsideBuffer(buffer) {}
      ...
    }

По умолчанию Folly считает, что объекты пользовательских классов не-relocatable. Чтобы указать, что пользовательский класс Widget является relocatable, нужно написать это:

    // at global namespace level
    namespace folly {
      struct IsRelocatable : boost::true_type {};
    }

Раньше я обещал показать, как выбирается способ переноса объектов; вот так это выглядит для folly::fbvector:

1. Если тип IsRelocatable: делается memcpy памяти, занимаемой объектами.

2. Если у типа есть move-конструктор, являющийся noexcept: делается move каждого объекта.

3. Если у типа нет copy-конструктора: делается move каждого объекта.

4. По умолчанию: делается copy каждого объекта.

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

Про второй пункт: зачем нужно требование на noexcept у move-конструктора? Это нужно для того, чтобы выполнялись «strong exception guarantee». Посмотрим на такой код:

void TryAddWidget(std::vector& widgets) { // или folly::fbvector
    // выполняем некий код...
    Widget w;
    try {
        widgets.push_back(std::move(w));
    } catch (...) {
        // поймали исключение...
        // ожидаем, что `widgets` остался юзабельным
    }
}

«Strong exception guarantee» заключается в том, что если при попытке добавить объект в вектор произошло исключение, то сам вектор должен остаться в консистентном состоянии — то есть таким же, как был до попытки добавления объекта.

Если move-конструктор может бросить исключение, то мы можем безнадежно сломать исходный вектор. Пусть мы делаем переаллокацию и во время переноса произошло исключение:

Брошено исключение во время move пятого объекта

В общем случае объекты после move использовать нельзя. Так как часть объектов перемещена в новую память, то надо их переместить назад в старую память. Если во время этого «восстановления» выбросится новое исключение, то выполнение программы окончательно сломано.

А у noexcept move-конструкторов таких проблем нет. В C++ есть правила, по которым у классов могут создаваться неявные конструкторы11, и если это возможно, то на них навешивается noexcept.

Многие стайлгайды C++ запрещают использование исключений в принципе (например Google C++ Style Guide12), и такой класс проблем отсутствует.

Про третий пункт: если у класса нет copy-конструктора (таким классом является, например, std::unique_ptr13), то вызывается move-конструктор независимо от наличия noexcept-спецификатора. Это может сломать консистентность (гарантии нет), но таких классов довольно мало и это событие маловероятно.

Про четвертый пункт: если все прошлые пункты не выполняются, то используется обычное копирование объекта.

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

У классического std::vector такой же выбор логики для перемещения объектов как для folly::fbvector, за исключением первого пункта. Стандартная реализация считает, что объект класса Widget relocatable, если std::is_trivially_move_constructible::value == true15, и это поменять нельзя.

std: deque

std::deque16 (double-ended queue) это контейнер с быстрым добавлением объектов в начало и в конец. Если std::vector это сплошной кусок памяти, то в std::deque вся память разбивается на несколько кусков памяти (чанков) одинаковой величины.

Добавление нового объекта в середину списка

Быстро получить N-й объект нельзя, для этого нужно пройтись от корневой вершины по next_ptr N раз. Размер списка тоже можно узнать только пройдя по всем next_ptr, пока не увидим nullptr. У контейнера даже нет метода .size().

Вне STL есть реализации однонаправленного списка, где метод .size() реализован за , за оверхед в виде хранения переменной size на стеке.

Итераторы и указатели на объект в этом контейнере никогда не инвалидируются, пока не будет удален сам объект. Это максимально сильные гарантии среди всех контейнеров.

std: list

std::list19 это более сложная организация списка. Она имеет все те же свойства, как у std::forward_list, но вершины дополнительно могут ссылаться на предыдущие вершины, и есть быстрое добавление в конец списка.

template< class T, class Container = std::deque > class stack; template< class T, class Container = std::deque > class queue; template< class T, class Container = std::vector, class Compare = std::less > class priority_queue;

В большинстве случаев интерфейс контейнера-адаптера просто перенаправляет вызов методов, например у std::stack:

    bool empty()     const      {return c.empty();}
    size_type size() const      {return c.size();}
    reference top()             {return c.back();}
    void push(const value_type& __v) {c.push_back(__v);}
    void pop() {c.pop_back();}

Битовые контейнеры — std: bitset, std: vector, boost: dynamic_bitset

Битовые контейнеры нужны для управления последовательностью из N битов. То есть это контейнеры для всего лишь одного типа — битов.

Объект не может «весить» меньше чем 1 байт, но в один байт вмещается целых CHAR_BIT21 битов (обычно CHAR_BIT = 8). Поэтому специальный контейнер для битов в 8 раз эффективнее по памяти.

Физически такие контейнеры содержат несколько чисел, обычно типа size_t (их размер 64 бита на 64-битной машине).

Как и в «стандартных» контейнерах, данные могут лежать либо на стеке, либо в куче.

std::bitset<512> b; b[128] = 1; // или b[128] = true

operator[](size_t pos) переопределен так, чтобы на его вызов возвращался «легкий» объект std::bitset::reference, в котором находится указатель на число и «маска» бита. И в свою очередь у этого объекта переопределен operator=(bool x), который производит запись в нужный бит.

Как вы уже могли заметить, в C++ много где используются подобные фокусы с подставлением «легких» объектов (итераторы, bit reference), чтобы пользователям было удобно с ними работать.

Аналогичный класс с данными в куче (где количество битов можно задавать в run-time), сделан в виде std::vector. Этот класс многим программистам не нравится и есть мнение, что это неудачное решение в C++24. Люди, которые пытаются использовать его как полноценный контейнер, а не как »std::bitset на куче», натыкаются, например, на невозможность использовать нормальные указатели на объект (нельзя указывать на отдельный бит). Если есть такие проблемы, можно использовать std::vector, std::vector, std::deque.

alignas(T) std::byte buff[sizeof(T)];

и потом создавать объекты в buff через ставший привычный нам placement new.

По умолчанию, при попытке добавить N+1 объект в boost::static_vector выбросится исключение. Можно написать код и запустить через godbolt (он поддерживает Boost)29. Для максимального перформанса можно в шаблон передать настройку не выбрасывать исключение, тогда программа просто схлопнется30.

Small vector

boost::small_vector31 это гибрид boost::static_vector и std::vector. В нем статически отводится память под N объектов, но при переполнении аллоцируется память в куче.

template struct node; template std::vector*> node_ptrs;

В ноде два значения: ссылка на место в массиве ссылок на ноды; и сам объект

template
struct node {
    node** up;
    T value;
};

Итератор работает со ссылкой на ноду:

template
class stable_vector_iterator {
public:
    using self = stable_vector_iterator;

    self& operator++() {
        p = *(p->up + 1);
        return *this;
    }

    T& operator*() {
        return p->value;
    }

private:
    node* p;
};

Чтобы получить ссылку на «следующую» ноду, надо пройти по up в то место массива, где лежит текущая ссылка, сдвинуться на следующее место, и разыменовать получившееся значение.

Алгоритмическая сложность всех методов boost::stable_vector точно такая же, как у соответствующих методов std::vector. В частности, в отличие от std::list можно за  получить объект по произвольному индексу.

Circular buffer

Про кольцевой буфер есть статья на Wikipedia35. В C++ его можно реализовать в виде контейнера фиксированной длины N (на стеке или в куче), где при выходе за границу массива объект создается в начале массива.

Кольцевой буфер с памятью на стеке на 8 объектов; start = 5, size = 5

Кольцевой буфер может быть реализован как обычный vector. Плюс контейнера — быстрое удаление/вставка в начале. Минус контейнера — жесткое ограничение по памяти в N объектов. Больше этот контейнер ничем не интересен.

Реализация кольцевого буфера есть в boost: boost::circular_buffer36.

Colony

Контейнер colony (колония) это гибрид std::deque и std::list. Этот контейнер предлагали к внесению в стандарт С++, но пока не внесли. Есть документ с максимально подробным описанием контейнера37.

Во многих проектах объекты чаще не «владеют» другими объектами, а только ссылаются на них. Например, в видеоиграх объект сущности может ссылаться на общие ресурсы: объекты звуков, объекты спрайтов.

Эти общие ресурсы живут в контейнерах. Если ресурсы часто видоизменяются (выгружаются/загружаются), то контейнер должен быть «стабильным». К сожалению, std::vector не является «стабильным», а std::list не дружит с кэшем и тормозит, особенно при итерировании по нему.

Колония это достаточно быстрый «стабильный» контейнер. Объекты в нем лежат разделенные по чанкам, как в std::deque. Если в std::deque объекты лежат «плотно», то в колонии в чанках могут быть «прорехи». Общий вид колонии за годы несколько раз менялся, но абстракто он выглядит так:

© Habrahabr.ru