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

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

В стандартную библиотеку 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::array<T, N>3 это простейший контейнер. Его семантика ничем не отличается от обычного массива T[N]. Эти объекты лежат на стеке. Ни добавлять, ни удалять объекты нельзя, их ровно N.

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

std::array<T, 8>
std::array<T, 8>

Контейнеры разделяют две стадии "получить память для объекта" и "проинициализировать объект в этой памяти"; вторая стадия может произойти значительно позже первой. Но в std::array все N объектов инициализируются сразу.

По правилам C++ в массиве инициализация объектов происходит "слева направо", уничтожение "справа налево"4.

Небольшое отступление: может быть такое, что конструктор/деструктор объекта не делает совсем ничего (не меняет память, не вызывает другие делающие что-нибудь методы...). Такой конструктор/деструктор называют тривиальным. Если у T тривиальные конструктор и деструктор, то кроме выделения памяти для std::array<T, N> ничего не происходит5.

std::vector

std::vector<T>6 аллоцирует память для объектов в куче. На стеке лежат три указателя: на первый объект (begin), на следующий за последним объектом (end), и на следующий за последним доступным участком памяти (end_cap).

std::vector<T>, size = 5, capacity = 8
std::vector<T>, size = 5, capacity = 8

Объект в заранее аллоцированной памяти создается с помощью конструкции placement new7. А начиная с C++11 с вводом perfect forwarding8 новый объект для вектора можно создавать in-place (с помощью метода emplace/emplace_back9) без лишних вызовов copy/move-конструкторов.

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

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

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

При добавлении нового объекта, если он "не влезает", то сначала запрашивается память под max(1, 2 * capacity) объектов и старые объекты перемещаются в новую память. Размер вектора растет в последовательности 0, 1, 2, 4, 8, 16, \ldots, 2^N.

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

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

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

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

Основное отличие от std::vector - capacity увеличивается не в 2раза, а в 1.5 раза. В документации приводится подробное объяснение, почему это намного лучше - такой коэффициент более 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<Widget> : 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<Widget>& widgets) { // или folly::fbvector
    // выполняем некий код...
    Widget w;
    try {
        widgets.push_back(std::move(w));
    } catch (...) {
        // поймали исключение...
        // ожидаем, что `widgets` остался юзабельным
    }
}

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

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

Брошено исключение во время 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<Widget>::value == true15, и это поменять нельзя.

std::deque

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

std::deque<T>, на картинке start = 3, size = 15
std::deque<T>, на картинке start = 3, size = 15

Указатели на чанки "живут" в контейнере, похожем на вектор (с мелкими отличиями).

Получение ссылки на объект проводится через 2 разыменования (вместо 1 у std::vector).

Если нельзя добавить объект в начало/конец, то сначала аллоцируется новый чанк памяти. В худшем случае аллокаций будет два, потому что может понадобиться реаллокация контейнера указателей на чанки.

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

Минус контейнера в оверхеде по памяти, который более ощутим если объектов мало. std::deque<T> с одним объектом аллоцирует чанк немаленького размера (в реализации STL от Clang чанк занимает минимум 4096 байт).

Итераторы, указатели, и их инвалидация

До сего времени я не писал ничего подробного про итераторы и про их инвалидацию (как и про инвалидацию указателей).

Хотя эта тема знакома опытным C++-программистам, надо рассказать про них в контексте неклассических контейнеров.

Итератор у container<T> - это "легкий" объект, который должен быть похож на указатель T*. У каждого контейнера он свой. Задача итератора в основном в том, чтобы после вызова iter++ он начал как бы "указывать" на следующий объект контейнера, а вызов *iter вернул бы ссылку на как бы "указываемый" объект. Итераторы нужны много где, например для range-for17.

Самый простой итератор у std::array<T>, это и есть сам указатель T*.

Более сложный итератор у std::deque<T>, это объект из двух указателей: указатель на текущий чанк и указатель на текущий объект чанка. По iter++ эти указатели аккуратно обновляются и по *iter возвращается текущий объект чанка. Таким образом итератор обеспечивает "бесшовный" проход по всем объектам контейнера.

