In the previous chapter we used std::vector, the container you should reach for by default. But vector is not perfect for every job. Adding at the front is slow, inserting in the middle shifts everything, and sometimes you do not need a growing container at all, just a safer fixed-size array.
The STL gives us three more sequence containers for exactly these situations:
std::array– a fixed-size array that knows its own size (C++11)std::list– a doubly linked list with fast insertion and deletion anywhere (when you already have an iterator to the position)std::deque– a "double-ended queue" with fast insertion at both ends and random access
In this chapter we will learn how each one works inside, which operations are fast or slow and why, and how to choose between them.
Quick Recap: What Is a Sequence Container?
A sequence container stores elements in a linear order that you control: the element you put in position 3 stays in position 3 until you move it.
This is different from the associative containers (set, map) we will see later, which decide the order themselves. vector, array, list, forward_list and deque are all sequence containers.
The main difference between them is how the elements are laid out in memory, and that layout decides the cost of every operation:
std::array<int,4> one fixed block (lives inside the object itself)
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘
std::vector<int> one growing block on the heap
┌────┬────┬────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │ │ │ (spare capacity)
└────┴────┴────┴────┴────┴────┘
std::deque<int> several fixed-size blocks + a "map" of block pointers
map: [ • ][ • ][ • ]
│ │ └──► ┌────┬────┬────┐
│ └───────► ┌────┬────┬────┐
└────────────► ┌────┬────┬────┐
std::list<int> separate nodes linked in both directions
┌────┐ ┌────┐ ┌────┐
│ 10 │ ⇄ │ 20 │ ⇄ │ 30 │
└────┘ └────┘ └────┘std::array – A Fixed-Size Array Done Right
A C-style array like int marks[5]; has several problems: it does not know its own size, it silently "decays" to a pointer when passed to a function, you cannot copy it with =, and a == b on two arrays compares their addresses, not their contents (this comparison is deprecated since C++20).
std::array<T, N>(header<array>, C++11) is a fixed-size container that wraps a plain C array ofNelements of typeT. The sizeNmust be a compile-time constant and is part of the type.
It has zero overhead: no heap allocation, no extra pointer, just the array itself. But it behaves like a proper STL container with size(), iterators, at(), copying and comparison.
#include <array>
#include <iostream>
#include <stdexcept>
int main() {
std::array<int, 5> marks = {72, 85, 90, 64, 78};
std::cout << "Size: " << marks.size() << '\n';
std::cout << "First: " << marks.front() << ", Last: " << marks.back() << '\n';
marks[3] = 70; // no bounds check
int total = 0;
for (int m : marks) total += m;
std::cout << "Total: " << total << '\n';
try {
std::cout << marks.at(5) << '\n'; // bounds-checked
} catch (const std::out_of_range& e) {
std::cout << "Caught out_of_range\n";
}
std::array<int, 5> copy = marks; // whole-array copy works
copy.fill(0);
std::cout << "marks[0] = " << marks[0] << ", copy[0] = " << copy[0] << '\n';
std::cout << std::boolalpha << "Equal? " << (marks == copy) << '\n';
}Output:
Size: 5
First: 72, Last: 78
Total: 395
Caught out_of_range
marks[0] = 72, copy[0] = 0
Equal? falseNotice three things:
marks[3]does no bounds checking. Accessingmarks[5]would be undefined behavior, exactly like a C array.marks.at(5)checks the index and throwsstd::out_of_range(from<stdexcept>). We coveredtry/catchin the Exception Handling chapter.copy = markscopies all 5 elements, and==compares element by element. With C arrays the first does not compile and the second compares addresses.
Size Is Part of the Type
#include <array>
#include <iostream>
void printAll(const std::array<int, 4>& a) { // size is part of the type
for (int x : a) std::cout << x << ' ';
std::cout << "(size " << a.size() << ")\n";
}
int main() {
std::array<int, 4> a = {1, 2, 3, 4};
printAll(a);
auto b = std::to_array({10, 20, 30, 40}); // C++20: size deduced
printAll(b);
std::array<int, 4> zeros{}; // value-initialised: all 0
printAll(zeros);
std::array<int, 4> garbage; // NOT initialised (like int g[4];)
(void)garbage;
std::cout << "sizeof(a) = " << sizeof(a) << " (same as int[4] = " << sizeof(int[4]) << ")\n";
}Output:
1 2 3 4 (size 4)
10 20 30 40 (size 4)
0 0 0 0 (size 4)
sizeof(a) = 16 (same as int[4] = 16)std::array<int, 4>andstd::array<int, 5>are different types. A function takingstd::array<int, 4>cannot accept an array of 5. (If you need "any size", make the function a template, as in the Templates chapter, or usestd::vector.)std::to_array(C++20) deduces the size for you. Since C++17 you can also writestd::array b = {10, 20, 30, 40};using class template argument deduction.std::array<int, 4> zeros{};zero-initialises every element. Without the{}, elements of a built-in type such asintare left uninitialised (in a local variable), and reading them is undefined behavior.sizeof(a)equals the size of the raw array:std::arraystores nothing extra.
Because the size never changes, std::array has no push_back, insert or erase. If you need those, you want vector.
std::list – A Doubly Linked List
std::list<T>(header<list>) is a doubly linked list. Every element lives in its own heap-allocated node that holds the value plus a pointer to the previous node and a pointer to the next node.
This layout has two big consequences:
Inserting or erasing at a known position is O(1). We only relink a couple of pointers; no other element is moved.
There is no random access. To reach the 500th element you must walk 500 nodes, so there is no
operator[]and noit + 2. List iterators are bidirectional: they can only do++and--.
Here is what inserting 25 before 30 looks like:
Before: [20] ⇄ [30]
Step 1: create node [25]
Step 2: 25.prev = 20, 25.next = 30
Step 3: 20.next = 25, 30.prev = 25
After: [20] ⇄ [25] ⇄ [30] (no element was copied or moved)Basic Operations
#include <iostream>
#include <list>
void show(const std::list<int>& l) {
for (int x : l) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
std::list<int> l = {20, 30, 40};
l.push_front(10);
l.push_back(50);
show(l); // 10 20 30 40 50
auto it = l.begin();
++it; ++it; // points to 30 (no it + 2 for list!)
auto inserted = l.insert(it, 25); // insert before 30, O(1)
show(l);
std::cout << "it still points to " << *it << '\n';
std::cout << "inserted points to " << *inserted << '\n';
it = l.erase(it); // erase 30, returns next element
show(l);
std::cout << "after erase, it points to " << *it << '\n';
l.pop_front();
l.pop_back();
show(l);
std::cout << "size = " << l.size() << '\n';
}Output:
10 20 30 40 50
10 20 25 30 40 50
it still points to 30
inserted points to 25
10 20 25 40 50
after erase, it points to 40
20 25 40
size = 3Key points from this program:
push_frontandpush_backare both O(1).insert(it, value)inserts beforeitand returns an iterator to the new element.After the insert,
itstill points to 30. In a list, inserting never invalidates any iterator or reference.erase(it)invalidates only iterators to the erased element. That is why we writeit = l.erase(it);–erasereturns an iterator to the element after the erased one.We had to write
++it; ++it;becausel.begin() + 2does not compile for a list. (std::next(it, 2)also works, but still walks the nodes one by one: O(n).)
Special List Operations
Because a list can rearrange nodes just by changing pointers, it has some member functions that other containers do not have:
#include <iostream>
#include <list>
void show(const char* label, const std::list<int>& l) {
std::cout << label;
for (int x : l) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
std::list<int> a = {5, 1, 4, 1, 3, 1, 2};
a.remove(1); // removes every 1
show("remove(1): ", a);
a.remove_if([](int x) { return x % 2 == 0; }); // remove even numbers
show("remove_if even: ", a);
std::list<int> b = {9, 3, 7, 3, 3, 1};
b.sort(); // member sort: std::sort needs random access
show("sort(): ", b);
b.unique(); // removes CONSECUTIVE duplicates
show("unique(): ", b);
a.sort();
a.merge(b); // both must be sorted; b becomes empty
show("merge: ", a);
std::cout << "b.size() = " << b.size() << '\n';
std::list<int> c = {100, 200};
auto pos = a.begin();
++pos;
a.splice(pos, c); // move ALL nodes of c before pos, O(1)
show("splice: ", a);
std::cout << "c.empty() = " << std::boolalpha << c.empty() << '\n';
a.reverse();
show("reverse(): ", a);
}Output:
remove(1): 5 4 3 2
remove_if even: 5 3
sort(): 1 3 3 3 7 9
unique(): 1 3 7 9
merge: 1 3 3 5 7 9
b.size() = 0
splice: 1 100 200 3 3 5 7 9
c.empty() = true
reverse(): 9 7 5 3 3 200 100 1 (The [](int x) { return x % 2 == 0; } part is a lambda: a small unnamed function written inline. Here it simply answers "is x even?". We study lambdas fully in the Lambda Expressions chapter.)
Member | What it does | Cost |
|---|---|---|
| Erases every matching element | O(n) |
| Sorts the list (stable) | O(n log n) |
| Removes consecutive duplicates only, so sort first | O(n) |
| Merges two sorted lists; | O(n + m) |
| Moves all nodes of | O(1) |
| Reverses the order of the nodes | O(n) |
Why does list have its own sort()? The general std::sort algorithm needs random-access iterators (it jumps around in the middle of the range), which a list does not provide. std::sort(l.begin(), l.end()) will not compile. The member sort() uses a merge sort that only relinks nodes.
The Real Cost of a Linked List
On paper, a list wins for insertion in the middle. In practice, vector is usually faster even then, for two reasons:
Finding the position is O(n) in a list anyway, and walking scattered nodes is slow because each node can be anywhere in memory (poor cache locality).
Memory overhead: each
intin a list carries two pointers (16 bytes on a 64-bit system) plus allocator overhead, and every insert is a separate heap allocation.
Use std::list when you truly need its special powers: you keep iterators to elements and insert/erase around them often, you need iterators and references to stay valid, or you need splice.
A Note on std::forward_list
std::forward_list (header <forward_list>, C++11) is a singly linked list: one pointer per node, forward iteration only. It has insert_after / erase_after instead of insert / erase (you cannot go back to fix the previous node's pointer), and it deliberately has no size() member, to save space. Use it only when memory per node really matters.
std::deque – Fast at Both Ends
std::deque<T>(header<deque>, pronounced "deck") is a double-ended queue: a sequence that supports fast insertion and removal at both the front and the back, together with random access by index.
#include <deque>
#include <iostream>
void show(const std::deque<int>& d) {
for (int x : d) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
std::deque<int> d = {3, 4, 5};
d.push_front(2);
d.push_front(1);
d.push_back(6);
show(d);
std::cout << "d[0] = " << d[0] << ", d[4] = " << d[4] << '\n'; // random access
std::cout << "front = " << d.front() << ", back = " << d.back() << '\n';
d.pop_front();
d.pop_back();
show(d);
d.insert(d.begin() + 2, 99); // middle insert: O(n), allowed but slow
show(d);
d.erase(d.begin() + 2);
show(d);
}Output:
1 2 3 4 5 6
d[0] = 1, d[4] = 5
front = 1, back = 6
2 3 4 5
2 3 99 4 5
2 3 4 5 deque has almost the same interface as vector ([], at, begin() + 2, insert, erase) plus push_front and pop_front. A vector has no push_front because adding at the front would shift every element: O(n).
How Does a Deque Work Inside?
The C++ standard does not dictate the exact layout, but every major implementation (GCC's libstdc++, LLVM's libc++, Microsoft's STL) uses the same idea: elements are stored in fixed-size blocks (chunks), and a small central array, often called the map, holds pointers to those blocks.
map (array of block pointers)
┌─────┬─────┬─────┬─────┐
│ • │ • │ • │ │
└──┼──┴──┼──┴──┼──┴─────┘
│ │ │
▼ ▼ ▼
┌──┬──┬──┐ ┌──┬──┬──┐ ┌──┬──┬──┐
│ │ 1│ 2│ │ 3│ 4│ 5│ │ 6│ │ │
└──┴──┴──┘ └──┴──┴──┘ └──┴──┴──┘
▲ ▲
front backpush_front: if the first block has room before the front, use it; otherwise allocate a new block and add its pointer to the front of the map. Existing elements never move.
push_back: the same at the other end.
d[i]: compute which block and which slot inside it, then follow one pointer. Still O(1), but a little slower than a vector's single address calculation.
insert in the middle: elements on one side must shift, so it is O(n).
Because the blocks are not one contiguous array, a deque has no data() member and no capacity() / reserve(). You cannot pass its contents to a C function expecting an int*.
Deque Keeps References Valid at the Ends
Since existing elements never move when we add at the ends, references and pointers to them remain valid. Compare this with vector, which may reallocate its whole buffer:
#include <deque>
#include <iostream>
#include <vector>
int main() {
std::deque<int> d = {1, 2, 3};
int& ref = d[1]; // reference to the element 2
for (int i = 0; i < 1000; ++i) d.push_back(i);
for (int i = 0; i < 1000; ++i) d.push_front(i);
std::cout << "deque: ref still valid, ref = " << ref << '\n';
std::vector<int> v = {1, 2, 3};
std::cout << "vector capacity before: " << v.capacity() << '\n';
// int& vref = v[1]; v.push_back(4); // vref would dangle if capacity is exceeded
v.push_back(4);
std::cout << "vector capacity after: " << v.capacity() << " (storage moved)\n";
}Output:
deque: ref still valid, ref = 2
vector capacity before: 3
vector capacity after: 6 (storage moved)(The exact vector capacity after growth is implementation-specific; GCC doubles it. The point is that the storage moved.)
The precise rule for deque is subtle and a favourite interview question:
push_front/push_back(andemplace_*): all iterators are invalidated, but references and pointers to elements stay valid. (The map may be reallocated, and iterators point into the map; the elements themselves stay put.)pop_front/pop_back: only iterators and references to the erased element are invalidated (forpop_back, alsoend()).insert/erasein the middle: everything is invalidated.
Complexity Comparison
Operation |
|
|
|
|
|---|---|---|---|---|
Access by index | O(1) | O(1) | O(1) | not available (O(n) walk) |
Insert/erase at back | not available | O(1) amortized | O(1) | O(1) |
Insert/erase at front | not available | O(n) | O(1) | O(1) |
Insert/erase in middle (iterator given) | not available | O(n) | O(n) | O(1) |
Search for a value | O(n) | O(n) | O(n) | O(n) |
Iterator category | contiguous | contiguous | random access | bidirectional |
Contiguous memory? | yes | yes | no (blocks) | no (nodes) |
Size changes? | no (fixed) | yes | yes | yes |
Memory overhead per element | none | small (spare capacity) | small (block map) | two pointers + allocation |
Which One Should I Use?
Size known at compile time and never changes →
std::array.Default choice for a growing sequence →
std::vector.Need to add/remove at the front as well as the back (sliding windows, BFS queues, undo history with a limit) →
std::deque.Need stable iterators/references and frequent insert/erase at positions you already hold, or
splice(for example the classic LRU cache:list+ hash map) →std::list.
Common Mistakes
Using
std::sorton a list. It does not compile; calll.sort()instead.Writing
l.begin() + 3on a list. List iterators are bidirectional, not random access. Usestd::next(l.begin(), 3)and remember it costs O(n).Calling
unique()on an unsorted list and expecting all duplicates to disappear. It only removes duplicates that are next to each other.Using an iterator after
erase.l.erase(it); ++it;is undefined behavior becauseitnow refers to a destroyed node. Writeit = l.erase(it);.Keeping a deque iterator across
push_front/push_back. References survive, iterators do not.Forgetting
{}onstd::arrayof built-in types.std::array<int, 3> a;inside a function holds garbage.Reaching for
list"because insertion is O(1)". If you first have to search for the position, the search is O(n) and usually slower than a vector's shift.
Interview / GATE-Style Questions
Q1. Why does std::vector not have push_front, while std::deque does?
A vector stores elements in one contiguous block starting at the front. Adding at the front would require shifting every element one position right, O(n). The standard only provides operations that can be done efficiently for a container, so vector leaves it out. A deque stores elements in separate blocks and can add a new block before the first one, making push_front O(1).
Q2. After d.push_back(x) on a std::deque, which of these are still valid: iterators, references, pointers to existing elements?
References and pointers to existing elements remain valid; all iterators (including begin() and end()) are invalidated. For a std::vector, if the size exceeded the capacity, all three would be invalidated.
Q3. What is the time complexity of erasing an element from a std::list given an iterator to it? And given only its value?
Given an iterator: O(1), because only the neighbouring nodes' pointers are updated. Given only the value: O(n), because the list must first be traversed to find the element (l.remove(value) walks the whole list).
Q4. What is the output? std::list<int> l = {3, 1, 3, 3, 2, 1}; l.unique(); then print l.
3 1 3 2 1. Only the consecutive pair of 3s is collapsed into one. To remove all duplicates, call l.sort() first, which gives 1 2 3 after unique().
Q5. What is the difference between int a[5] and std::array<int, 5> a?
Both have the same size and layout and no heap allocation. But std::array knows its size (a.size()), does not decay to a pointer when passed to a function, can be copied/assigned and compared with ==, supports at() with bounds checking, and works with STL algorithms through begin()/end().
Summary
std::array<T, N>is a fixed-size, zero-overhead wrapper around a C array. The size is part of the type; it supports copying, comparison andat().std::listis a doubly linked list: O(1) insert/erase at any position you hold an iterator to, no random access, iterators stay valid except for erased elements, and special members likesort,splice,mergeandunique.std::dequegives O(1) push/pop at both ends plus random access, using blocks of elements; its memory is not contiguous.For most problems,
vectoris still the right default. Choose another sequence container only when its specific strength matters.
In the next chapter, stack, queue & priority_queue, we will see how the STL builds these classic data structures on top of containers like deque and vector.