В 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 | O(1) (амортизированная) |
std::list | O(1) |
std::forward_list | O(1) |
std::vector | O(n) |
Для частых операций вставки в начало предпочтительнее использовать std::deque, std::list или std::forward_list по сравнению с std::vector. Выбор между ними зависит от других необходимых операций (например, доступа по индексу или частых вставок/удалений в середине контейнера).