Итераторы/указатели могут инвалидироваться, то есть перестать указывать на объект. Обычно для описания условий, когда это происходит, создают всякие большие таблицы, где разбирают corner case-ы и т.д.

Лучше, конечно, не зубрить таблицы, а прочитать исходник класса итератора и класса контейнера. Тогда понимание этого вопроса придет само. Например, если не знать внутреннее устройство std::vector и std::deque, то сложно понимать, почему после вызова push_back ссылка на объект в первом контейнере может "протухнуть", а во втором - нет.

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

std::forward_list

std::forward_list18 это однонаправленный список - самая простая реализация списка. Список состоит из вершин. Вершина списка это сам объект и указатель на следующую вершину (указатель принимает значение nullptr, если объект последний в списке). Для каждой вершины память аллоцируется отдельно, размером sizeof(T) + sizeof(void*) байт.

std::forward_list<T> из трех объектов, корневая вершина на стеке
std::forward_list<T> из трех объектов, корневая вершина на стеке

Контейнер поддерживает быструю вставку и удаление объектов в любом месте, потому что для этого понадобится только правка next_ptr у вершины слева. Впрочем, "быстрая вставка" относится исключительно к "алгоритмической сложности". Аллокация памяти для новой вершины может быть небыстрой.

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

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

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

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

std::list

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

std::list<T>, size = 3
std::list<T>, size = 3

Интересный факт: начиная с C++11, вызов .size() должен работать за константное время20. Для этого поддерживается переменная, куда записывается размер списка. До C++11 реализации STL могли выполнять .size() за линейное время, проходя по всем вершинам.

Контейнеры-адаптеры

Некоторые контейнеры не имеют хитрого внутреннего устройства, и их функционал базируется на функционале какого-нибудь другого контейнера. В STL таких контейнеров три: std::stack, std::queue, std::priority_queue, в каждом можно выбрать "реальный" контейнер.

template<
    class T,
    class Container = std::deque<T>
> class stack;

template<
    class T,
    class Container = std::deque<T>
> class queue;

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> 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<bool>, boost::dynamic_bitset

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

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

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

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

std::bitset<512> на 64-битной машине (хватает 8 чисел size_t)
std::bitset<512> на 64-битной машине (хватает 8 чисел size_t)

В std::bitset<N>22, который лежит на стеке, количество битов нужно знать "заранее". Изначально все биты заполняются нулями. В контейнере есть несколько разнообразных методов для управления битами (всеми битами или конкретным битом).

Групповые операции, например .count()23 работают намного быстрее, чем если бы они совершались в обычном цикле for. Процессоры умеют производить все битовые операции над числом в одну инструкцию, что как минимум в 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<bool>. Этот класс многим программистам не нравится и есть мнение, что это неудачное решение в C++24. Люди, которые пытаются использовать его как полноценный контейнер, а не как "std::bitset на куче", натыкаются, например, на невозможность использовать нормальные указатели на объект (нельзя указывать на отдельный бит). Если есть такие проблемы, можно использовать std::vector<char>, std::vector<int>, std::deque<bool>.

std::vector<bool> или std::dynamic_bitset
std::vector<bool> или std::dynamic_bitset

std::vector<bool> отличается крайней бедностью доступных операций над битами. В нем отсутствуют элементарные групповые операции над битами, которые, как уже ранее писал, процессор умеет выполнять на порядки более эффективно, чем через for-цикл.

Есть его более продвинутый аналог в Boost - boost::dynamic_bitset25. В нем есть быстрая реализация всех операций над битсетом, которые только можно представить. Этот контейнер используется во многих проектах, у него широкий спектр применения.

"Неклассические" контейнеры хороши тем, что их можно достаточно быстро улучшать, отправляя туда патчи. Несколько лет назад я отправил в boost::dynamic_bitset пару патчей, которые ускоряли подсчет битов и добавляли новые методы для управления последовательностью битов26.

Static vector

