YouTip

## C++ `std::list::push_front` Member Function The `push_front` function is a member of the C++ Standard Template Library (STL) `std::list` container. It is used to **insert a new element at the very beginning (head) of the list**. Unlike `std::vector`, which requires shifting all subsequent elements when inserting at the front, `std::list` is implemented as a doubly-linked list. This allows `push_front` to perform insertions in **$O(1)$ constant time**, making it highly efficient. --- ## Syntax and Parameters ### Function Prototype ```cpp void push_front(const T& value); void push_front(T&& value); // Since C++11 (Move semantics support) ``` ### Parameters * **`value`**: The value of the element to be prepended to the list. * **Type**: Must match the template type `T` specified when the `std::list` was declared. * **C++11 and later**: Supports both lvalue references (copying the value) and rvalue references (moving the value). ### Return Value * **`void`**: This function does not return any value. ### Complexity and Side Effects * **Time Complexity**: $O(1)$ (Constant time). * **Space Complexity**: $O(1)$ (Allocates memory for a single node). * **Size**: Increases the container's `size()` by 1. * **Iterator Validity**: Does not invalidate any existing iterators or references to elements in the list. --- ## Code Examples ### Example 1: Basic Usage - Prepending an Element This example demonstrates how to insert an element at the front of an existing list. ```cpp #include #include int main() { // Initialize a list with three elements std::list numbers = {20, 30, 40}; std::cout << "Original list: "; for (int n : numbers) { std::cout << n << " "; } std::cout << std::endl; // Insert 10 at the front of the list numbers.push_front(10); std::cout << "After push_front(10): "; for (int n : numbers) { std::cout << n << " "; } std::cout << std::endl; return 0; } ``` #### Expected Output ```text Original list: 20 30 40 After push_front(10): 10 20 30 40 ``` --- ### Example 2: Building a List in Reverse Order Because `push_front` always inserts elements at the head, adding elements sequentially using this method results in a list with a reversed order relative to the insertion sequence. ```cpp #include #include int main() { std::list data; // Sequentially push elements to the front data.push_front(5); data.push_front(4); data.push_front(3); data.push_front(2); data.push_front(1); std::cout << "Constructed list: "; for (int n : data) { std::cout << n << " "; } std::cout << std::endl; return 0; } ``` #### Expected Output ```text Constructed list: 1 2 3 4 5 ``` --- ## Key Considerations ### 1. `push_front` vs. `emplace_front` Since C++11, `std::list` also provides the `emplace_front` member function. * `push_front` takes an already constructed object (or constructs a temporary one) and copies or moves it into the list. * `emplace_front` forwards the arguments directly to the constructor of the element type, constructing the element in-place. This avoids unnecessary copy or move operations. ### 2. Container Compatibility * **`std::list` and `std::deque`** support `push_front` with $O(1)$ complexity. * **`std::vector`** does **not** support `push_front` because prepending elements to a vector requires shifting all existing elements in memory, which is an expensive $O(N)$ operation. If you need to frequently insert elements at the front, use `std::list` or `std::deque` instead of `std::vector`.