SyntaxPilot
Courses/C++/Lesson 22

C++ · Lesson 22 of 40 · 11 min

STL 2: list and deque

queued

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 - start is 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 write steady_clock instead of std::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::list is 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, it is still valid and still on B1, 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

  1. A music playlist: while a song plays, insert a song to play next (right after the current one), then skip to it.
  2. Time 100 inserts into the middle of a 100000-element vector vs a 100000-element list, where the list must walk to the middle each time. Who wins?
  3. Merge two sorted lists into one sorted list without copying any element.
  4. 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

  1. What is the difference between vector, deque and list? 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.
  2. Why can't you use std::sort on a std::list? std::sort needs random-access iterators (it subtracts and jumps); list iterators are bidirectional (one step forward or back). Use list::sort().
  3. What is iterator invalidation? Give an example. An iterator that no longer points at a valid element after the container changes. vector::push_back that grows the capacity invalidates all iterators; list::insert invalidates none; list::erase invalidates only the erased one.
  4. 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.
  5. What does splice do, 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.
  6. Does pop_front() return the removed element? No, it returns void. Read front() first, then pop_front().
  7. 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 vector shifts every element: O(n) each, seconds for 200000 items.
  • deque is open at both ends: push_front, pop_front, push_back, pop_back in O(1), and d[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::list is a doubly linked list: insert(it, x) (before it) and erase(it) in O(1) through an iterator, and other iterators stay valid.
  • A list has no []; next(it, n) walks. std::sort doesn't work on it; use list.sort(). splice relinks whole lists without copying; remove erases by value.
  • Default to vector; use deque for both ends and list for 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.