Рассматриваемый ранее std::array<T, N> имеет свойство, что все N объектов инициализируются сразу. Если такое свойство не нравится, и хочется управлять памятью под N объектов, то можно использовать boost::static_vector27.

boost::static_vector<T, 8>
boost::static_vector<T, 8>

Этот контейнер ведет себя как обычный std::vector, но память у него аллоцирована на стеке под N объектов.

Каким образом можно получить сырую память на стеке, не имея создаваемого объекта? До C++23 это делается через std::aligned_storage28, с высоким риском для программиста сделать что-то не так и отстрелить себе ногу. Начиная с С++23 можно будет делать попроще:

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 объектов, но при переполнении аллоцируется память в куче.

boost::small_vec<T, 8> с 13 объектами
boost::small_vec<T, 8> с 13 объектами

На изображении показано, что N объектов лежит на стеке и size - N объектов в куче. Но есть реализации, где все size объектов выкидываются в кучу, чтобы обеспечить нахождение объектов в непрерывном участке памяти (при size > N).

Этот контейнер хорош, если количество объектов с большой вероятностью не превосходит заранее известное число.

Авторы этого контейнера пишут, что вдохновлялись SmallVector'ом из LLVM32. Это неудивительно - описываемые в статье контейнеры много где переизобретались заново.

В boost есть свой велосипед реализация собственно STL-овых контейнеров с разными фичами, например можно задавать growth factor у vector33 или размер блока у deque.

Devector

boost::devector это гибрид std::vector и std::deque. В этом контейнере есть быстрая вставка в начало и в конец, как в deque, но при этом сохраняются свойства vector, в частности непрерывный участок памяти и условия инвалидации указателей/итераторов.

boost::devector<T>, size = 5, front_capacity = 1, back_capacity = 2
boost::devector<T>, size = 5, front_capacity = 1, back_capacity = 2

При переаллокации вектора выбирается, в какую сторону девектор нужно расширять - слева или справо, в зависимости от того, какая граница была "пробита".

Если sizeof(std::vector) == 3 * sizeof(T*), то devector требуется дополнительный указатель, то есть sizeof(boost::devector) == 4 * sizeof(T*).

Stable vector

boost::stable_vector34 это гибрид std::vector и std::list.

В std::vector есть минус - легко инвалидирующиеся ссылки и итераторы. Они инвалидируются, когда вектор реаллоцируется, или когда удаляется/вставляется объект ближе к началу.

Можно поделить контейнеры на "стабильные" и "нестабильные". В "стабильных" контейнерах ссылки и итераторы на объект остаются валидными до тех пор, пока объект не удален из контейнера. Пример "стабильного" контейнера - std::list. Понятно, что std::vector - "нестабильный" контейнер.

Если у std::vector убрать требование на последовательное расположение объектов в памяти, то можно реализовать "стабильный" аналог вектора:

boost::stable_vector<T>, содержит 5 объектов
boost::stable_vector<T>, содержит 5 объектов

Там, где у std::vector лежат объекты, у boost::stable_vector вместо них лежит массив со ссылками на node.

node содержит в себе value - сам объект, и up - обратную ссылку на место в массиве, чье значение указывает на node.

Так же, как в std::list, node для каждого объекта аллоцируется отдельно.

Итератором на объект является ссылка на node.

Ссылки и итераторы на объект валидны до тех пор, пока объект не удалят из контейнера. Вставка/удаление объекта, который "ближе" к началу вектора, перепишет указатель up, но ни ссылка (на value), ни итератор (node*) не изменятся. Реаллокация массива ссылок на ноды также не инвалидирует ссылки/итераторы на объект (контейнер пофиксит значения up во время реаллокации).

Покажем на oversimplified псевдокоде, как работает итератор. Пусть есть вектор с указателями на ноды (как на картинке):

template<typename T>
struct node;

template<typename T>
std::vector<node<T>*> node_ptrs;

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

template<typename T>
struct node {
    node<T>** up;
    T value;
};

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

template<typename T>
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<T>* p;
};

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

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

Circular buffer

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

