Ответ по умолчанию

Используйте std::vector. Это правильный контейнер для подавляющего большинства случаев. Выбирайте что-то другое только при наличии конкретной причины.

Это не отговорка — это следствие того, как работают кэши CPU. Вектор хранит элементы последовательно в памяти. Итерация по вектору из N элементов касается N кэш-линий по порядку. Все остальные стандартные контейнеры разбрасывают элементы по памяти, увеличивая количество промахов кэша.

1std::vector<float> vec(1000);     // 1000 float, одно выделение, последовательный доступ
2std::list<float>   lst(1000);     // 1000 узлов, 1000 выделений, случайный паттерн доступа

На современном CPU итерация по lst может быть в 10–50 раз медленнее, чем по vec при том же количестве элементов — исключительно из-за эффектов кэша.

std::array — фиксированный размер, на стеке

std::array<T, N> — обёртка с нулевыми накладными расходами над массивом C. Размер фиксирован на этапе компиляции; нет выделения на куче.

1#include <array>
2
3std::array<uint8_t, 64> buf{};   // 64 байта на стеке
4buf[0] = 0xAA;
5buf.fill(0);
6
7// range-for, итераторы, size() — всё работает как в vector
8for (auto b : buf) process(b);

Используйте когда:

  • Размер известен на этапе компиляции и не будет меняться
  • Нужно избежать выделения на куче (встраиваемые, ISR-контексты)
  • Нужен API std::vector без накладных расходов

Не используйте когда:

  • Размер меняется во время выполнения

std::array — встраиваемый стандарт для буферов. Предпочитайте его сырому T arr[N], так как он несёт информацию о размере, поддерживает копирование/перемещение/сравнение и работает со span’ами.

1void process(std::span<const uint8_t> data);
2
3std::array<uint8_t, 8> frame = {0x01, 0x02, 0x03};
4process(frame);  // неявное преобразование в span — без копирования

std::vector — динамический, непрерывный

std::vector<T> — рабочая лошадка. Непрерывная память, амортизированный O(1) push_back, O(1) случайный доступ.

1std::vector<SensorSample> samples;
2samples.reserve(1000);              // предварительное выделение — избегает перераспределений
3
4samples.push_back({tick, voltage});
5samples.emplace_back(tick, voltage);  // конструирование на месте — без лишней копии
6
7float third = samples[2].voltage;   // O(1)

Ключевые операции и стоимость:

Операция Стоимость
operator[], at() O(1)
push_back / emplace_back O(1) амортизированный
Вставка в середину O(n) — сдвигает элементы
Удаление из середины O(n) — сдвигает элементы
Поиск (не отсортирован) O(n)
Поиск (отсортирован + lower_bound) O(log n)

reserve обязателен для кода, чувствительного к производительности. Без него вектор удваивает ёмкость при каждом переполнении — корректно, но вызывает повторные выделения на куче и копирования.

1// Построить вектор из данных известного размера — всегда reserve
2std::vector<Frame> frames;
3frames.reserve(messageCount);
4for (auto& msg : messages)
5    frames.push_back(parseFrame(msg));

Идиома erase-remove — удаление элементов по значению без второго выделения:

1// Удалить все устаревшие сэмплы
2auto now = HAL_GetTick();
3auto it = std::remove_if(samples.begin(), samples.end(),
4    [now](const SensorSample& s) { return now - s.tick > 5000; });
5samples.erase(it, samples.end());

std::deque — двусторонняя очередь

std::deque<T> поддерживает O(1) push/pop с обоих концов и O(1) случайный доступ. Внутри это сегментированный массив — не полностью непрерывный, но более кэш-дружественный, чем список.

1std::deque<Command> queue;
2queue.push_back(cmd1);   // добавить в конец
3queue.push_front(cmd2);  // добавить в начало
4auto c = queue.front();
5queue.pop_front();        // O(1)

Используйте когда:

  • Нужен O(1) доступ с обоих концов
  • Нужен случайный доступ (в отличие от list)
  • Рабочий набор достаточно мал, чтобы промахи кэша от сегментации не имели значения

Не используйте когда:

  • Нужна непрерывная память (span, DMA, C API)
  • Интенсивная итерация — для последовательного доступа vector быстрее

