Контейнер - это объект, используемый для хранения других объектов. Контейнер берет на себя управление всей памятью, которые эти объекты занимают.
В стандартную библиотеку 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
все N
объектов инициализируются сразу.
По правилам C++ в массиве инициализация объектов происходит "слева направо", уничтожение "справа налево"4.
Небольшое отступление: может быть такое, что конструктор/деструктор объекта не делает совсем ничего (не меняет память, не вызывает другие делающие что-нибудь методы...). Такой конструктор/деструктор называют тривиальным. Если у T
тривиальные конструктор и деструктор, то кроме выделения памяти для std::array<T, N>
ничего не происходит5.
std::vector
std::vector<T>
6 аллоцирует память для объектов в куче. На стеке лежат три указателя: на первый объект (begin
), на следующий за последним объектом (end
), и на следующий за последним доступным участком памяти (end_cap
).
Объект в заранее аллоцированной памяти создается с помощью конструкции placement new7. А начиная с C++11 с вводом perfect forwarding8 новый объект для вектора можно создавать in-place (с помощью метода emplace
/emplace_back
9) без лишних вызовов copy/move-конструкторов.
У вектора есть метод .size()
, это количество реальных объектов; и .capacity()
, это количество объектов, под которые зарезервирована память.
Пустой вектор ничего не аллоцирует (begin = end = end_cap = nullptr
), то есть имеет size
и capacity
равные .
При добавлении нового объекта, если он "не влезает", то сначала запрашивается память под max(1, 2 * capacity)
объектов и старые объекты перемещаются в новую память. Размер вектора растет в последовательности .
Объекты из старой памяти нужно переместить в новую память, и потом освободить старую память. Перемещать объекты можно разными способами - чуть позже я опишу, каким образом можно выбрать наиболее оптимальный. Сейчас можно презентовать кастомную реализацию вектора.
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<Widget> : boost::true_type {};
}
Раньше я обещал показать, как выбирается способ переноса объектов; вот так это выглядит для folly::fbvector
:
Если тип
IsRelocatable
: делается memcpy памяти, занимаемой объектами.Если у типа есть move-конструктор, являющийся noexcept: делается move каждого объекта.
Если у типа нет copy-конструктора: делается move каждого объекта.
По умолчанию: делается 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 использовать нельзя. Так как часть объектов перемещена в новую память, то надо их переместить назад в старую память. Если во время этого "восстановления" выбросится новое исключение, то выполнение программы окончательно сломано.
А у noexcept move-конструкторов таких проблем нет. В C++ есть правила, по которым у классов могут создаваться неявные конструкторы11, и если это возможно, то на них навешивается noexcept.
Многие стайлгайды C++ запрещают использование исключений в принципе (например Google C++ Style Guide12), и такой класс проблем отсутствует.
Про третий пункт: если у класса нет copy-конструктора (таким классом является, например, std::unique_ptr
13), то вызывается move-конструктор независимо от наличия noexcept-спецификатора. Это может сломать консистентность (гарантии нет), но таких классов довольно мало и это событие маловероятно.
Про четвертый пункт: если все прошлые пункты не выполняются, то используется обычное копирование объекта.
Для реализации такой логики используются уникальные функции из стандарта, например std::move_if_noexcept
14.
У классического std::vector
такой же выбор логики для перемещения объектов как для folly::fbvector
, за исключением первого пункта. Стандартная реализация считает, что объект класса Widget
relocatable, если std::is_trivially_move_constructible<Widget>::value == true
15, и это поменять нельзя.
std::deque
std::deque
16 (double-ended queue) это контейнер с быстрым добавлением объектов в начало и в конец. Если std::vector
это сплошной кусок памяти, то в std::deque
вся память разбивается на несколько кусков памяти (чанков) одинаковой величины.
Указатели на чанки "живут" в контейнере, похожем на вектор (с мелкими отличиями).
Получение ссылки на объект проводится через 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_list
18 это однонаправленный список - самая простая реализация списка. Список состоит из вершин. Вершина списка это сам объект и указатель на следующую вершину (указатель принимает значение nullptr
, если объект последний в списке). Для каждой вершины память аллоцируется отдельно, размером sizeof(T) + sizeof(void*)
байт.
Контейнер поддерживает быструю вставку и удаление объектов в любом месте, потому что для этого понадобится только правка next_ptr
у вершины слева. Впрочем, "быстрая вставка" относится исключительно к "алгоритмической сложности". Аллокация памяти для новой вершины может быть небыстрой.
Быстро получить N-й объект нельзя, для этого нужно пройтись от корневой вершины по next_ptr
N раз. Размер списка тоже можно узнать только пройдя по всем next_ptr
, пока не увидим nullptr
. У контейнера даже нет метода .size()
.
Вне STL есть реализации однонаправленного списка, где метод .size()
реализован за , за оверхед в виде хранения переменной size
на стеке.
Итераторы и указатели на объект в этом контейнере никогда не инвалидируются, пока не будет удален сам объект. Это максимально сильные гарантии среди всех контейнеров.
std::list
std::list
19 это более сложная организация списка. Она имеет все те же свойства, как у std::forward_list
, но вершины дополнительно могут ссылаться на предыдущие вершины, и есть быстрое добавление в конец списка.
Интересный факт: начиная с 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_BIT
21 битов (обычно CHAR_BIT = 8
). Поэтому специальный контейнер для битов в 8 раз эффективнее по памяти.
Физически такие контейнеры содержат несколько чисел, обычно типа size_t
(их размер 64 бита на 64-битной машине).
Как и в "стандартных" контейнерах, данные могут лежать либо на стеке, либо в куче.
В 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>
отличается крайней бедностью доступных операций над битами. В нем отсутствуют элементарные групповые операции над битами, которые, как уже ранее писал, процессор умеет выполнять на порядки более эффективно, чем через for-цикл.
Есть его более продвинутый аналог в Boost - boost::dynamic_bitset
25. В нем есть быстрая реализация всех операций над битсетом, которые только можно представить. Этот контейнер используется во многих проектах, у него широкий спектр применения.
"Неклассические" контейнеры хороши тем, что их можно достаточно быстро улучшать, отправляя туда патчи. Несколько лет назад я отправил в boost::dynamic_bitset
пару патчей, которые ускоряли подсчет битов и добавляли новые методы для управления последовательностью битов26.
Static vector
Рассматриваемый ранее std::array<T, N>
имеет свойство, что все N
объектов инициализируются сразу. Если такое свойство не нравится, и хочется управлять памятью под N объектов, то можно использовать boost::static_vector
27.
Этот контейнер ведет себя как обычный std::vector
, но память у него аллоцирована на стеке под N
объектов.
Каким образом можно получить сырую память на стеке, не имея создаваемого объекта? До C++23 это делается через std::aligned_storage
28, с высоким риском для программиста сделать что-то не так и отстрелить себе ногу. Начиная с С++23 можно будет делать попроще:
alignas(T) std::byte buff[sizeof(T)];
и потом создавать объекты в buff
через ставший привычный нам placement new.
По умолчанию, при попытке добавить N+1
объект в boost::static_vector
выбросится исключение. Можно написать код и запустить через godbolt (он поддерживает Boost)29. Для максимального перформанса можно в шаблон передать настройку не выбрасывать исключение, тогда программа просто схлопнется30.
Small vector
boost::small_vector
31 это гибрид boost::static_vector
и std::vector
. В нем статически отводится память под N
объектов, но при переполнении аллоцируется память в куче.
На изображении показано, что N
объектов лежит на стеке и size - N
объектов в куче. Но есть реализации, где все size
объектов выкидываются в кучу, чтобы обеспечить нахождение объектов в непрерывном участке памяти (при size > N
).
Этот контейнер хорош, если количество объектов с большой вероятностью не превосходит заранее известное число.
Авторы этого контейнера пишут, что вдохновлялись SmallVector'ом из LLVM32. Это неудивительно - описываемые в статье контейнеры много где переизобретались заново.
В boost есть свой велосипед реализация собственно STL-овых контейнеров с разными фичами, например можно задавать growth factor у vector33 или размер блока у deque.
Devector
boost::devector
это гибрид std::vector
и std::deque
. В этом контейнере есть быстрая вставка в начало и в конец, как в deque, но при этом сохраняются свойства vector, в частности непрерывный участок памяти и условия инвалидации указателей/итераторов.
При переаллокации вектора выбирается, в какую сторону девектор нужно расширять - слева или справо, в зависимости от того, какая граница была "пробита".
Если sizeof(std::vector) == 3 * sizeof(T*)
, то devector требуется дополнительный указатель, то есть sizeof(boost::devector) == 4 * sizeof(T*)
.
Stable vector
boost::stable_vector
34 это гибрид std::vector
и std::list
.
В std::vector
есть минус - легко инвалидирующиеся ссылки и итераторы. Они инвалидируются, когда вектор реаллоцируется, или когда удаляется/вставляется объект ближе к началу.
Можно поделить контейнеры на "стабильные" и "нестабильные". В "стабильных" контейнерах ссылки и итераторы на объект остаются валидными до тех пор, пока объект не удален из контейнера. Пример "стабильного" контейнера - std::list
. Понятно, что std::vector
- "нестабильный" контейнер.
Если у std::vector
убрать требование на последовательное расположение объектов в памяти, то можно реализовать "стабильный" аналог вектора:
Там, где у 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
можно за получить объект по произвольному индексу.
Circular buffer
Про кольцевой буфер есть статья на Wikipedia35. В C++ его можно реализовать в виде контейнера фиксированной длины N
(на стеке или в куче), где при выходе за границу массива объект создается в начале массива.
Кольцевой буфер может быть реализован как обычный vector. Плюс контейнера - быстрое удаление/вставка в начале. Минус контейнера - жесткое ограничение по памяти в N
объектов. Больше этот контейнер ничем не интересен.
Реализация кольцевого буфера есть в boost: boost::circular_buffer
36.
Colony
Контейнер colony
(колония) это гибрид std::deque
и std::list
. Этот контейнер предлагали к внесению в стандарт С++, но пока не внесли. Есть документ с максимально подробным описанием контейнера37.
Во многих проектах объекты чаще не "владеют" другими объектами, а только ссылаются на них. Например, в видеоиграх объект сущности может ссылаться на общие ресурсы: объекты звуков, объекты спрайтов.
Эти общие ресурсы живут в контейнерах. Если ресурсы часто видоизменяются (выгружаются/загружаются), то контейнер должен быть "стабильным". К сожалению, std::vector
не является "стабильным", а std::list
не дружит с кэшем и тормозит, особенно при итерировании по нему.
Колония это достаточно быстрый "стабильный" контейнер. Объекты в нем лежат разделенные по чанкам, как в std::deque
. Если в std::deque
объекты лежат "плотно", то в колонии в чанках могут быть "прорехи". Общий вид колонии за годы несколько раз менялся, но абстракто он выглядит так:
Когда из колонии удаляют объект, то объекты "справа" от него не будут сдвигаться на освободившееся место. Таким образом указатели на объект не могут инвалидироваться.
Колония держит структуру skipfield, в которой кодирует информацию о "прорехах". "Прорехи" переиспользуются - при добавлении нового объекта он записывается в самую левую "прореху". Также skipfield используется для быстрого итерирования по "живым" объектам.
Кроме стабильности, контейнер имеет такие гарантии по базовым операциям:
вставка (одного объекта):
вставка (
N
объектов):удаление (одного объекта):
удаление (
N
объектов): если тип не trivially destructible, если trivially destructiblestd::find
: ; для поиска объекта нужно проитерироваться по всему контейнеруRandom access (оператор
[]
): ; из-за "прорех" доступ к произвольному объекту за невозможен
Этот контейнер подходит, если нужна какая-то структура, куда можно быстро добавлять и удалять объекты, и чтобы ссылка на эти объекты не инвалидировалась, и чтобы это работало быстрее чем в 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. Какие будут плюсы:
Объекты невозможно случайно передать по значению/скопировать/переместить.
Указатели на объекты живут столько же, сколько контейнер, где содержится объект.
Компилятор C++ не даст заиспользовать контейнер как std::vector
, который потенциально сможет инвалидировать ссылки. Скомпилируется использование безопасного контейнера, например std::list
. Из неклассических контейнеров скомпилируется использование, например, stable_vector
или colony
.
Ссылки
godbolt.org - демонстрация автоматического создания и уничтожения объектов в
std::array
godbolt.org - создание
std::array
для элементарногоT
.folly/FBVector.md - документация к folly::fbvector
godbolt.org - переполнение boost::static_vector, исключение
godbolt.org - переполнение boost::static_vector, assert
Комментарии (23)
ap1973
08.05.2022 17:10Я конечно не специалист по C, и возможно что-то не так понял, но... Если ваш контейнер содержит не ссылку на объект, а сам объект, то использовать ссылку на него, во вне работы с контейнером - ну... будет беда. Либо copy on write (value type), без ссылок, либо ссылки в контейнере.
Shreedeer
08.05.2022 18:02+2Ну это зависит от контейнера, например в ассоциативных (мапы, сеты) или array ссылки не инвалидируются, а в векторе или деке (при вставке в середину) да.
ap1973
08.05.2022 19:24+3Возможно я был не прав, но сама идея ссылки на элемент контейнера, инстинктивно вызывает у меня отторжение, и это мягко сказано. Тем более, тип контейнера имеет тенденцию меняться, а код который его использует, нет.
mentin
08.05.2022 22:41+4Иногда без этого никак. Например, вам нужен быстрый поиск и одновременно определенный порядок: придется завести map и скажем list, и иметь перекрестные ссылки между контейнерами. Хорошая практика конечно абстрагировать это как новый тип контейнера, но внутри будут ссылки между используемыми контейнерами.
middle
08.05.2022 19:55fbvector не cache-friendly, а снижает фрагментацию памяти (или, лучше сказать, в случае удвоения фрагментация практически гарантирована).
mentin
08.05.2022 23:19+1Это одно и то же в данном контексте: рост с фактором меньше 2х позволяет вектору при росте использовать свои предыдущие куски памяти. Это и снижает фрагментацию и делает это cache-friendly поскольку предыдущие куски вероятно в кеше.
middle
09.05.2022 06:25Так ли важно, находится ли в кэше память, которую вы перезаписываете?
mentin
09.05.2022 07:46+2Да, хотя не так сильно как на чтение конечно, и от конкретной системы зависит.
Всё что вы перезапишите должно быть рано или поздно скинуто в основную память. Если новый вектор расположен поверх старых, а старые версии еще не попали в основную память - то сброс этих старых версий в основную память вы сэкономили. В результате вам надо меньше пропускной способности шины.
Плюс в многопроцессорных системах экономия на координации в каком кеше какая память лежит.
dbezheckov
08.05.2022 20:25+2более оптимально аллоцировать
классическая ошибка, не бывает более или менее оптимально, бывает либо оптимально, либо нет, это же определение оптимальности :)
mrbald
08.05.2022 20:36+3Спасибо, хорошая подборка. Вы не упомянули boost::intrusive (как концепцию и как набор конкретных контейнеров). Она хорошего качества (я использую в проде много лет) и позволяет клепать вещи типа multi-index или queue-map правильно и быстро.
PyerK
09.05.2022 11:40+1Искренне интеретсуюсь, почему std::valarray пропущен в статье ?
Часто провожу собеседования, статистически о std::valarray, кандидаты знают +- как и о std::deque = ничего.Izaron Автор
09.05.2022 12:25В статье рассматривается скорее внутреннее устройство контейнеров и управление памятью.
std::valarray
по своему внутреннему устройству имеет незначительное отличие отstd::vector
(а именно 2 указателя вместо 3, так как там size = capacity)."Синтаксический сахар" (методы
min
,sqrt
, и тд) дляstd::valarray
отличается от такового уstd::vector
, но это не так важно. В мире C++ есть много vector-like объектов, но они не принесли бы принципиально новой информации в статью.PyerK
09.05.2022 13:12+1std::valarray имеет довольно таки интересный "сахар", как например, запись для обнуления элементов меньших нуля:
data[ data < 0 ] = 0;
Само по себе, существование такого сахара вызывает как минимум - любопытство. (Кто сможет реализовать такое API в векторе, не зная изначально и не подглядывая как это сделано в valarray ?).
Ну и в отличии от vector`а стандрат разрешает распарралеливать "сахар" (интересно реализовано ли это в современных компиляторах ?), и имеет дополнительные правила для aliasинга элементов что ещё больше делает его особенным.
shovdmi
09.05.2022 19:17Спасибо за отличный обзор!
Можете что-нибудь сказать о библиотеке Bitmagic, как альтернативе bitset или vector<bool>?
Izaron Автор
10.05.2022 17:32К сожалению, не пользовался библиотекой Bitmagic. Прочитав про нее, увидел что это очень мощная библиотека. Про устройство - последовательность битов там может иметь очень разные представления. Все зависит от сценариев использования, мне хватало функционала bitset и dynamic_bitset.
Единственно (на мой взгляд) минус в том, что библиотека Bitmagic является header-only, это негативно влияет на время компиляции.
sena
09.05.2022 19:20таких классов довольно мало и это событие маловероятно
что-то мне такой подход не очень
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, а то много проблем может быть
DmitryKoterov
11.05.2022 11:28Почему итератор у vector не сделан в виде 2 чисел - ссылка на сам вектор и номер позиции в векторе (начиная с 0)? Ведь в этом случае итератор бы не протухал, когда вектор ресайзится.
Izaron Автор
11.05.2022 13:37Думаю что это сделано из соображений перфоманса.
С вашим дизайном было бы так: разыменовать (1) ссылку на вектор, посмотреть на
.data()
, разыменовать (2) сам объект в нужном адресе.С текущим дизайном разыменование одно, так как сразу знаем нужный адрес.
Можно считать что итератор станет работать в 2 раза медленнее.
demp
В описании
std::vector
небольшая неточность - стратегия роста емкости никак не указана в стандарте, так что это деталь реализации. В stdlibc++ и libc++ это удвоение размера, но вроде бы в Visual C++ используется множитель 1.5Еще у Matthew Bentley, автора Colony, есть интересный документ про рост емкости для deque-like контейнера: https://plflib.org/matt_bentley_-_pot_blocks_bit_tricks.pdf
Izaron Автор
Спасибо! Да, проверил что для Visual C++ в 1.5 раза увеличивается
https://godbolt.org/z/WYs9f7Kn5
sergegers
Добавлю, что в теории оптимально использовать золотое сечение как коэффициент увеличения буфера. Но умножать на 1.61803398875 и потом округлять накладно да и не не имеет особого смысла практически. Поэтому используют сдвиг вправо или сдвиг влево и сложение с исходной величиной.