Vector vs. List: Memory & Performance

Hello! Welcome to our next lesson on STL internals.

In the previous lesson, we dug into std::vector's memory management and its strict iterator invalidation rules. We established that its contiguous memory layout is responsible for both its greatest strength (fast, cache-friendly traversal) and its primary weakness (the potential for slow insertions/deletions due to element shifting and disruptive reallocations).

This leads to a natural question: what if your application's main job is to frequently insert and remove elements from the middle of a sequence? For that, C++ offers an alternative with a completely different internal design.

Today, we will directly address the learning outcome: Compare the memory layout and performance trade-offs of std::vector (contiguous) vs. std::list (node-based). This comparison is fundamental to making informed decisions as a C++ developer and goes right to the heart of your goal to understand how things work "under the hood."

Revisiting `std::vector`: Contiguous Memory

As a quick refresher, a std::vector object itself is small and typically lives on the stack. It manages a dynamic array of elements in a single, contiguous block of memory on the heap.

What does std::vector look like in memory?

The Stack Overflow post 'What does std::vector look like in memory?' has an excellent, simple diagram illustrating this.

Review the first answer by Vittorio Romeo. Focus on the MS Paint diagram. It clearly shows the std::vector object on the stack with a pointer to the heap-allocated buffer. This is the mental model you should have.

The consequence of this contiguous layout is that when the vector's capacity is exceeded, it must perform a costly reallocation.

Back To Basics: C++ Containers

The video 'Back To Basics: C++ Containers' provides a great dynamic visualization of how a vector grows and reallocates.

Watch the segment from 10:56 to 18:22. The creator uses a small program to demonstrate how adding elements to a vector can force the entire block of memory to move, changing the addresses of all its elements. This reinforces the concepts from our last lesson on iterator invalidation.

`std::list`: The Node-Based Alternative

Now, let's contrast this with std::list. A std::list is a doubly-linked list. Instead of one large memory block, it's composed of individual nodes scattered across the heap. Each node contains:

The element itself.
A pointer to the next node in the sequence.
A pointer to the previous node in the sequence.

Comparison of std::list and std::vector Internal Structures — This image provides a high-level visual comparison. `std::vector` uses a single contiguous array, while `std::list` links together separate, non-contiguous nodes.

The std::list object itself only needs to store pointers to the head and tail nodes.

Internal Structure of std::list<T> — This diagram shows a more detailed view of the node structure for `std::list`, highlighting the `_M_next` and `_M_prev` pointers that form the links between elements.

This node-based design has profound implications.

Back To Basics: C++ Containers

Let's return to the 'Back To Basics: C++ Containers' video to see the mechanics of std::list.

Watch from 18:22 to 21:24. Notice how adding new elements simply involves allocating a new node and updating pointers. The existing nodes never move, which is the complete opposite of how std::vector behaves.

The Performance Showdown: It's All About the Cache

On paper, std::list seems superior for insertions and deletions. A vector has O(N) complexity for an insertion in the middle (shifting elements), while a list has O(1) complexity (re-wiring pointers). However, real-world performance is not determined by algorithmic complexity alone. Your systems background and study of OSTEP will make the following reason particularly clear: the CPU cache.

Modern CPUs are orders of magnitude faster than main memory (RAM). To hide this latency, CPUs use small, extremely fast memory caches. When your program requests data from a memory address, the CPU doesn't just fetch that single byte; it fetches a whole cache line (typically 64 bytes) of adjacent memory.

This is where std::vector's contiguous layout becomes a massive performance win.

std::vector and Spatial Locality: When you iterate through a vector, you access memory sequentially. Accessing v[0] pulls a cache line into the cache. This same cache line likely also contains v[1], v[2], ..., v[15] (for 4-byte integers). The CPU's access to these subsequent elements becomes an incredibly fast cache hit. Furthermore, the hardware prefetcher detects this linear access pattern and starts loading the next cache lines before you even ask for them.
std::list and Pointer Chasing: When you iterate through a list, you are pointer chasing. Each node can be in a completely different part of memory. Accessing the first node pulls in its cache line. To get to the next element, the CPU must dereference the next pointer, find a totally new memory address, and likely fetch a new cache line from main memory, resulting in a slow cache miss. The prefetcher cannot predict these jumps and is rendered useless.

