vector vs list vs deque: Why Cache Locality Usually Beats Big-O

Introduction: “vector, list, deque… Which Should I Use?”

C++ STL provides three main sequence containers: vector, list, and deque. Each has different time complexity and memory layout, so choosing appropriately for the situation is important.

The textbook answer comes from a complexity table: list inserts in the middle in O(1), vector in O(n), so a workload with many middle insertions should use list. On modern hardware that answer is often wrong, and understanding why is more useful than memorizing the table. Memory is fetched in 64-byte cache lines, and the CPU prefetches the next lines when it sees a sequential pattern. Shifting a few thousand ints in a vector is a memmove over memory that is already in cache. Walking a list to the insertion point is a chain of dependent loads, each of which may miss the cache, because the next address is not known until the current node has been read.

When to use vector, when list·deque?

Aspect	vector	list	deque
Performance	Sequential access·cache excellent	Middle insertion theoretically O(1) but high constant·allocation cost	Both ends insertion·deletion O(1)
Usability	[], reserve etc intuitive	Node-based iterator invalidation rules need attention	Index access more restricted than vector
Application Scenario	Default choice	When insertion position is truly random and frequent	Sliding window·double-ended queue

Common misconceptions:

• “Always use list for frequent middle insertions” → Wrong (need to consider cache efficiency)
• “vector is slow because it’s an array” → Wrong (fastest in most cases)
• “deque is only fast for both-end insertion” → Partially correct (middle access also O(1))

This guide looks at the internal structure of each container, compares their time complexity for insertion, deletion and lookup, walks through four benchmark scenarios and what drives the result in each, and ends with a selection guide by situation.

---

Container Internal Structure

vector: Contiguous Memory Array

[1][2][3][4][5][6][7][8]...
 ↑                       ↑
begin                   end

Characteristics:
- Contiguous memory block
- Highest cache efficiency
- Entire copy on reallocation

std::vector<int> vec = {1, 2, 3, 4, 5};

// Memory layout
// [1][2][3][4][5][capacity spare space...]

A vector object is three pointers (begin, end, end of capacity) and one heap buffer. When push_back exceeds the capacity, it allocates a larger buffer (libstdc++ and libc++ double it, MSVC grows by 1.5×), moves or copies every element, and frees the old buffer. That is the source of both its main cost and its main hazard: every pointer, reference and iterator into the old buffer is now dangling. If the element type’s move constructor is not noexcept, the vector copies instead of moving during reallocation to keep the strong exception guarantee, which can make growth much slower for types like classes with a user-written move constructor that forgot noexcept.

list: Doubly Linked List

[1] ⇄ [2] ⇄ [3] ⇄ [4] ⇄ [5]
 ↑                       ↑
begin                   end

Characteristics:
- Nodes scattered in memory
- Each node has prev/next pointers
- No reallocation

std::list<int> lst = {1, 2, 3, 4, 5};

// Memory layout (conceptual)
// Node1: [prev=null][data=1][next=Node2]
// Node2: [prev=Node1][data=2][next=Node3]
// ...

On a 64-bit platform each node carries two 8-byte pointers besides the value, and the allocator adds its own bookkeeping and alignment to each allocation. For std::list<int> that means a 4-byte payload inside an allocation of roughly 24 to 32 bytes, so the same data takes several times the memory of a vector and fills correspondingly more cache lines. The upside of the node structure is real, though: inserting or erasing never moves other elements, so iterators and pointers to them stay valid, and splice can move a range of nodes from one list to another in O(1) without allocating or copying anything.

deque: Chunk Array

Chunk1: [1][2][3][4]
Chunk2: [5][6][7][8]
Chunk3: [9][10][11][12]
       ↑
      map (chunk pointer array)

Characteristics:
- Multiple fixed-size chunks
- Both-end insertion O(1)
- Middle access O(1) (slightly slower)

A deque keeps a “map”, an array of pointers to fixed-size blocks. Indexing computes which block and which offset, so d[i] is O(1) but costs two dependent loads instead of one. Pushing at either end fills the current end block and allocates a new block only when it is full, which is why neither end requires moving existing elements and why references to existing elements survive push_front and push_back (iterators do not, because the map may be reallocated).

The block size is an implementation detail with a large effect. libstdc++ uses blocks of 512 bytes, so a deque<int> holds 128 elements per block. MSVC’s implementation uses much smaller blocks (16 bytes, or a single element for types larger than 8 bytes), so a deque of medium-sized structs on MSVC behaves almost like one allocation per element. If you choose deque for performance, measure on every platform you ship.