Кольцевой буфер с памятью на стеке на 8 объектов; start = 5, size = 5
Кольцевой буфер с памятью на стеке на 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 объекты лежат "плотно", то в колонии в чанках могут быть "прорехи". Общий вид колонии за годы несколько раз менялся, но абстракто он выглядит так:

colony<T>
colony<T>

Когда из колонии удаляют объект, то объекты "справа" от него не будут сдвигаться на освободившееся место. Таким образом указатели на объект не могут инвалидироваться.

Колония держит структуру skipfield, в которой кодирует информацию о "прорехах". "Прорехи" переиспользуются - при добавлении нового объекта он записывается в самую левую "прореху". Также skipfield используется для быстрого итерирования по "живым" объектам.

Кроме стабильности, контейнер имеет такие гарантии по базовым операциям:

  • вставка (одного объекта): O(1)

  • вставка (N объектов): O(N)

  • удаление (одного объекта): O(1)

  • удаление (N объектов): O(N) если тип не trivially destructible, O(logN)если trivially destructible

  • std::find: O(N); для поиска объекта нужно проитерироваться по всему контейнеру

  • Random access (оператор []): O(N); из-за "прорех" доступ к произвольному объекту за O(1)невозможен

Этот контейнер подходит, если нужна какая-то структура, куда можно быстро добавлять и удалять объекты, и чтобы ссылка на эти объекты не инвалидировалась, и чтобы это работало быстрее чем в std::list. Быстро получить объект по произвольному индексу нельзя, для этого контейнер не предназначен.

Реализацию контейнера можно посмотреть на github38.

Как выбрать подходящий контейнер?

Теперь, когда мы рассмотрели классические и неклассические контейнеры, можно представить себе практический кейс.

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

Запросы приходят в API вашего сервиса. Пусть все данные для оценки представлены классами/структурами на C++.

Представим себе API-класс, который описывает одну из ближайших к юзеру точек питания. У него есть расстояние до юзера (чем дольше, тем меньше "вес" в оценке), загруженность, наличие разных блюд, акции, а также история посещений юзером.

struct Restaurant {
    double Distance; // расстояние
    double Occupancy; // загруженность
    std::vector<Meal*> Meals; // доступные блюда
    std::vector<Promo*> Promos; // акции
    std::vector<Visit> VisitHistory; // история посещений
};

Некоторыми данными объект "владеет" (как историей посещения), а на некоторые просто ссылается, потому что они общие для всех.

Здесь получаем проблему - пусть у нас где-то в программе лежат объекты блюд std::vector<Meal> Meals. Если мы создадим Restaurant-ы, а потом добавим какое-то новое блюдо, то можно попасть на переаллокацию вектора, и в таком случае все ссылки Meal* станут висячими.

Можно обернуть объекты в умный указатель std::vector<std::shared_ptr<Meal>> Meals, но это не бесплатно и некрасиво.

Есть способ, который решает несколько проблем - все API-классы нужно объявить non-copyable39 И non-movable. Какие будут плюсы:

  1. Объекты невозможно случайно передать по значению/скопировать/переместить.

  2. Указатели на объекты живут столько же, сколько контейнер, где содержится объект.

Компилятор C++ не даст заиспользовать контейнер как std::vector, который потенциально сможет инвалидировать ссылки. Скомпилируется использование безопасного контейнера, например std::list. Из неклассических контейнеров скомпилируется использование, например, stable_vector или colony.

