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

std::list and std::deque.

std::list:

• Doubly linked list.
• Adding at the beginning (push_front) and end (push_back) in constant time O(1).
• Inserting and deleting elements anywhere also in constant time (with an iterator to the element).
• Does not provide random access by index O(1).
• Has higher storage overhead compared to std::vector.

std::deque:

• Double-ended queue.
• Allows fast (constant time O(1)) addition and removal of elements at both the front (push_front, pop_front) and the back (push_back, pop_back).
• Provides random access by index in constant time O(1).
• Internally implemented as a set of blocks, which can lead to memory fragmentation and slower index access compared to std::vector (though asymptotically similar).

Example of using push_front:

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

int main() {
    // Using std::list
    std::list<int> my_list;
    my_list.push_front(20);
    my_list.push_front(10);
    // list: 10, 20

    // Using 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;
}