Which containers in C++ allow inserting elements at the beginning?

The C++ standard library provides several containers that allow efficient insertion of elements at the beginning:

• std::deque (double-ended queue): This container is optimized for inserting and deleting elements at both the beginning and the end. Insertion at the beginning has amortized constant complexity O(1).

• std::list (doubly linked list): A linked list. Insertion at the beginning is done by changing the head pointers. The complexity of insertion at the beginning is constant - O(1).

• std::forward_list (singly linked list): A singly linked list. Insertion at the beginning (using push_front or emplace_front) also has constant complexity O(1).

• std::vector: Although technically you can insert an element at the beginning of a std::vector using insert(begin(), value), this is not efficient. Inserting at the beginning of a std::vector requires shifting all existing elements to the right, which leads to linear complexity O(n), where n is the number of elements in the vector.

Brief comparison of insertion efficiency at the beginning:

Container	Insertion complexity at the beginning
std::deque	O(1) (amortized)
std::list	O(1)
std::forward_list	O(1)
std::vector	O(n)

For frequent insertion operations at the beginning, it is preferable to use std::deque, std::list, or std::forward_list compared to std::vector. The choice among them depends on other necessary operations (for example, index access or frequent insertions/deletions in the middle of the container).