Ссылки

  1. Containers library - cppreference.com

  2. Аллокаторы памяти - habr.com

  3. std::array - cppreference.com

  4. godbolt.org - демонстрация автоматического создания и уничтожения объектов в std::array

  5. godbolt.org - создание std::array для элементарного T.

  6. std::vector - cppreference.com

  7. Placement new operator in C++ - GeeksforGeek

  8. Идеальная передача и универсальные ссылки в C++ - habr.com

  9. std::vector<T,Allocator>::emplace_back - cppreference.com

  10. folly/FBVector.md - документация к folly::fbvector

  11. Default constructors - cppreference.com

  12. Google C++ Style Guide

  13. std::unique_ptr - cppreference.com

  14. std::move_if_noexcept - cppreference.com

  15. std::is_trivially_move_constructible - cppreference.com

  16. std::deque - cppreference.com

  17. Range-based for loop - cppreference.com

  18. std::forward_list - cppreference.com

  19. std::list - cppreference.com

  20. std::list::size - cppreference.com

  21. C numeric limits interface - cppreference.com

  22. std::bitset<N> - cppreference.com

  23. std::bitset<N>::count - cppreference.com

  24. Алёна C++: Чем плох vector<bool>

  25. boost::dynamic_bitset

  26. Мои коммиты в boost::dynamic_bitset

  27. boost::static_vector

  28. std::aligned_storage - cppreference.com

  29. godbolt.org - переполнение boost::static_vector, исключение

  30. godbolt.org - переполнение boost::static_vector, assert

  31. boost::small_vector

  32. llvm/ADT/SmallVector.h - LLVM Programmer's Manual

  33. boost::container::growth_factor

  34. boost::stable_vector

  35. Circular buffer - Wikipedia

  36. boost::circular_buffer

  37. Introduction of std::colony to the standard library

  38. mattreecebentley/plf_colony - github.com

  39. boost::noncopyable

