These are the notes for C++ episode 22, the second STL episode. In episode 21 you met vector: fast at the back, fast to index, but slow when you insert anywhere else. Here we fix that twice. First at the front, with std::deque. Then in the middle, with std::list, a doubly linked list that you will invent yourself. Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; the outputs and error messages are copied from those runs. Timings are in milliseconds and change a little from run to run and machine to machine; the ratio between them is what matters.
The problem: a hospital OPD queue
The OPD (outpatient department) of a hospital is a waiting line:
| What happens | Where in the line | The operation we need |
|---|---|---|
| A new patient takes a token | joins at the back | add at the back |
| An ambulance brings an emergency | goes straight to the front | add at the front |
| The doctor calls the next patient | from the front, who then leaves | remove from the front |
Step 1: the obvious way, a vector
A vector can do all three: push_back, insert(begin(), x) and erase(begin()).
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
vector<string> opd = {"Asha", "Ravi"};
opd.push_back("Meena"); // joins at the back
opd.insert(opd.begin(), "Emergency"); // goes to the front
cout << "Doctor calls: " << opd[0] << endl;
opd.erase(opd.begin()); // leaves from the front
for (string p : opd) cout << p << " ";
cout << endl;
return 0;
}
Output:
Doctor calls: Emergency
Asha Ravi Meena
It works, for four patients.
Step 2: scale it up, and time it
A busy city hospital: 200000 emergencies, each inserted at the front. To measure how long it takes we use <chrono>, C++'s stopwatch library:
steady_clock::now()reads a clock that only moves forward (it is not changed when your computer's time is adjusted).end - startis how much time passed, as a duration.duration_cast<milliseconds>(...)converts that duration to milliseconds, and.count()gives the number.using namespace std::chrono;lets us writesteady_clockinstead ofstd::chrono::steady_clock.
#include <iostream>
#include <vector>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
auto start = steady_clock::now();
vector<int> opd;
for (int i = 0; i < 200000; i++)
opd.insert(opd.begin(), i); // emergency: to the front
auto end = steady_clock::now();
cout << "vector, 200000 at the front: "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
return 0;
}
Output:
vector, 200000 at the front: 1857 ms
Almost two seconds for one queue, and every new emergency waits longer than the one before.
Timings in these notes come from one run; yours will differ with the machine and how busy it is (in the video's run the same program took several seconds). What stays the same is the shape: front inserts into a vector take seconds, the deque takes about a millisecond, and the list wins in the middle.
Why the front of a vector is slow
A vector keeps every element side by side in one block of memory, starting at index 0. The only free space is at the back. So to put a new patient at index 0, every patient already in the line must shift one step to the right:
before: [0] Asha [1] Ravi [2] Meena [3] (free)
insert "Emergency" at the front: Meena moves to [3], Ravi to [2], Asha to [1]
after: [0] Emergency [1] Asha [2] Ravi [3] Meena
With n patients, one front insert costs n moves. 200000 front inserts cost about 200000 × 200000 / 2 = 20 billion element moves. We need a line that is open at both ends.
Step 3: deque, a line open at both ends
Real-life example: a smart receptionist doesn't keep the OPD register on one long sheet. She uses short loose pages, each holding a few names. An emergency? She adds a new page at the front and writes there; nobody is copied. Patient number 7? She works out "page 2, line 3" and jumps straight there.
| At the OPD register | In C++ |
|---|---|
| short pages, not one long sheet | deque stores elements in fixed-size blocks |
| a new page at the front or the back | push_front / push_back in constant time |
| "patient 7 = page 2, line 3" | opd[7] still works, instantly |
std::deque (pronounced "deck") stands for double-ended queue: a queue that is open at both ends. Include <deque>.
| Method | What it does |
|---|---|
push_back(x) / push_front(x) |
add at the back / at the front |
pop_back() / pop_front() |
remove the last / the first element (returns nothing) |
front() / back() |
the first / the last element |
d[i], d.at(i) |
element number i (at checks the range) |
size(), empty() |
how many elements; whether there are none |
#include <iostream>
#include <deque>
#include <string>
using namespace std;
int main() {
deque<string> opd = {"Asha", "Ravi"};
opd.push_back("Meena"); // joins at the back
opd.push_front("Emergency"); // goes to the front
cout << "Doctor calls: " << opd.front() << endl;
opd.pop_front(); // leaves from the front
cout << "Next: " << opd[0] << ", last: " << opd.back() << endl;
cout << "Waiting: " << opd.size() << endl;
return 0;
}
Output:
Doctor calls: Emergency
Next: Asha, last: Meena
Waiting: 3
The race at the front
#include <iostream>
#include <vector>
#include <deque>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
auto start = steady_clock::now();
vector<int> v;
for (int i = 0; i < 200000; i++) v.insert(v.begin(), i);
auto end = steady_clock::now();
cout << "vector: "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
start = steady_clock::now();
deque<int> d;
for (int i = 0; i < 200000; i++) d.push_front(i);
end = steady_clock::now();
cout << "deque: "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
return 0;
}
Output:
vector: 1851 ms
deque: 0 ms
0 ms doesn't mean no work: all 200000 push_front calls together took less than one millisecond. The time of one push_front does not grow with the size of the deque; that is what constant time means (written O(1)). One front insert on a vector is O(n): it grows with n.
Step 4: the next problem, the middle
A text editor stores your essay letter by letter. You go back to the middle of a 400000-letter essay to add a paragraph: the cursor is at position 200000, not the front, not the back. Every key you press inserts one letter at the cursor, and the cursor moves one step forward.
#include <iostream>
#include <deque>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
deque<char> essay(400000, 'a'); // a long essay
int cursor = 200000; // the cursor, in the middle
auto start = steady_clock::now();
for (int i = 0; i < 150000; i++) {
essay.insert(essay.begin() + cursor, 'x'); // type a key
cursor++;
}
auto end = steady_clock::now();
cout << "deque, typing in the middle: "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
return 0;
}
Output:
deque, typing in the middle: 1534 ms
Why it's slow: a deque is only fast at its two ends. In the middle it still shifts about half of the letters, for every key. The real problem is that the letters sit side by side at all.
Step 5: inventing the linked list
Real-life example: a train. The coaches don't sit in one big box; each coach is its own vehicle, coupled to the coach in front and the coach behind. To add a pantry car in the middle, the railway staff uncouple two coaches and couple the pantry car between them. No other coach moves, however long the train is.
| On the railway | In C++ |
|---|---|
| a coach | a node: one value + links |
| couplings to the coach in front and behind | prev and next links: a doubly linked list |
| uncouple two coaches, couple the new one | list.insert(it, x): two links change, constant time |
| to find coach 7, walk from the engine | no index: you walk with an iterator |
- A node is a small piece of memory holding one value plus links (addresses) to other nodes.
- A linked list is a sequence of nodes connected by links, instead of sitting side by side.
- In a doubly linked list each node links both to the next node and to the previous one, so you can walk both ways.
std::listis a doubly linked list.
Engine <-> A1 <-> B1 <-> B2
insert Pantry before B1: A1.next = Pantry, Pantry.prev = A1, Pantry.next = B1, B1.prev = Pantry
Engine <-> A1 <-> Pantry <-> B1 <-> B2 (nothing else moved)
The price: there is no index. To reach B1 you start at the engine and follow links. So how do we tell the list where to insert? With a bookmark on one node: an iterator.
Iterators
An iterator is an object that points at one element of a container, like a bookmark:
| Code | Meaning |
|---|---|
train.begin() |
an iterator on the first element |
train.end() |
an iterator one past the last element (a "stop sign", not an element) |
it++ |
move the bookmark to the next element |
*it |
the element under the bookmark |
next(it, n) |
a new iterator n steps after it |
auto it = ... |
let the compiler write the long iterator type (list<string>::iterator) |
Step 6: std::list in action
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main() {
list<string> train = {"Engine", "A1", "B1", "B2"};
auto it = train.begin(); // a bookmark on "Engine"
it++;
it++; // now on "B1"
train.insert(it, "Pantry"); // couple a coach before B1
train.push_back("Guard");
for (string c : train) cout << c << " ";
cout << endl << "it is still on: " << *it << endl;
train.erase(it); // detach B1
for (string c : train) cout << c << " ";
cout << endl;
return 0;
}
Output:
Engine A1 Pantry B1 B2 Guard
it is still on: B1
Engine A1 Pantry B2 Guard
train.insert(it, "Pantry")inserts before the iterator.train.erase(it)removes the node under the iterator.- After the insert,
itis still valid and still onB1, because no node moved.
Iterator invalidation. With a vector, an insert can shift elements or move the whole block to bigger memory, so an iterator you saved earlier may point at the wrong element or at freed memory: using it is undefined behaviour. With a list, an iterator stays valid until its own node is erased. (A deque keeps references valid on push_front/push_back, but its iterators are invalidated by them.)
No [] on a list
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main() {
list<string> train = {"Engine", "A1", "B1", "B2"};
cout << train[2] << endl;
return 0;
}
g++ says:
main.cpp:8:18: error: no match for 'operator[]' (operand types are 'std::__cxx11::list<std::__cxx11::basic_string<char> >' and 'int')
A list has no index: there is no "page and line" to jump to, only links to follow. If you really need the third element, walk there:
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main() {
list<string> train = {"Engine", "A1", "B1", "B2"};
auto it = next(train.begin(), 2); // walk 2 steps
cout << *it << endl;
return 0;
}
Output:
B1
next(train.begin(), 2) takes 2 steps. For element 1000 it takes 1000 steps, so a list is for when you already hold an iterator, not for jumping around.
Step 7: the typing race, deque vs list
The list walks to the middle once, keeps that iterator as the cursor, and inserts before it 150000 times. Each new letter goes just before the cursor, exactly like an editor.
#include <iostream>
#include <deque>
#include <list>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
auto start = steady_clock::now();
deque<char> d(400000, 'a');
for (int i = 0; i < 150000; i++)
d.insert(d.begin() + 200000 + i, 'x');
auto end = steady_clock::now();
cout << "deque: "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
start = steady_clock::now();
list<char> l(400000, 'a');
auto cursor = next(l.begin(), 200000); // walk there once
for (int i = 0; i < 150000; i++)
l.insert(cursor, 'x');
end = steady_clock::now();
cout << "list: "
<< duration_cast<milliseconds>(end - start).count() << " ms" << endl;
return 0;
}
Output:
deque: 1536 ms
list: 21 ms
Most of the list's time is building the 400000 nodes and the one walk to the middle; each insert only changes two links.
Step 8: list superpowers, splice, remove and sort
splice moves nodes from one list into another by relinking them: nothing is copied, and it takes constant time for a whole list. remove(x) erases every element equal to x.
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main() {
list<string> express = {"Engine", "A1", "B1"};
list<string> slip = {"S1", "S2", "S3"}; // coaches of another train
express.splice(express.end(), slip); // move them all over
cout << express.size() << " " << slip.size() << endl;
express.remove("S2"); // detach every S2
for (string c : express) cout << c << " ";
cout << endl;
return 0;
}
Output:
6 0
Engine A1 B1 S1 S3
After the splice, express has 6 coaches and slip is empty.
Sorting a list
std::sort (from <algorithm>) needs random-access iterators: iterators that can jump by any amount and be subtracted (last - first). List iterators can only step one node at a time, so this fails:
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main() {
list<int> marks = {72, 45, 90, 61};
sort(marks.begin(), marks.end());
return 0;
}
The error is long; the key line is:
/usr/include/c++/13/bits/stl_algo.h:1948:50: error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>')
Use the list's own member function, which sorts by relinking nodes:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> marks = {72, 45, 90, 61};
marks.sort(); // the list sorts itself
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
45 61 72 90
Other useful list members: merge(other) (merge two sorted lists), reverse(), unique() (remove consecutive duplicates), remove_if(condition).
vector vs deque vs list
vector |
deque |
list |
|
|---|---|---|---|
| Memory | one block, side by side | fixed-size blocks | separate nodes with prev/next links |
v[i] index |
yes, O(1) | yes, O(1) | no (walk with next, O(n)) |
| Add/remove at the back | O(1)* | O(1) | O(1) |
| Add/remove at the front | O(n) | O(1) | O(1) |
| Insert/erase in the middle | O(n) | O(n) | O(1) with an iterator |
| Iterators after an insert | may be invalidated | invalidated | stay valid |
std::sort |
yes | yes | no: use l.sort() |
| Best for | the default choice | queues, both ends | many inserts/erases at a known position, splicing |
* amortized: usually O(1), occasionally a full copy when it grows (episode 21).
Start with a vector. It is usually the fastest for small and medium data, because the processor reads memory in a row very quickly (this is called being cache-friendly). Switch only when you measure a problem, the way we did with chrono. Practice question 2 below shows a case where the vector beats the list.
Common mistakes (and the real g++ messages)
| Mistake | Code | What g++ says / what happens | Fix |
|---|---|---|---|
| Indexing a list | train[2] |
error: no match for 'operator[]' (operand types are 'std::__cxx11::list<...>' and 'int') |
*next(train.begin(), 2) |
std::sort on a list |
sort(marks.begin(), marks.end()); |
error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>') |
marks.sort(); |
| Front inserts on a vector in a loop | v.insert(v.begin(), x); |
no message: about 1850 ms for 200000 items | deque + push_front |
pop_front() on an empty deque or list |
d.pop_front(); |
no message: undefined behaviour (anything can happen) | if (!d.empty()) d.pop_front(); |
Using pop_front() as if it returned the value |
string p = d.pop_front(); |
error: conversion from 'void' to non-scalar type 'std::string' {aka 'std::__cxx11::basic_string<char>'} requested |
string p = d.front(); d.pop_front(); |
| Using an iterator after erasing its node | train.erase(it); cout << *it; |
no message: undefined behaviour | it = train.erase(it); (erase returns the next iterator) |
Expecting insert to go after the iterator |
train.insert(it, x) |
x lands before *it |
train.insert(next(it), x) to insert after |
Mini project: an OPD token system
Read commands: join <name> (back of the line, gets a token number), emergency <name> (front of the line), call (the doctor calls the front patient). Refuse call safely when nobody is waiting.
#include <iostream>
#include <deque>
#include <string>
using namespace std;
int main() {
deque<string> opd;
int token = 0;
string cmd, name;
while (cin >> cmd) {
if (cmd == "join") {
cin >> name;
opd.push_back(name);
cout << name << " joins, token " << ++token << endl;
} else if (cmd == "emergency") {
cin >> name;
opd.push_front(name);
cout << name << " goes to the front" << endl;
} else if (cmd == "call") {
if (opd.empty()) {
cout << "Nobody waiting" << endl;
} else {
cout << "Doctor calls: " << opd.front() << endl;
opd.pop_front();
}
}
}
cout << "Still waiting: " << opd.size() << endl;
return 0;
}
Input:
join Asha
join Ravi
emergency Kabir
call
join Meena
call
call
call
call
Output:
Asha joins, token 1
Ravi joins, token 2
Kabir goes to the front
Doctor calls: Kabir
Meena joins, token 3
Doctor calls: Asha
Doctor calls: Ravi
Doctor calls: Meena
Nobody waiting
Still waiting: 0
Extensions: add a leave <name> command (use a list and remove), and print the whole line after every command.
Practice
- A music playlist: while a song plays, insert a song to play next (right after the current one), then skip to it.
- Time 100 inserts into the middle of a 100000-element
vectorvs a 100000-elementlist, where the list must walk to the middle each time. Who wins? - Merge two sorted lists into one sorted list without copying any element.
- Rotate a queue: move the front patient to the back k times, using a deque.
Solutions
1. insert goes before an iterator, so to insert after the current song, insert before next(now).
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main() {
list<string> playlist = {"Kesariya", "Tum Hi Ho", "Chaiyya Chaiyya"};
auto now = playlist.begin(); // playing: Kesariya
playlist.insert(next(now), "Kun Faya Kun"); // play this next
now++; // skip to the next song
cout << "Now playing: " << *now << endl;
for (string s : playlist) cout << s << " | ";
cout << endl;
return 0;
}
Output:
Now playing: Kun Faya Kun
Kesariya | Kun Faya Kun | Tum Hi Ho | Chaiyya Chaiyya |
2. The vector wins, by more than ten times here. Each list insert is O(1), but finding the middle means walking 50000 nodes scattered in memory, every time. The vector's shift is one fast block move over memory that sits in a row. A list only wins when you already hold the iterator (like the editor's cursor). (microseconds, written us here, are millionths of a second.)
#include <iostream>
#include <vector>
#include <list>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main() {
vector<int> v(100000, 0);
list<int> l(100000, 0);
auto start = steady_clock::now();
for (int i = 0; i < 100; i++) v.insert(v.begin() + v.size() / 2, i);
auto end = steady_clock::now();
cout << "vector: " << duration_cast<microseconds>(end - start).count() << " us" << endl;
start = steady_clock::now();
for (int i = 0; i < 100; i++) l.insert(next(l.begin(), l.size() / 2), i); // walk, then insert
end = steady_clock::now();
cout << "list: " << duration_cast<microseconds>(end - start).count() << " us" << endl;
return 0;
}
Output:
vector: 661 us
list: 10175 us
3. splice moves b's nodes into a, then sort relinks them in order (or use a.merge(b), which merges two already-sorted lists in one pass).
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> a = {10, 40, 70};
list<int> b = {20, 30, 90};
a.splice(a.end(), b); // move b's nodes to the end of a
a.sort();
for (int x : a) cout << x << " ";
cout << endl << "b now has " << b.size() << " items" << endl;
return 0;
}
Output:
10 20 30 40 70 90
b now has 0 items
4.
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> q = {1, 2, 3, 4, 5};
int k = 2;
for (int i = 0; i < k; i++) {
q.push_back(q.front()); // the front patient goes to the back
q.pop_front();
}
for (int x : q) cout << x << " ";
cout << endl;
return 0;
}
Output:
3 4 5 1 2
Quick quiz
What does this print?
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> l = {1, 2, 3};
auto it = l.begin();
it++;
l.insert(it, 9);
l.push_front(0);
cout << *it << " " << l.size();
return 0;
}
- A)
9 5 - B)
2 5 - C)
3 5 - D)
2 4
Answer
B) 2 5. it is moved to the second node, which holds 2. insert(it, 9) puts 9 before 2, and it stays on 2 because list iterators stay valid. push_front(0) adds 0 at the front. The list is 0 1 9 2 3: 5 elements.
2 5
Interview questions
- What is the difference between
vector,dequeandlist? Vector: one contiguous block, O(1) index, O(1) amortized at the back, O(n) elsewhere. Deque: blocks, O(1) index, O(1) at both ends, O(n) in the middle. List: doubly linked nodes, no index, O(1) insert/erase anywhere given an iterator. - Why can't you use
std::sorton astd::list?std::sortneeds random-access iterators (it subtracts and jumps); list iterators are bidirectional (one step forward or back). Uselist::sort(). - What is iterator invalidation? Give an example. An iterator that no longer points at a valid element after the container changes.
vector::push_backthat grows the capacity invalidates all iterators;list::insertinvalidates none;list::eraseinvalidates only the erased one. - Why is a list often slower than a vector even for inserts in the middle? Finding the position is O(n) in a list, and its nodes are scattered in memory (not cache-friendly), while a vector's shift is a fast contiguous move.
- What does
splicedo, and what is its complexity? It moves nodes from one list to another by relinking, without copying or allocating: O(1) for a whole list or one element. - Does
pop_front()return the removed element? No, it returnsvoid. Readfront()first, thenpop_front(). - What is a deque used for in algorithms? BFS queues, sliding-window maximum (monotonic deque), 0-1 BFS: anywhere you add or remove at both ends.
Glossary
| Term | Meaning | Example |
|---|---|---|
| OPD | Outpatient department: the part of a hospital where you take a token and wait to see a doctor | our queue example |
deque |
double-ended queue: a sequence open at both ends, stored in blocks, with an index | deque<string> opd; |
| double-ended queue | a queue where you can add and remove at both the front and the back | push_front, pop_back |
push_front / pop_front |
add at / remove from the front | opd.push_front("Emergency"); |
front() / back() |
the first / last element | opd.front() |
| constant time, O(1) | the time doesn't grow with the size of the container | d.push_front(x) |
| linear time, O(n) | the time grows in proportion to the size | v.insert(v.begin(), x) |
<chrono> |
C++'s time library (a stopwatch) | steady_clock::now() |
steady_clock |
a clock that only moves forward, for measuring durations | auto start = steady_clock::now(); |
duration_cast |
converts a duration to a unit, like milliseconds | duration_cast<milliseconds>(end - start).count() |
| millisecond / microsecond | a thousandth / a millionth of a second | 1851 ms |
| node | one piece of memory holding a value and links to other nodes | a coach |
| link | the stored address of another node | a coupling |
| linked list | a sequence of nodes connected by links instead of sitting side by side | a train |
| doubly linked list | each node links to both the next and the previous node | std::list |
std::list |
the STL's doubly linked list | list<string> train; |
| iterator | an object that points at one element, like a bookmark | auto it = train.begin(); |
begin() / end() |
an iterator on the first element / one past the last | for (auto it = l.begin(); it != l.end(); it++) |
*it |
the element the iterator points at | cout << *it; |
next(it, n) |
a new iterator n steps after it |
next(train.begin(), 2) |
| iterator invalidation | an old iterator becoming unusable after the container changes | a vector growing |
| random-access iterator | an iterator that can jump any distance and be subtracted | vector and deque iterators |
| bidirectional iterator | an iterator that can step one forward or one back | list iterators |
splice |
move nodes from one list to another by relinking, without copying | a.splice(a.end(), b); |
remove(x) |
erase every element equal to x | express.remove("S2"); |
list::sort() |
the list's own sort, which relinks nodes | marks.sort(); |
| undefined behaviour | code the C++ standard gives no meaning to: it may crash, or seem to work | pop_front() on an empty deque |
| cache-friendly | data laid out in a row in memory, which the processor reads very fast | a vector |
Summary
- Inserting at the front of a
vectorshifts every element: O(n) each, seconds for 200000 items. dequeis open at both ends:push_front,pop_front,push_back,pop_backin O(1), andd[i]still works. Perfect for queues.- Measure with
<chrono>:steady_clock::now()before and after,duration_cast<milliseconds>(end - start).count(). - In the middle, a deque still shifts. A linked list stores nodes linked to their neighbours, so an insert changes only two links.
std::listis a doubly linked list:insert(it, x)(beforeit) anderase(it)in O(1) through an iterator, and other iterators stay valid.- A list has no
[];next(it, n)walks.std::sortdoesn't work on it; uselist.sort().splicerelinks whole lists without copying;removeerases by value. - Default to
vector; usedequefor both ends andlistfor many inserts and erases at positions you already hold. Measure before you switch.
Next episode: STL 3, map and set: find a phone number by name, without walking the whole list.