На практике std::deque используется для очередей BFS, стеков отмены с доступом к началу и очередей задач с элементами с обоих концов. Для простого FIFO это чище, чем std::queue (который по умолчанию использует deque).

std::list — двусвязный список

std::list<T> — двусвязный список. Каждый элемент — отдельное выделение на куче. O(1) вставка/удаление в любом месте при наличии итератора на позицию.

 1std::list<Task> tasks;
 2tasks.push_back(t1);
 3tasks.push_front(t2);
 4
 5// Splice — O(1) перенос между списками без копирования
 6std::list<Task> pending;
 7auto it = tasks.begin();
 8pending.splice(pending.end(), tasks, it);  // перемещает *it в pending, O(1)
 9
10// Удаление по итератору — O(1)
11auto pos = std::find(tasks.begin(), tasks.end(), target);
12if (pos != tasks.end()) tasks.erase(pos);  // O(1) удаление, O(n) поиск

Используйте когда:

  • Требуется стабильность итераторов при вставке/удалении (итераторы на другие элементы остаются действительными)
  • Нужен O(1) splice (перемещение диапазонов между списками без копирования)
  • Реализуете структуру данных, которая изначально требует связанных узлов (например, колесо таймеров)

Не используйте для: чего угодно, где вы итерируете весь контейнер. Промах кэша на каждый элемент делает итерацию std::list значительно медленнее, чем std::vector.

Вектор с erase-remove почти всегда быстрее, чем список для типичных случаев, где вы думали, что нужен список.

std::set / std::map — отсортированное дерево

std::set<T> и std::map<K, V> — красно-чёрные деревья. O(log n) вставка, удаление, поиск. Отсортированный порядок. Каждый узел — выделение на куче, такой же штраф кэша, как у списка.

1std::map<std::string, Config> settings;
2settings["baud"] = Config{115200};
3auto it = settings.find("baud");  // O(log n)

Используйте когда:

  • Нужен отсортированный порядок и O(log n) операции
  • Нужна стабильность итераторов (итераторы переживают вставку/удаление других элементов)

Предпочитайте std::unordered_map, когда нужен только O(1) средний поиск и порядок не важен:

1std::unordered_map<std::string, Config> settings;
2settings["baud"] = Config{115200};
3auto it = settings.find("baud");  // O(1) в среднем

Для небольших хранилищ ключ-значение фиксированного размера (до ~20 записей) отсортированный vector пар с std::lower_bound часто быстрее обоих — нет накладных расходов на узлы кучи, кэш-дружественный, бинарный поиск за O(log n).

Руководство по выбору

Размер известен на этапе компиляции?
  Да → std::array<T, N>

Размер динамический?
  Нужен O(1) с обоих концов?
    Да → std::deque
    Нет → std::vector  ← по умолчанию

Нужен O(1) вставка/удаление в середине со стабильными итераторами?
  Да → std::list (и измерьте — редко оправдано)

Нужен поиск по отсортированному ключу?
  O(log n), упорядоченный, стабильный → std::map / std::set
  O(1) в среднем, неупорядоченный    → std::unordered_map / std::unordered_set

Встраиваемые контейнеры

На МК без кучи или с жёсткими ограничениями памяти стандартные контейнеры с выделением часто запрещены. Альтернативы:

Стандартный Встраиваемая альтернатива
std::vector std::array + ручной счётчик размера, или etl::vector
std::list Интрузивный связный список (узел встроен в объект)
std::map Отсортированный std::array + бинарный поиск
std::queue Кольцевой буфер (RingBuffer<T, N>)

Embedded Template Library (ETL) предоставляет версии большинства STL-контейнеров без кучи с фиксированной ёмкостью времени компиляции.

Итоги

  • std::array — размер на этапе компиляции, стек, нулевые накладные расходы — встраиваемый стандарт для фиксированных буферов
  • std::vector — динамический, непрерывный, кэш-дружественный — стандарт для всего остального
  • std::deque — O(1) с обоих концов, случайный доступ — очереди задач, BFS
  • std::list — O(1) вставка/удаление везде, стабильные итераторы, splice — редко оправдывает потери кэша
  • std::map/set — отсортированное дерево, O(log n) — когда важен порядок или стабильность итераторов
  • std::unordered_map — хэш-таблица, O(1) в среднем — когда важна скорость поиска, порядок нет

Что дальше