Chapter 36 of 48

list, deque & array

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 of N elements of type T. The size N must 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? false

Notice three things:

  • marks[3] does no bounds checking. Accessing marks[5] would be undefined behavior, exactly like a C array.

  • marks.at(5) checks the index and throws std::out_of_range (from <stdexcept>). We covered try/catch in the Exception Handling chapter.

  • copy = marks copies 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> and std::array<int, 5> are different types. A function taking std::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 use std::vector.)

  • std::to_array (C++20) deduces the size for you. Since C++17 you can also write std::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 as int are left uninitialised (in a local variable), and reading them is undefined behavior.

  • sizeof(a) equals the size of the raw array: std::array stores 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 no it + 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 = 3

Key points from this program:

  • push_front and push_back are both O(1).

  • insert(it, value) inserts before it and returns an iterator to the new element.

  • After the insert, it still 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 write it = l.erase(it); – erase returns an iterator to the element after the erased one.

  • We had to write ++it; ++it; because l.begin() + 2 does 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

remove(v) / remove_if(pred)

Erases every matching element

O(n)

sort()

Sorts the list (stable)

O(n log n)

unique()

Removes consecutive duplicates only, so sort first

O(n)

merge(other)

Merges two sorted lists; other becomes empty

O(n + m)

splice(pos, other)

Moves all nodes of other before pos, without copying

O(1)

reverse()

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:

  1. 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).

  2. Memory overhead: each int in 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                   back
  • push_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 (and emplace_*): 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 (for pop_back, also end()).

  • insert / erase in the middle: everything is invalidated.


Complexity Comparison

Operation

array

vector

deque

list

Access by index [i]

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

  1. Using std::sort on a list. It does not compile; call l.sort() instead.

  2. Writing l.begin() + 3 on a list. List iterators are bidirectional, not random access. Use std::next(l.begin(), 3) and remember it costs O(n).

  3. Calling unique() on an unsorted list and expecting all duplicates to disappear. It only removes duplicates that are next to each other.

  4. Using an iterator after erase. l.erase(it); ++it; is undefined behavior because it now refers to a destroyed node. Write it = l.erase(it);.

  5. Keeping a deque iterator across push_front/push_back. References survive, iterators do not.

  6. Forgetting {} on std::array of built-in types. std::array<int, 3> a; inside a function holds garbage.

  7. 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 and at().

  • std::list is 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 like sort, splice, merge and unique.

  • std::deque gives O(1) push/pop at both ends plus random access, using blocks of elements; its memory is not contiguous.

  • For most problems, vector is 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.