std::list и std::deque.
std::list:
- Двусвязный список.
- Добавление в начало (
push_front) и конец (push_back) за константное время O(1).
- Вставка и удаление элементов в любом месте также за константное время (при наличии итератора на нужный элемент).
- Не обеспечивает произвольный доступ по индексу O(1).
- Больше накладные расходы на хранение по сравнению с
std::vector.
std::deque:
- Двусторонняя очередь.
- Позволяет быстро (за константное время O(1)) добавлять и удалять элементы как в начале (
push_front, pop_front), так и в конце (push_back, pop_back).
- Обеспечивает произвольный доступ по индексу за константное время O(1).
- Внутренне реализован как набор блоков, что может привести к фрагментации памяти и медленному доступу по индексу по сравнению с
std::vector (хотя асимптотика такая же).
Пример использования push_front:
cpp