Cache-Friendly C++ - Jonathan Müller - CppCon 2025

The CppCon talk 'Cache-Friendly C++' is one of the best explanations of this phenomenon. It shows why our intuition about data structures can be wrong if we don't account for the hardware.

Please watch from 02:09 to 11:06 and from 26:32 to 31:52. The speaker, Jonathan Müller, will cover: A benchmark showing a sorted std::vector outperforming theoretically faster containers. A clear explanation of the CPU cache hierarchy and cache lines. A direct comparison of the cache-friendliness of std::vector versus the cache-hostility of std::list and other node-based containers (std::map).

The article "Beating the Cache" reinforces these concepts with a direct benchmark comparing linear access (like std::vector) against pointer-chasing (like std::list). The results are stark: pointer-chasing is dramatically slower due to its inability to leverage the cache.

Summary of Trade-offs

Let's summarize the key differences in a table.

Feature	`std::vector`	`std::list`
Memory Layout	Single contiguous block on the heap.	Individual nodes scattered on the heap.
Memory Overhead	Low. Only stores elements.	High. Stores `next`/`prev` pointers for each element.
Cache-Friendliness	Excellent. High spatial locality, benefits from prefetching.	Poor. Pointer-chasing leads to cache misses.
Random Access	O(1). Fast indexing via pointer arithmetic.	O(N). Must traverse the list from an end.
Insertion/Deletion	O(N). Elements must be shifted.	O(1) (if you have an iterator to the location).
Iterator Invalidation	Frequent. Reallocation invalidates all iterators. Insertion/erasure invalidates subsequent iterators.	Rare. Only iterators to erased elements are invalidated.

Test your understanding!

You are designing a system to process logs from a web server. You will read millions of log entries into memory at startup. After that, the primary operation is to iterate through all the logs multiple times to generate different statistical reports. The collection of logs is never modified after startup.

Which container, std::vector or std::list, would you choose for storing the log entries, and why? Justify your answer based on memory layout and cache performance.

Show answer

The clear choice is std::vector.

The dominant operation is frequent iteration over the entire dataset. std::vector's contiguous memory layout provides excellent spatial locality. This means that as you iterate from one log entry to the next, it's highly likely the next entry is already in the CPU cache, making traversal extremely fast. The hardware prefetcher will further accelerate this process.

A std::list, on the other hand, would store each log entry in a separate node, likely scattered across memory. Iterating through the list would involve constant pointer-chasing, leading to frequent cache misses and significantly slower performance. Since there are no insertions or deletions after initialization, the main advantage of std::list is irrelevant.

Conclusion

Today we've seen a classic engineering trade-off. While std::list offers superior algorithmic complexity for certain operations, the realities of modern hardware architecture mean that std::vector is often the superior choice in practice.

Key Takeaways:

std::vector uses a contiguous memory block, which is extremely friendly to CPU caches and hardware prefetchers, resulting in very fast traversal.
std::list uses non-contiguous, pointer-linked nodes, which causes frequent cache misses during traversal, making it much slower for iteration.
The performance cost of shifting elements in a vector can often be less than the cost of the cache misses incurred while traversing a list to find an insertion/deletion point.
Default to std::vector. Only consider std::list if you have evidence from profiling that element shifting is a major bottleneck and you cannot tolerate std::vector's iterator invalidation rules.

What's Next?

This theme of memory layout dictating performance extends to other containers as well. In the next lesson, we will analyze another pair of fundamental containers: std::map and std::unordered_map. This will introduce you to two new underlying data structures—a balanced binary tree (more pointer chasing!) and a hash table—and we'll explore their respective performance trade-offs, once again through the critical lens of memory and cache behavior.

Recommended resources

Revisiting std::vector: Contiguous Memory