deque, list & array
Scenario
You need to frequently insert elements at the very front of your sequence. Knowing `std::vector::insert` at the front is O(N), you switch to `std::list` for O(1) front insertions. Your benchmark shows the code is actually running 5x slower than the vector.
If linked list insertions are theoretically O(1) and vector insertions are O(N), why did the vector win?
Mental model
`std::array` is a fixed, immovable box (C-array with a seatbelt). `std::list` is a scavenger hunt across the heap (linked list). `std::deque` is a collection of `std::vector`s linked together, balancing fast growth at both ends with decent cache locality.
While `std::vector` is the default, C++ offers other sequence containers. `std::array` provides zero-overhead fixed-size arrays. `std::list` provides doubly-linked lists. `std::deque` provides a double-ended queue. The most critical lesson is understanding why `std::list` performs terribly in practice due to CPU caching.
Explanation
**1. std::array (Fixed Size)**
`std::array<int, 5>` is a thin wrapper around a raw C-array (`int arr[5]`). It allocates exactly where it is declared (usually the stack). It cannot grow or shrink. Use it when the size is known at compile time. It provides bounds checking (`.at()`) and knows its own size (`.size()`), making it much safer than raw C-arrays. Crucially, unlike raw C-arrays, `std::array` does not automatically decay into a pointer when passed to a function.
**2. std::list (Doubly-Linked List)**
Every element is allocated separately on the heap with pointers to the next and previous nodes. While inserting in the middle is O(1) *theoretically*, traversing to find the insertion point is O(N). More importantly, because nodes are scattered across the heap, iterating a `std::list` causes constant CPU cache misses. In modern hardware, cache locality beats algorithmic complexity for small to medium N. Avoid `std::list` unless you are storing massive objects where copying is prohibitively expensive.
**3. std::deque (Double-Ended Queue)**
Erasing or inserting at the front of a `std::vector` is O(N) because it must shift all subsequent elements left to close the gap. A `std::deque` solves this, allowing O(1) insertions and deletions at both the front and the back. Unlike a vector, it is not one massive contiguous block. It is typically an array of pointers to fixed-size arrays (chunks). When the front is full, it just allocates a new chunk. It gives you the O(1) `push_front` of a list, but maintains the cache-friendliness of a vector. If you need a queue, `std::deque` is the answer.
**Real-world Engineering:** `std::deque` is strictly superior to a vector when implementing a task scheduler queue or a sliding window algorithm where you constantly push to the back and pop from the front. `std::list` is useful when implementing an LRU cache where you must pluck nodes from the middle and move them to the front without invalidating references to them.
Code examples
Using std::array vs std::deque
#include <iostream>
#include <array>
#include <deque>
int main() {
// std::array: Size must be a compile-time constant.
// Lives on the stack. Ultra-fast, zero heap allocations.
std::array<int, 3> arr = {1, 2, 3};
std::cout << arr.size() << '\n'; // Safe size checking
// std::deque: Grows at both ends.
std::deque<int> dq;
dq.push_back(10); // O(1)
dq.push_front(20); // O(1) - Impossible to do efficiently with vector
// Elements are accessible via index, just like vector
std::cout << "Front: " << dq[0] << '\n'; // Prints 20
return 0;
}`std::array` replaces raw C-arrays for fixed data. `std::deque` replaces `std::vector` when you specifically need to insert/remove from the front frequently.
Key points
- Avoid std::list: Unless you have a hyper-specific reason (iterator stability + massive objects), `std::list` is a performance trap due to cache misses.
- Deque for Queues: Use `std::deque` when you need O(1) pushes and pops at both the front and the back.
Common mistakes
- Defaulting to std::list for middle insertions: Developers often use `std::list` to avoid the O(N) shifting cost of inserting into the middle of a vector. However, a vector's `memmove` shifts are so optimized by the CPU that a vector easily outperforms a list for insertions unless the list has thousands of massive objects.
Recall questions
- Why is `std::list` generally much slower to iterate over than `std::vector`?
- How is `std::deque` structured internally to allow O(1) insertions at both ends?
- What is the primary advantage of `std::array` over a raw C-style array (`int arr[]`)?
Questions & answers
A candidate needs to implement a First-In-First-Out (FIFO) queue for a breadth-first search (BFS). They use a `std::vector` and call `vec.erase(vec.begin())` to remove the front element. Why is this a critical mistake?
Erasing the first element of a vector forces the CPU to shift every single subsequent element left by one position. This makes the dequeue operation O(N), turning a BFS into O(V * E). The correct container is `std::deque` (or `std::queue`), which provides O(1) `pop_front()`.
Approach: Understand the performance characteristics of front-removal in different sequence containers.
When would you actually choose `std::list` over `std::vector`?
When the elements are extremely large/expensive to copy (meaning shifting them in a vector is a bottleneck), AND you need to perform frequent insertions/deletions in the middle of the container using existing iterators without invalidating them.
Approach: Identify the rare edge cases where linked lists outperform contiguous arrays.