Какие контейнеры в 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).
• Внутренне реализован как набор блоков, что может привести к фрагментации памяти и медленному доступу по индексу по сравнению с std::vector (хотя асимптотика такая же).

Пример использования push_front:

#include <list>
#include <deque>
#include <iostream>

int main() {
    // Использование std::list
    std::list<int> my_list;
    my_list.push_front(20);
    my_list.push_front(10);
    // list: 10, 20

    // Использование std::deque
    std::deque<int> my_deque;
    my_deque.push_front(20);
    my_deque.push_front(10);
    // deque: 10, 20

    std::cout << "List elements: ";
    for (int val : my_list) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    std::cout << "Deque elements: ";
    for (int val : my_deque) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}