​​Гибридные вектора
#опытным

std::inplace_vector воплощает в себя преимущества динамического расширения размеров и отсутствия аллокаций. Полезная штука, но и она ограничена. Literally: вы не можете добавить в массив элементов больше, чем capacity.

И это нормальные ограничения. Нельзя иметь неограничено расширяемый массив на стеке.

Но что если я знаю, что в 99% случаев мой массив будет содержать не больше N элементов. Но все же иногда нужно будет хранить потенциально намного больше элементов. Что делать?

Ну для начала есть small object optimization для стандартного std::vector. Вместо того, чтобы хранить элементы в куче, небольшое число маленьких по размеру элементов можно хранить на стеке. И при добавлении элементов больше порога уже использовать динамические аллокации. Как SSO в std::string.

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

Но можно сделать и более управляемый вариант.

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

Такой комбинированный подход позволяет и рыбку съесть, и на правильный стул сесть. Аллокаций на минимуме, перф суперблейзинговый и привычный интерфейс.

Вот несколько представителей этого подхода:

- absl::InlinedVector.
- boost::container::small_vector.
- llvm::SmallVector.
- folly::small_vector.

Combine advantages. Stay cool.

#performance #memory #optimization