Sequence Containers: vector, deque, list, array
Explore the sequence containers in the STL — vector, deque, list, forward_list, and array. Learn their performance trade-offs, memory layouts, and iterator invalidation rules.
What Are Sequence Containers?
Sequence containers store elements in a strict linear order. The STL provides five sequence containers, each optimized for different access and mutation patterns:
- std::vector — dynamic array, contiguous memory
- std::deque — double-ended queue, fast insertion at both ends
- std::list — doubly-linked list
- std::forward_list — singly-linked list
- std::array — fixed-size array, stack-allocated
Choosing the right container is one of the most impactful performance decisions you will make in C++. The key factors are access pattern, insertion/deletion pattern, and cache locality.
std::vector — The Default Choice
std::vector is the most commonly used container. It stores elements in a single contiguous block of memory, giving it excellent cache performance and O(1) random access. Appending elements with push_back is amortized O(1) because the vector doubles its capacity when full.
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums; // empty vector
nums.reserve(100); // pre-allocate for 100 elements (no reallocation)
for (int i = 0; i < 10; ++i) {
nums.push_back(i * i); // amortized O(1)
}
// Size vs capacity
std::cout << "Size: " << nums.size() << '\n'; // 10
std::cout << "Capacity: " << nums.capacity() << '\n'; // >= 100
// Random access — O(1)
std::cout << "Element 3: " << nums[3] << '\n'; // 9
std::cout << "Element 3: " << nums.at(3) << '\n'; // 9 (bounds-checked)
// Erase-remove idiom (pre-C++20)
nums.erase(std::remove_if(nums.begin(), nums.end(),
[](int x) { return x > 50; }),
nums.end());
// C++20: std::erase_if (cleaner)
std::erase_if(nums, [](int x) { return x > 30; });
// Range-based for loop
for (int n : nums) {
std::cout << n << ' ';
}
std::cout << '\n';
}deque, list, and forward_list
std::deque provides O(1) insertion and deletion at both the front and back, but uses a segmented memory layout (array of fixed-size blocks) rather than a single contiguous allocation. std::list is a doubly-linked list offering O(1) insertion/deletion anywhere given an iterator, at the cost of poor cache locality. std::forward_list is a singly-linked list that uses less memory per node but only supports forward traversal.
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>
int main() {
// deque — O(1) push_front and push_back
std::deque<int> dq;
dq.push_front(1); // O(1) — vector cannot do this efficiently
dq.push_back(2); // O(1)
dq.push_front(0); // O(1)
// dq: {0, 1, 2}
// list — O(1) insert/erase at any position with iterator
std::list<std::string> names = {"Alice", "Charlie", "Eve"};
auto it = std::next(names.begin()); // points to "Charlie"
names.insert(it, "Bob"); // O(1) insert before "Charlie"
names.erase(it); // O(1) erase "Charlie"
// names: {"Alice", "Bob", "Eve"}
// list has splice — O(1) move of entire sublists
std::list<std::string> more = {"Frank", "Grace"};
names.splice(names.end(), more); // moves all of 'more' into 'names'
// names: {"Alice", "Bob", "Eve", "Frank", "Grace"}
// more is now empty
// forward_list — singly linked, no size(), push_front only
std::forward_list<int> fl = {3, 1, 4, 1, 5};
fl.push_front(0);
fl.sort(); // member sort — O(n log n), stable
fl.unique(); // remove consecutive duplicates
// fl: {0, 1, 3, 4, 5}
for (int v : fl) std::cout << v << ' ';
std::cout << '\n';
}std::array — Fixed-Size, Zero Overhead
std::array wraps a C-style array in a proper class, providing .size(), .at(), iterators, and compatibility with all STL algorithms — with zero overhead compared to a raw T[N].
#include <array>
#include <algorithm>
#include <iostream>
int main() {
std::array<int, 5> arr = {5, 2, 8, 1, 9};
std::sort(arr.begin(), arr.end()); // works with STL algorithms
std::cout << "Size: " << arr.size() << '\n'; // constexpr — known at compile time
std::cout << "Front: " << arr.front() << '\n'; // 1
std::cout << "Back: " << arr.back() << '\n'; // 9
// Bounds-checked access
try {
arr.at(10); // throws std::out_of_range
} catch (const std::out_of_range& e) {
std::cout << "Out of range: " << e.what() << '\n';
}
// Compile-time size via std::tuple_size
constexpr std::size_t n = std::tuple_size_v<decltype(arr)>; // 5
static_assert(n == 5);
}Choosing the Right Sequence Container
Use this decision guide:
Use std::vector (the default) when you need random access, cache-friendly iteration, or push/pop at the back. The vast majority of code should use vector.
Use std::deque when you need frequent insertion/removal at both front and back (e.g., a sliding window, BFS queue).
Use std::list when you need O(1) insertion/removal in the middle given an iterator, or when you need splice() to move sublists between lists without copying.
Use std::forward_list when memory per node matters and you only need forward traversal.
Use std::array when the size is known at compile time and will never change.
Performance note: Due to CPU cache effects, std::vector often outperforms std::list even for middle insertions on modern hardware, up to surprisingly large sizes (thousands of elements). Always measure before choosing a linked list.
Each container has different rules for when iterators, pointers, and references become invalid:
vector — Insertion that triggers reallocation invalidates all iterators. Insertion without reallocation invalidates iterators at or after the insertion point. Erasure invalidates iterators at or after the erasure point.
deque — Insertion at the front or back invalidates all iterators but not references/pointers to existing elements. Insertion in the middle invalidates everything. Erasure at front/back only invalidates the erased element's iterator.
list / forward_list — Insertion and erasure never invalidate iterators, references, or pointers to other elements. Only the erased element's iterator is invalidated.
array — Iterators are never invalidated (the array cannot change size).
A common bug is modifying a vector inside a range-based for loop. If a push_back triggers reallocation, the loop's hidden iterators become dangling.
If you know (or can estimate) how many elements a vector will hold, call reserve() before filling it. This pre-allocates memory and avoids costly reallocations:
- reserve(n) changes capacity but not size — no elements are added.
- resize(n) changes size — it actually default-constructs elements.
- shrink_to_fit() is a non-binding request to reduce capacity to match size.
For hot loops that build vectors, a single reserve() call can cut allocation overhead dramatically. Measure with large data sets to see the difference.
std::vectoris the default choice — contiguous memory means cache-friendly iteration and O(1) random access- Use
reserve()to pre-allocate vector memory when the approximate size is known std::dequeprovides O(1) push/pop at both front and back, but is not contiguousstd::listoffers O(1) insert/erase with an iterator and never invalidates other iteratorsstd::arrayis a zero-overhead wrapper around C arrays with full STL compatibility- Iterator invalidation rules differ per container — know them to avoid dangling iterator bugs
Quiz — Test Your Knowledge
(15 XP)1. Which sequence container provides O(1) amortized `push_back` and contiguous memory layout?
2. What happens to all vector iterators when a `push_back` triggers reallocation?
3. What is the difference between `reserve(n)` and `resize(n)` on a vector?