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

В C++ стандартная библиотека предоставляет несколько контейнеров, которые позволяют эффективно вставлять элементы в начало:

• std::deque (double-ended queue): Этот контейнер оптимизирован для вставки и удаления элементов как в начале, так и в конце. Вставка в начало имеет амортизированную постоянную сложность O(1).

• std::list (doubly linked list): Связный список. Вставка в начало осуществляется путем изменения указателей головы списка. Сложность вставки в начало постоянная - O(1).

• std::forward_list (singly linked list): Односвязный список. Вставка в начало (с помощью push_front или emplace_front) также имеет постоянную сложность O(1).

• std::vector: Хотя технически можно вставить элемент в начало std::vector с использованием insert(begin(), value), это не эффективно. Вставка в начало std::vector требует сдвига всех существующих элементов вправо, что приводит к линейной сложности O(n), где n — количество элементов в векторе.

Краткое сравнение эффективности вставки в начало:

Для частых операций вставки в начало предпочтительнее использовать std::deque, std::list или std::forward_list по сравнению с std::vector. Выбор между ними зависит от других необходимых операций (например, доступа по индексу или частых вставок/удалений в середине контейнера).