# Sequence containers

> vector, deque, list, forward_list and array differ in one thing, where they put their elements, and every complexity bound, invalidation rule and exception guarantee follows from that layout. Learn the layouts and the rest can be derived.

- **Source:** C++ Atlas (https://cppatlas.com/topics/sequence-containers)
- **Track:** Containers and strings
- **Estimated reading time:** 12 minutes
- **ISO C++ clauses:** [sequence.reqmts] (https://eel.is/c++draft/sequence.reqmts), [vector.capacity] (https://eel.is/c++draft/vector.capacity), [vector.modifiers] (https://eel.is/c++draft/vector.modifiers), [deque.modifiers] (https://eel.is/c++draft/deque.modifiers), [list.ops] (https://eel.is/c++draft/list.ops), [forward.list] (https://eel.is/c++draft/forward.list), [vector.erasure] (https://eel.is/c++draft/vector.erasure)
- **cppreference links:** [std::vector](https://en.cppreference.com/w/cpp/container/vector), [std::deque](https://en.cppreference.com/w/cpp/container/deque), [std::list](https://en.cppreference.com/w/cpp/container/list), [std::forward_list](https://en.cppreference.com/w/cpp/container/forward_list), [std::array](https://en.cppreference.com/w/cpp/container/array), [std::vector::reserve](https://en.cppreference.com/w/cpp/container/vector/reserve), [std::list::splice](https://en.cppreference.com/w/cpp/container/list/splice)
- **Prerequisites:** copy-and-move, noexcept

## The one idea

A sequence container keeps its elements in an order you control, and the only real design choice is where the elements live. A `vector` keeps them in one contiguous block. A `deque` keeps them in several fixed-size blocks reached through an index. A `list` and a `forward_list` give every element its own node. A `std::array` keeps them inside the object itself.

Once you know the layout you can predict almost everything the standard promises: how long an operation takes, whether pointers to elements survive it, and what happens when an element's move constructor throws.

> **Mental model.** Ask two questions of any operation. Does it need to shift or reallocate elements? If so, it costs linear time and breaks references. Does it only relink or construct one element at an end? If so, it is cheap and the rest of the container is left alone.

```text
vector      [e0 e1 e2 e3 .. spare ..]        one block, capacity >= size
deque       map -> [e0 e1 e2] [e3 e4 e5] ... blocks, index of blocks
list        e0 <-> e1 <-> e2 <-> e3          node per element, two links
forward_list e0 -> e1 -> e2 -> e3            node per element, one link
array<T,N>  [e0 e1 e2]                       inside the object, no heap
```

The block structure of `deque` is an implementation technique rather than a requirement, but the guarantees the standard states can only be met by something like it.

## What each container guarantees

| Container | Element access | Insert or erase at end | At front | In the middle |
| --- | --- | --- | --- | --- |
| `vector` | random, contiguous | amortized constant | linear | linear |
| `deque` | random, not contiguous | constant | constant | linear |
| `list` | none by index | constant | constant | constant, given an iterator |
| `forward_list` | none by index | linear to find the end | constant | constant after an iterator |

`vector` and `array` are the contiguous ones: `&v[0]` plus an offset reaches every element, so `v.data()` can be handed to a C interface. `deque` is random access but not contiguous, so it has no `data()`. `list` and `forward_list` have only bidirectional and forward iterators.

`forward_list` has no `size()` at all. The standard leaves it out so the container costs no more than a hand-written singly linked list. It also has no `push_back` and no `insert`, only `insert_after` and `erase_after`, because a node cannot reach its predecessor.

## Growth, `reserve` and `shrink_to_fit`

`vector::push_back` is amortized constant time because capacity grows geometrically. The standard does not say what the factor is, only that `capacity()` is at least `size()` and that reallocation happens only when a larger size would exceed the capacity. Do not assume doubling.

`reserve(n)` raises capacity to at least `n`, and after it, insertions will not reallocate until the size would exceed `capacity()`. That is a guarantee you can build on: iterators and references stay valid across those insertions. It does not create elements.

```cpp
#include <vector>

void demo() {
  std::vector<int> v;
  v.reserve(100);
  // v.size() == 0 and v.capacity() >= 100, but v[0] is undefined behavior.
  v.push_back(1);          // no reallocation, whatever the growth policy is
  v.resize(10);            // this is what creates elements
  v.shrink_to_fit();       // a request: capacity() may stay larger
}
```

`shrink_to_fit` is explicitly a non-binding request. An implementation may ignore it, and if it does reallocate, everything is invalidated. If you must release the storage, destroy the vector or swap it with an empty one.

A `deque` has no `capacity`, `reserve` or `data`. `list` and `forward_list` have none of these either: there is nothing to reserve when every element is its own allocation.

## Reallocation and `noexcept` moves

When a `vector` runs out of room it allocates a new block and relocates the old elements. It must keep the strong exception guarantee for `push_back`: if something throws, the vector is as it was before. Moving elements out of the old block would break that, because a throwing move leaves some elements already stolen.

So the implementation uses `std::move_if_noexcept`. If the move constructor is `noexcept`, or the type cannot be copied, elements are moved. Otherwise they are copied, and the originals stay safe until the copy finishes.

```cpp
#include <cstdio>
#include <vector>

struct Slow {
  Slow() = default;
  Slow(const Slow&) { std::puts("copy"); }
  Slow(Slow&&) { std::puts("move"); }   // forgot noexcept: growth copies
};

struct Fast {
  Fast() = default;
  Fast(const Fast&) { std::puts("copy"); }
  Fast(Fast&&) noexcept { std::puts("move"); }  // growth moves
};
```

This is why a missing `noexcept` on a move constructor is a performance bug that no test fails on. The rule is covered in depth in the topic on `noexcept`. The standard requires the strong guarantee for a single `push_back` of a copyable type, and the mainstream implementations meet it with `move_if_noexcept`.

> **Pitfall.** A move-only type whose move constructor can throw is moved anyway, because there is no copy to fall back on. If that move throws during growth, the standard says the effects are unspecified.

## `emplace_back` versus `push_back`

`push_back(x)` takes an already-built element, copies or moves it into the new slot. `emplace_back(args...)` forwards its arguments to a constructor and builds the element in place. The saved temporary rarely matters for cheap types, but two differences are about correctness.

First, `emplace_back` can call an `explicit` constructor, where `push_back(3)` cannot convert an `int` into an explicit-constructible `P` and is rejected. That cuts both ways: `emplace_back` also makes it easy to construct something you did not mean to. Second, `emplace_back` returns a reference to the new element since C++17, so you can use the new element straight away.

```cpp
#include <string>
#include <vector>

struct P {
  explicit P(int);
};

void f(std::vector<P>& v, std::vector<std::string>& s) {
  v.emplace_back(1);        // OK: explicit constructor, called directly
  // v.push_back(1);        // ill-formed: needs an implicit conversion
  s.push_back("abc");       // builds a std::string temporary, then moves it
  s.emplace_back("abc");    // builds the std::string directly in the slot
}
```

The argument may even alias an element: `v.push_back(v[0])` is required to work, even when it reallocates, so implementations construct the new element before destroying the old block.

## `deque` and `list`: what stays put

`deque` keeps its element blocks where they are when you add at either end. The index of blocks may be rebuilt, so every iterator is invalidated, but no element moves, so references and pointers survive. Inserting or erasing in the middle shifts elements and invalidates everything.

```cpp
#include <deque>

void demo() {
  std::deque<int> d{1, 2, 3};
  int& r = d[1];
  d.push_front(0);
  d.push_back(4);
  r = 99;                   // OK: references survive end insertions
  // an iterator taken before the pushes would be invalid here
}
```

The full table of rules lives in the topic on iterator invalidation. A `list` is the extreme case: no element ever moves, so only iterators to the erased elements die. That also makes `splice` possible. `a.splice(pos, b, it)` relinks one node from `b` into `a` in constant time. No element is copied or destroyed, so references stay valid and iterators keep referring to the same elements, now as iterators into `a`.

```cpp
#include <list>

void demo() {
  std::list<int> a{1, 2, 3}, b{4, 5};
  auto it = a.begin();
  b.splice(b.end(), a, it);   // constant time; *it is still 1, now inside b
  b.splice(b.end(), a);       // moves everything left in a: also constant
}
```

Splicing a range `[first, last)` from a different list is linear in the length of the range, because the destination's `size()` must be updated and `list::size()` is constant time. Same list, constant.

`forward_list` has the matching operations with `_after` names: `splice_after`, `insert_after`, `erase_after`, and `before_begin()` to get a position before the first element. `merge`, `sort`, `reverse`, `remove` and `unique` are member functions on both list types, because the generic algorithms need random access or cannot relink nodes.

## Erasing and the C++20 and C++23 additions

Removing elements by value or predicate used to mean the erase-remove idiom: `v.erase(std::remove_if(...), v.end())`. C++20 added non-member `std::erase(c, value)` and `std::erase_if(c, pred)` for `vector`, `deque`, `list` and `forward_list`, and `erase_if` for the associative containers too. They return the number of removed elements. For `list` and `forward_list` they call the member `remove_if`, which relinks nodes; for `vector` and `deque` they do the erase-remove idiom.

```cpp
#include <vector>

void demo() {
  std::vector<int> v{1, 2, 3, 4, 5, 6};
  auto n = std::erase_if(v, [](int x) { return x % 2 == 0; });
  // n == 3, v == {1, 3, 5}
  (void)n;
}
```

C++23 added range-aware members. `insert_range(pos, rg)` inserts a whole range and returns an iterator to the first inserted element. `append_range(rg)` adds at the end and returns `void`. `assign_range` replaces the contents. `forward_list` has `insert_range_after` and `prepend_range` instead. They avoid the temporary container and let `vector` allocate once when the range's size is known. The inserted range must not overlap the container itself.

## Choosing

Start with `vector`; it wins more often than its complexity table suggests, because contiguous memory is friendly to caches and prefetchers. A `list` earns its place only when you need stable iterators and references through arbitrary insertion and removal, or constant-time `splice`. Reach for `deque` when you need both-end insertion with reference stability, a queue that grows at the back and shrinks from the front, or very large containers where reallocating one huge block hurts. Use `forward_list` only when per-element overhead of one pointer matters. Use `std::array` when the size is a compile-time constant; its details belong to the topic on `array`, `bitset` and `vector<bool>`.

> **Standardese.** [list.ops] says that after a splice, pointers and references to the moved elements refer to the same elements as members of the destination, and iterators keep referring to their elements but behave as iterators into the destination. [vector.capacity] says no reallocation takes place after `reserve` until an insertion would make the size exceed the capacity, and describes `shrink_to_fit` as a non-binding request.

## What to remember

- Layout decides everything: contiguous block, block index, one node per element, or inline storage.
- `vector` growth is amortized constant, with an unspecified factor; `reserve` creates capacity, not elements.
- `shrink_to_fit` and `reserve` beyond capacity can reallocate; only `reserve` gives a guarantee about later insertions.
- Growth moves elements only when their move is `noexcept` or they cannot be copied; otherwise it copies. Mark moves `noexcept`.
- `emplace_back` constructs in place and can call explicit constructors; `push_back` takes a finished element.
- `deque` end insertions invalidate iterators but not references; middle insertions invalidate both.
- `list::splice` moves nodes without touching elements, so iterators stay valid and now belong to the destination.
- `forward_list` has no `size()`, and its operations act after a position.
- C++20 `erase` and `erase_if` replace the erase-remove idiom; C++23 `insert_range` and `append_range` take whole ranges.
- Default to `vector`, and change only for a stated reason.

## Concept Map Outline

- **Sequence containers:** Five containers that differ in where elements live; guarantees follow from layout.
  - **Layouts:** Storage shape decides complexity, invalidation and exception behavior.
    - **vector:** One contiguous block with spare capacity; data() works.
    - **deque:** Fixed-size blocks behind an index; random access but not contiguous.
    - **list and forward_list:** One node per element; forward_list has no size() and only _after operations.
    - **array:** Elements live inside the object; fixed size, no allocation.
  - **Growth and capacity:** Only vector has capacity; the growth factor is unspecified.
    - **push_back amortized O(1):** Capacity grows geometrically, so appending is amortized constant time.
    - **reserve:** Raises capacity without creating elements; later insertions do not reallocate until capacity is exceeded.
    - **shrink_to_fit:** A non-binding request to drop spare capacity; the implementation may ignore it.
  - **Relocation on growth:** Growth must keep the strong guarantee for copyable types.
    - **move_if_noexcept:** Elements are moved only if their move is noexcept or they cannot be copied.
    - **Mark moves noexcept:** A missing noexcept silently turns reallocation into copying.
  - **Inserting elements:** Construction in place versus passing a finished object.
    - **emplace_back:** Forwards arguments to a constructor, including explicit ones, and returns a reference since C++17.
    - **push_back:** Copies or moves an existing element; cannot use an explicit conversion.
    - **insert_range, append_range:** C++23 range members; insert_range returns an iterator, append_range returns void.
  - **What stays put:** Which references and iterators survive common operations.
    - **deque end insertion:** Invalidates iterators but not references or pointers to existing elements.
    - **list::splice:** Relinks nodes in constant time; iterators stay valid and now belong to the destination.
  - **Erasing and choosing:** Removal helpers and a default pick.
    - **erase and erase_if:** C++20 non-member functions replace the erase-remove idiom and return the removed count.
    - **Default to vector:** Contiguous memory is cache friendly; switch only for a stated need such as stability or splice.

## Standardese Quiz Questions

### Question 1 [warmup] ([vector.erasure], [alg.remove])

In C++23, what does this program print?

```cpp
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{1, 2, 3, 4, 5, 6};
  auto n = std::erase_if(v, [](int x) { return x % 2 == 0; });
  std::cout << n << ' ' << v.size() << '\n';
}
```

A. 3 3
B. 3 6
C. 6 3
D. Undefined behavior

**Answer (A):** 3 3

**Why:** Since C++20, `std::erase_if` on a `vector` performs the erase-remove idiom for you and returns the number of elements it removed. Three even numbers go, so `n` is 3 and the size drops from 6 to 3. The tempting `3 6` imagines `std::remove_if` alone, which shuffles elements but leaves the size unchanged.

### Question 2 [warmup] ([vector.modifiers], [class.conv.ctor])

Which of the three calls is ill-formed?

```cpp
#include <vector>

struct P {
  explicit P(int);
};

void f(std::vector<P>& v) {
  v.emplace_back(1);  // (1)
  v.push_back(P(2));  // (2)
  v.push_back(3);     // (3)
}
```

A. None of them
B. Only (2)
C. Only (3)
D. (2) and (3)

**Answer (C):** Only (3)

**Why:** `emplace_back` forwards its arguments to a constructor call, so an explicit constructor is fine. `push_back(P(2))` passes an actual `P`. `push_back(3)` needs an implicit conversion from `int` to `P` to bind the `value_type` parameter, and an explicit constructor forbids that, so only (3) is rejected.

### Question 3 [warmup] ([vector.capacity], [sequence.reqmts])

What is the behavior of this program?

```cpp
#include <vector>

int main() {
  std::vector<int> v;
  v.reserve(10);
  v[0] = 1;
}
```

A. Well-formed; `v` now holds one element
B. Undefined behavior
C. Throws `std::out_of_range`
D. Well-formed; element 0 is written but `size()` stays 0

**Answer (B):** Undefined behavior

**Why:** `reserve` only allocates capacity; it creates no elements and leaves `size()` at 0. `operator[]` does no bounds check, and indexing at or past `size()` is undefined behavior, even though the storage exists. `at` would throw `std::out_of_range`, which is the tempting but wrong description of `operator[]`.

### Question 4 [tricky] ([deque.modifiers])

What does this program print?

```cpp
#include <deque>
#include <iostream>

int main() {
  std::deque<int> d{1, 2, 3};
  int& r = d[1];
  for (int i = 0; i < 1000; ++i) {
    d.push_back(i);
    d.push_front(-i);
  }
  r = 99;
  std::cout << d[1001] << '\n';
}
```

A. 2
B. Undefined behavior: the reference was invalidated
C. 99
D. Implementation-defined

**Answer (C):** 99

**Why:** Insertion at either end of a `deque` invalidates iterators but never references or pointers to existing elements. The original element 2 sits at index 1001 after 1000 `push_front` calls, and `r` still names it, so the write is well-defined and the program prints 99. The same program using an iterator instead of `r` would be undefined behavior, which is what makes the first option tempting.

### Question 5 [tricky] ([list.ops])

What does this program print?

```cpp
#include <iostream>
#include <iterator>
#include <list>

int main() {
  std::list<int> a{1, 2, 3}, b{4, 5};
  auto it = a.begin();
  b.splice(b.end(), a, it);
  std::cout << *it << ' ' << std::boolalpha
            << (std::next(it) == b.end()) << ' ' << a.size() << '\n';
}
```

A. Undefined behavior: `it` is invalidated by the splice
B. 1 true 2
C. 1 false 2
D. 4 true 2

**Answer (B):** 1 true 2

**Why:** `splice` relinks nodes without copying or destroying anything. Iterators to the moved element stay valid, keep referring to the same element, and now behave as iterators into `b`. The element 1 is the new last element of `b`, so `std::next(it)` equals `b.end()`, and `a` is left with two elements. The third option imagines `it` still belonging to `a`.

### Question 6 [tricky] ([vector.modifiers])

With libstdc++ or libc++, what does this program print after `grow`? (The standard only demands the strong exception guarantee; this is what both implementations do for a copyable type.)

```cpp
#include <cstdio>
#include <vector>

struct S {
  S() = default;
  S(const S&) { std::puts("copy"); }
  S(S&&) { std::puts("move"); }  // not noexcept
};

int main() {
  std::vector<S> v;
  v.reserve(4);
  while (v.size() < v.capacity()) v.emplace_back();
  std::puts("grow");
  v.emplace_back();
}
```

A. One `move` line for each old element
B. One `copy` line for each old element
C. Nothing; growth never touches the old elements
D. One `move` line, then the old elements are copied

**Answer (B):** One `copy` line for each old element

**Why:** To keep the strong guarantee, `vector` relocates with `std::move_if_noexcept`: elements are moved only if the move constructor is `noexcept` or the type cannot be copied. Here the move constructor may throw and a copy constructor exists, so every old element is copied, and the originals stay intact if a copy throws. Marking the move constructor `noexcept` would flip the output to `move`.

### Question 7 [standardese] ([forward.list], [container.reqmts])

Is this program well-formed in C++23?

```cpp
#include <forward_list>

int main() {
  std::forward_list<int> f{1, 2, 3};
  return static_cast<int>(f.size());
}
```

A. Well-formed; `size()` is linear time
B. Well-formed; `size()` is constant time
C. Ill-formed: `forward_list` has no `size()` member
D. Unspecified

**Answer (C):** Ill-formed: `forward_list` has no `size()` member

**Why:** `forward_list` is specified as a container that omits `size()`, so that it can keep the same space overhead as a hand-written singly linked list. Use `std::distance(f.begin(), f.end())` and accept the linear cost. `list`, by contrast, has a constant-time `size()` since C++11.

### Question 8 [standardese] ([vector.modifiers], [sequence.reqmts])

In C++23, what does this program print?

```cpp
#include <array>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{1, 2};
  std::array<int, 2> a{8, 9};
  auto it = v.insert_range(v.begin(), a);
  std::cout << *it << ' ';
  v.append_range(a);
  std::cout << v.size() << '\n';
}
```

A. 1 6
B. Ill-formed: `insert_range` returns `void`
C. 9 6
D. 8 6

**Answer (D):** 8 6

**Why:** C++23 added range-aware members. `insert_range` returns an iterator to the first inserted element (the 8), and `append_range` returns `void`. The vector goes from 2 to 4 to 6 elements. Dereferencing `it` before the append matters, because a reallocation in `append_range` would invalidate it.
