Какие контейнеры в C++ позволяют добавлять элементы в начало?

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).
• Внутренне реализован как набор блоков, что может привести к фрагментации памяти