Комментарии (23)


  1. demp
    08.05.2022 16:27
    +7

    В описании std::vector небольшая неточность - стратегия роста емкости никак не указана в стандарте, так что это деталь реализации. В stdlibc++ и libc++ это удвоение размера, но вроде бы в Visual C++ используется множитель 1.5

    Еще у Matthew Bentley, автора Colony, есть интересный документ про рост емкости для deque-like контейнера: https://plflib.org/matt_bentley_-_pot_blocks_bit_tricks.pdf


    1. Izaron Автор
      08.05.2022 16:35

      Спасибо! Да, проверил что для Visual C++ в 1.5 раза увеличивается

      https://godbolt.org/z/WYs9f7Kn5


    1. sergegers
      09.05.2022 18:13
      +2

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


  1. ap1973
    08.05.2022 17:10

    Я конечно не специалист по C, и возможно что-то не так понял, но... Если ваш контейнер содержит не ссылку на объект, а сам объект, то использовать ссылку на него, во вне работы с контейнером - ну... будет беда. Либо copy on write (value type), без ссылок, либо ссылки в контейнере.


    1. Shreedeer
      08.05.2022 18:02
      +2

      Ну это зависит от контейнера, например в ассоциативных (мапы, сеты) или array ссылки не инвалидируются, а в векторе или деке (при вставке в середину) да.


      1. ap1973
        08.05.2022 19:24
        +3

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


        1. mentin
          08.05.2022 22:41
          +4

          Иногда без этого никак. Например, вам нужен быстрый поиск и одновременно определенный порядок: придется завести map и скажем list, и иметь перекрестные ссылки между контейнерами. Хорошая практика конечно абстрагировать это как новый тип контейнера, но внутри будут ссылки между используемыми контейнерами.


  1. middle
    08.05.2022 19:55

    fbvector не cache-friendly, а снижает фрагментацию памяти (или, лучше сказать, в случае удвоения фрагментация практически гарантирована).


    1. mentin
      08.05.2022 23:19
      +1

      Это одно и то же в данном контексте: рост с фактором меньше 2х позволяет вектору при росте использовать свои предыдущие куски памяти. Это и снижает фрагментацию и делает это cache-friendly поскольку предыдущие куски вероятно в кеше.


      1. middle
        09.05.2022 06:25

        Так ли важно, находится ли в кэше память, которую вы перезаписываете?


        1. mentin
          09.05.2022 07:46
          +2

          Да, хотя не так сильно как на чтение конечно, и от конкретной системы зависит.

          Всё что вы перезапишите должно быть рано или поздно скинуто в основную память. Если новый вектор расположен поверх старых, а старые версии еще не попали в основную память - то сброс этих старых версий в основную память вы сэкономили. В результате вам надо меньше пропускной способности шины.

          Плюс в многопроцессорных системах экономия на координации в каком кеше какая память лежит.


  1. eee
    08.05.2022 20:12
    +4

    Потрясающая статья, спасибо за труды!


  1. dbezheckov
    08.05.2022 20:25
    +2

    более оптимально аллоцировать

    классическая ошибка, не бывает более или менее оптимально, бывает либо оптимально, либо нет, это же определение оптимальности :)


  1. mrbald
    08.05.2022 20:36
    +3

    Спасибо, хорошая подборка. Вы не упомянули boost::intrusive (как концепцию и как набор конкретных контейнеров). Она хорошего качества (я использую в проде много лет) и позволяет клепать вещи типа multi-index или queue-map правильно и быстро.


  1. PyerK
    09.05.2022 11:40
    +1

    Искренне интеретсуюсь, почему std::valarray пропущен в статье ?
    Часто провожу собеседования, статистически о std::valarray, кандидаты знают +- как и о std::deque = ничего.


    1. Izaron Автор
      09.05.2022 12:25

      В статье рассматривается скорее внутреннее устройство контейнеров и управление памятью.

      std::valarray по своему внутреннему устройству имеет незначительное отличие от std::vector (а именно 2 указателя вместо 3, так как там size = capacity).

      "Синтаксический сахар" (методы min, sqrt, и тд) для std::valarray отличается от такового у std::vector, но это не так важно. В мире C++ есть много vector-like объектов, но они не принесли бы принципиально новой информации в статью.


      1. PyerK
        09.05.2022 13:12
        +1

        std::valarray имеет довольно таки интересный "сахар", как например, запись для обнуления элементов меньших нуля:


        data[ data < 0 ] = 0;


        Само по себе, существование такого сахара вызывает как минимум - любопытство. (Кто сможет реализовать такое API в векторе, не зная изначально и не подглядывая как это сделано в valarray ?).


        Ну и в отличии от vector`а стандрат разрешает распарралеливать "сахар" (интересно реализовано ли это в современных компиляторах ?), и имеет дополнительные правила для aliasинга элементов что ещё больше делает его особенным.


  1. shovdmi
    09.05.2022 19:17

    Спасибо за отличный обзор!

    Можете что-нибудь сказать о библиотеке Bitmagic, как альтернативе bitset или vector<bool>?


    1. Izaron Автор
      10.05.2022 17:32

      К сожалению, не пользовался библиотекой Bitmagic. Прочитав про нее, увидел что это очень мощная библиотека. Про устройство - последовательность битов там может иметь очень разные представления. Все зависит от сценариев использования, мне хватало функционала bitset и dynamic_bitset.

      Единственно (на мой взгляд) минус в том, что библиотека Bitmagic является header-only, это негативно влияет на время компиляции.


  1. sena
    09.05.2022 19:20

    таких классов довольно мало и это событие маловероятно

    что-то мне такой подход не очень


    1. Izaron Автор
      09.05.2022 22:05

      Я на всякий случай проверил работу алгоритма перемещения.

      Изначально есть capacity для 10 объектов, при превышении делается реаллокация. Move-конструктор (не-noexcept) на 5-м объекте бросает исключение.

      Если есть конструктор копирования, то вызывается именно он - https://godbolt.org/z/8qnEavP1f и strong exception guarantee выполнится

      Widget(const Widget&) = default;

      Если его нет, то вызывается move-конструктор за неимением другого варианта и после ловли исключения часть объектов "побита" - https://godbolt.org/z/x5hjcGTqE

      Widget(const Widget&) = delete;

      Поэтому лучше стараться делать move-конструктор noexcept, а то много проблем может быть


  1. DmitryKoterov
    11.05.2022 11:28

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


    1. Izaron Автор
      11.05.2022 13:37

      Думаю что это сделано из соображений перфоманса.

      С вашим дизайном было бы так: разыменовать (1) ссылку на вектор, посмотреть на .data(), разыменовать (2) сам объект в нужном адресе.

      С текущим дизайном разыменование одно, так как сразу знаем нужный адрес.

      Можно считать что итератор станет работать в 2 раза медленнее.