Four containers hold elements in the order you put them. They are not interchangeable, and the differences are large enough to measure.

What each one is

std::vector — one contiguous heap block, plus a size and a capacity. Grows by doubling (lesson 11.6). This is IntVector from Module 11, made generic in lesson 12.3.

std::deque — a double-ended queue. Several fixed-size blocks, plus an index of pointers to them. Adding at either end allocates a new block; nothing is moved.

std::list — a doubly linked list. Each element is a separate heap node with prev and next pointers.

std::array — a fixed-size array with a container interface. No heap involvement at all; the elements live inside the object (lesson 12.5).

What that costs, measured

#include <array>
#include <chrono>
#include <deque>
#include <iostream>
#include <list>
#include <vector>

template <typename F>
long long time_us(F f) {
    auto t0 = std::chrono::steady_clock::now();
    f();
    auto t1 = std::chrono::steady_clock::now();
    return std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
}

int main() {
    const int N = 100000;

    std::cout << "push_front " << N << " elements:\n";
    std::cout << "  vector (insert at begin): "
              << time_us([&]{ std::vector<int> v; for (int i=0;i<N;++i) v.insert(v.begin(), i); })
              << " us\n";
    std::cout << "  deque:                    "
              << time_us([&]{ std::deque<int> d; for (int i=0;i<N;++i) d.push_front(i); })
              << " us\n";
    std::cout << "  list:                     "
              << time_us([&]{ std::list<int> l; for (int i=0;i<N;++i) l.push_front(i); })
              << " us\n";

    std::vector<int> v(N, 1);
    std::list<int> l(N, 1);
    std::cout << "\nsum by traversal (cache behaviour):\n";
    long long s = 0;
    std::cout << "  vector: " << time_us([&]{ for (int x : v) s += x; }) << " us\n";
    std::cout << "  list:   " << time_us([&]{ for (int x : l) s += x; }) << " us\n";
    std::cout << "  (checksum " << s << ")\n";

    std::cout << "\nsizeof:\n";
    std::cout << "  std::array<int,100>: " << sizeof(std::array<int,100>) << "\n";
    std::cout << "  std::vector<int>:    " << sizeof(std::vector<int>) << "\n";
    std::cout << "  std::deque<int>:     " << sizeof(std::deque<int>) << "\n";
    std::cout << "  std::list<int>:      " << sizeof(std::list<int>) << "\n";
    return 0;
}

A representative run, compiled -O2. Timings vary between runs and machines; the ratios are the point:

push_front 100000 elements:
  vector (insert at begin): 325929 us
  deque:                    412 us
  list:                     5268 us

sum by traversal (cache behaviour):
  vector: 31 us
  list:   231 us
  (checksum 200000)

sizeof:
  std::array<int,100>: 400
  std::vector<int>:    24
  std::deque<int>:     80
  std::list<int>:      24

Three results worth reading carefully.

Inserting at the front of a vector took 326 milliseconds — roughly 790 times slower than the deque. Each insert(begin(), x) shifts every existing element up one position, so 100,000 inserts move about 5 billion elements in total. This is O(n²) hiding behind a one-line call.

The list is 13× slower than the deque at the thing lists are supposedly for. Both are O(1) per push, but the list allocates a separate heap node for every single element, and new is not free. The deque allocates one block per few hundred elements.

Traversal: the vector is over 7× faster than the list, and both are O(n) with the same number of additions. The difference is entirely memory layout — the vector's elements are adjacent, so each cache line the CPU fetches brings in 16 useful ints; the list's are scattered, so most fetches bring in one useful int and 60 bytes of something else. Module 22 measures this properly, but the effect is visible already.

sizeof(std::vector<int>) is 24 regardless of contents — three pointers, or a pointer and two sizes. std::array<int, 100> is 400 bytes, because it is the elements.

The table

| | array | vector | deque | list | |---|---|---|---|---| | Storage | in the object | one heap block | blocks + index | separate nodes | | Size fixed at | compile time | — | — | — | | Index [i] | O(1) | O(1) | O(1), slower | no | | Insert/erase at back | — | O(1) amortised | O(1) | O(1) | | Insert/erase at front | — | O(n) | O(1) | O(1) | | Insert/erase in middle | — | O(n) | O(n) | O(1) given an iterator | | Iterator category | random access | random access | random access | bidirectional | | Iterators survive insert | — | no | no (all) | yes | | References survive insert | — | no | yes | yes | | Cache friendly | yes | yes | mostly | no |

The row people misread is insert in the middle. std::list inserts in O(1) once you already hold an iterator to the position. Finding that position is O(n), and finding it is usually the expensive part. A list only wins when you obtained the iterator some other way and are keeping it.

Choosing

Use std::vector. It is the right answer for the large majority of cases, and the standard's own guidance says so. Contiguous storage, the best cache behaviour, and the lowest per-element overhead.

Use std::array when the size is a compile-time constant. A 3D point, a fixed lookup table, a 256-entry byte histogram. No allocation at all.

Use std::deque when you push and pop at both ends — a queue, a sliding window, an undo buffer. It is also the default backing store for std::stack and std::queue (lesson 13.6).

Use std::list when you need stable iterators across insertion and removal, or you splice whole sublists between containers in O(1). Both are real needs, and both are rare. If you are reaching for a list because "insertion is O(1)", measure first — the numbers above are typical.

The vector operations worth knowing

// v.reserve(n)          allocate for n now, avoiding reallocation later
// v.shrink_to_fit()     release unused capacity (a request, not a guarantee)
// v.data()              pointer to the contiguous block — for C APIs
// v.emplace_back(args)  construct in place rather than construct-and-move
// v.clear()             size 0, capacity unchanged (lesson 11.6)
// v.assign(n, value)    replace the contents

reserve is the one with the biggest practical effect. Lesson 11.6 measured 11 reallocations against 1 for 1000 push_backs — and every reallocation copies or moves everything already stored.

The erase-remove idiom

std::remove does not remove anything, which surprises everyone exactly once:

// std::remove shuffles the elements you want to keep to the front and
// returns an iterator to the new logical end. The container's size is
// unchanged — an algorithm has iterators, not the container.
//
//   auto new_end = std::remove(v.begin(), v.end(), 3);
//   v.erase(new_end, v.end());          // the container does the removing
//
// Or in one line:
//   v.erase(std::remove(v.begin(), v.end(), 3), v.end());
//
// Since C++20, simply:
//   std::erase(v, 3);
//   std::erase_if(v, [](int x) { return x % 2 == 0; });

The reason for the split is the whole point of lesson 13.1: an algorithm sees a range, not a container, so it cannot change a container's size. std::erase in C++20 finally provides the container-aware version, and you should use it.

Try it

Checkpoint

• vector is one contiguous block; deque is blocks plus an index; list is separate nodes; array is the elements themselves.
• Default to std::vector — contiguity beats asymptotics at realistic sizes.
• insert(begin(), x) on a vector is O(n); doing it 100,000 times measured 326 ms.
• Traversing a list measured 7× slower than a vector of the same size, from cache behaviour alone.
• std::list's O(1) insert requires an iterator you already hold; finding it is O(n).
• Choose list for stable iterators or O(1) splicing, not for insertion speed.
• Choose deque for push and pop at both ends; it backs stack and queue.
• Choose array when the size is a compile-time constant and you want no allocation.
• reserve avoids repeated reallocation; clear keeps capacity.
• std::remove does not remove — use C++20's std::erase and std::erase_if.