---

Time Complexity Comparison

Time Complexity by Operation

Operation	vector	list	deque
Front insertion	O(n)	O(1)	O(1)
Back insertion	O(1) amortized	O(1)	O(1)
Middle insertion	O(n)	O(1)	O(n)
Front deletion	O(n)	O(1)	O(1)
Back deletion	O(1)	O(1)	O(1)
Middle deletion	O(n)	O(1)	O(n)
Index access	O(1)	O(n)	O(1)
Sequential traversal	Fast	Slow	Medium
Memory efficiency	High	Low	Medium

Note: Time Complexity ≠ Actual Performance

Cache efficiency greatly affects actual performance.

// list: O(1) insertion
std::list<int> lst;
for (int i = 0; i < 1000000; ++i) {
    lst.push_back(i);  // O(1), but many cache misses
}

// vector: O(1) amortized insertion
std::vector<int> vec;
vec.reserve(1000000);
for (int i = 0; i < 1000000; ++i) {
    vec.push_back(i);  // O(1), high cache efficiency
}

// Both loops are O(n) overall, yet the vector loop is typically many times
// faster: one allocation instead of a million, and sequential writes.

Both loops do the same asymptotic work. The list loop calls the allocator a million times and writes each node to wherever the allocator put it; the vector loop, after one reserve, writes a million integers into consecutive memory. The complexity table cannot show this difference because it counts operations, not allocations and cache misses. That is the gap every benchmark below is really measuring.

---

Benchmark Scenarios

The snippets below are benchmark skeletons. Absolute times vary a lot with CPU, allocator, compiler and flags, so this section describes what dominates the cost in each scenario and which container usually wins; run the code on your own machine with optimization enabled (-O2/-O3) to get real numbers.

Test 1: Back Insertion (push_back)

// Benchmark code
template <typename Container>
void benchPushBack() {
    Container c;
    for (int i = 0; i < 1000000; ++i) {
        c.push_back(i);
    }
}

What to expect:

Container	What dominates the cost
vector	Amortized O(1); an occasional reallocation moves every element
vector (reserve)	No reallocation at all, usually the fastest
list	One heap allocation per element, typically by far the slowest
deque	Allocates fixed-size blocks, usually between vector and list

Analysis: vector wins because writes are contiguous and allocations are rare.

Test 2: Front Insertion (push_front)

template <typename Container>
void benchPushFront() {
    Container c;
    for (int i = 0; i < 100000; ++i) {  // 100k (1M too slow)
        c.push_front(i);
    }
}

What to expect:

Container	What dominates the cost
vector	No push_front; insert(begin()) shifts every element, so the loop is O(n²) and very slow
list	O(1) per insert, plus one allocation each
deque	O(1) per insert into a block, few allocations

Analysis: For front insertion, deque is the natural choice.

Test 3: Middle Insertion

template <typename Container>
void benchMiddleInsert() {
    Container c;
    
    // Initial data
    for (int i = 0; i < 10000; ++i) {
        c.push_back(i);
    }
    
    // Insert 1000 times in middle
    auto it = c.begin();
    std::advance(it, 5000);  // Middle position
    
    for (int i = 0; i < 1000; ++i) {
        it = c.insert(it, 999);  // insert invalidates it for vector/deque
    }
}

What to expect:

Container	What dominates the cost
vector	Each insert shifts about half the elements (a fast memmove for int)
list	O(1) per insert once you hold the iterator, but reaching the position is O(n)
deque	Shifts elements toward the nearer end, often slower than vector

For vector and deque, insert invalidates it, which is why the loop reassigns it from the return value. Writing c.insert(it, 999) without the assignment is undefined behavior for those two containers; with a vector it often appears to work until an insertion triggers reallocation, and then the next insert writes through a dangling iterator. With a list the old iterator stays valid, which is exactly the property that makes list code easy to port incorrectly to vector.

Analysis: For middle insertion, list can win when you already hold the iterator and the container is large, but vector stays competitive for small and medium sizes because shifting contiguous memory is cheap. The benchmark above is also generous to list: it walks to the middle once and then inserts repeatedly at the same spot. In real code the position usually comes from a search (the first element greater than X, say), and that search is a full O(n) pointer walk for list, while vector can find it with std::lower_bound in O(log n) if the data is sorted.

The element type changes the result too. Shifting ints is cheap; shifting elements that are large and expensive to move is not. If each element is a 200-byte struct without a cheap move, a vector insertion in the middle copies a lot of bytes, and list or a vector of std::unique_ptr<T> (shifting 8-byte pointers) becomes competitive much sooner.

Test 4: Sequential Traversal

template <typename Container>
void benchIteration(const Container& c) {
    long long sum = 0;
    for (int x : c) {
        sum += x;
    }
}

What to expect: vector reads contiguous memory that the hardware prefetcher handles well, deque reads contiguous blocks with an extra indirection, and list follows a pointer per element that may land anywhere in the heap.

Analysis: For sequential traversal, vector is usually the clear winner, and list the clear loser.

A detail that makes list benchmarks misleading: if you build a list in one tight loop and traverse it immediately, the allocator often hands out nodes at increasing addresses, so the list is accidentally almost contiguous and traverses reasonably fast. In a long-running program, after many insertions and erasures interleaved with other allocations, nodes are scattered across the heap and traversal gets much slower. A fair benchmark shuffles the insertion order or interleaves other allocations.

Mistakes that come from the container choice

Most bugs specific to these containers are invalidation bugs. The one I see most often is code written against std::list that keeps iterators in another structure (a map from key to list iterator, for an LRU cache) and is later “optimized” by switching the list to a vector. It compiles, because the interfaces are nearly identical, and then the stored iterators silently dangle after the first reallocation or middle insertion. With a debug standard library (-D_GLIBCXX_DEBUG, or MSVC debug builds) this becomes an immediate assertion such as “attempt to dereference a singular iterator” or “vector iterator not dereferencable”; in a release build it is memory corruption.

The second is erasing inside a loop. for (auto it = v.begin(); it != v.end(); ++it) if (bad(*it)) v.erase(it); is wrong for all three containers: erase invalidates it, and the loop then increments an invalid iterator. The correct form is it = v.erase(it); without incrementing in that branch, or better, std::erase_if(v, bad) in C++20, which is O(n) for vector instead of O(n²) for repeated erase calls. std::list also has a member remove_if, which unlinks nodes without moving anything.

When order does not matter, there is also a vector idiom that makes the “frequent middle deletion” case disappear: swap the element with the last one and pop_back(). That is O(1) and keeps the data contiguous, at the cost of reordering.

---

Selection Guide by Situation

When to Use vector

Use vector when:

• Sequential access is frequent
• Random access needed
• Memory efficiency important
• Default choice

Don’t use vector when:

• Front insertion/deletion very frequent
• Both-end access needed

When to Use list

Use list when:

• Middle insertion/deletion very frequent
• Need to maintain iterators after insertion/deletion
• Don’t need random access

Don’t use list when:

• Sequential access frequent (cache inefficient)
• Memory overhead matters
• Element count is small, so shifting a vector is cheap anyway

A classic case where list is the right tool is an LRU cache: a std::list holds entries in recency order and an unordered_map maps keys to list iterators. On a hit, splice moves the node to the front in O(1) without invalidating the iterator stored in the map. With a vector, every move to the front would shift elements and invalidate the map’s stored positions.

When to Use deque

Use deque when:

• Both-end insertion/deletion frequent
• Need queue or double-ended queue
• Need sliding window

Don’t use deque when:

• Only back insertion needed (use vector)
• Memory layout must be contiguous

---

Choosing a sequence container

Need front insertion/deletion?
├─ Yes → deque
└─ No
    └─ Need iterators/pointers that survive insertion and erasure, or O(1) splice?
        ├─ Yes → list
        └─ No → vector (default)

Start with vector and move away only for a reason you can name. Its contiguous storage is what makes it fast in practice, even for middle insertions at moderate sizes, and it is the only one of the three whose data() can be handed to a C API or copied with memcpy.

When you switch to deque, know what you give up. Its elements are stored in fixed-size blocks, so it is not contiguous. Inserting at either end keeps references to existing elements valid but invalidates all iterators, which surprises code that caches iterators. list is justified mainly by its guarantees (stable iterators, splice), not by speed; if you pick it for performance, measure against vector on your own data first.

---

Frequently Asked Questions (FAQ)

Q. Can I keep pointers or iterators to elements while the container grows?

A. With vector, any insertion that exceeds the capacity reallocates, and every pointer, reference and iterator becomes invalid; reserve up front avoids that only while you stay within the capacity. deque::push_back and push_front invalidate iterators but keep pointers and references to existing elements valid. list never invalidates other elements on insertion or erasure. If other code must hold stable pointers, that stability is a real reason to choose list or deque despite vector’s better traversal speed.

---

Related Articles

• C++ std::vector Basics — Initialization, Operations &
• C++ Array vs vector
• Iterator Invalidation
• Cache-Friendly Code

---