Vector and list: where the data actually sits

Both containers support the same loop, and both loops are O(n):

std::int64_t total_qty(const std::vector<Quote>& v) {
    std::int64_t t = 0;
    for (const Quote& q : v) t += q.qty;
    return t;
}

std::int64_t total_qty(const std::list<Quote>& l) {
    std::int64_t t = 0;
    for (const Quote& q : l) t += q.qty;
    return t;
}

On a large container the vector version is typically several times faster, and the gap grows when the list has been built up over time by many insertions and removals. The source code gives no hint of this. The difference is entirely in where the quotes are in memory.

A std::vector<Quote> owns one heap block holding the quotes back to back. Element i + 1 starts exactly sizeof(Quote) bytes after element i. The vector object itself is three pointers: the start of the block, the end of the used part, the end of the capacity.

A std::list<Quote> owns a set of separately allocated nodes. Each node holds one quote plus two pointers, to the previous and the next node. The list object holds pointers to the first and last node and a count. Where the nodes are in memory depends on what the allocator handed out when each was created, and after a day of insertions and deletions, neighbours in the list are rarely neighbours in memory.

The processor does not read memory one value at a time. It reads it in fixed blocks called cache lines, 64 bytes on current x86 and most ARM server parts, and keeps recently used lines in small, fast caches close to the core. The next lesson goes into the mechanics; for now, two consequences are enough.

First, with a vector, one fetch brings in the next two or three quotes as well. Most iterations of the loop find their data already in the cache.

Second, the addresses in a vector are predictable. The hardware sees the loop reading upward through memory and starts fetching lines before the code asks for them. With a list, the address of node k + 1 is stored inside node k, so the next fetch cannot even begin until the current one has arrived. The loop waits on memory once per node.

There is a third, smaller cost: every list node carries two pointers, 16 bytes on a 64-bit machine. For a 24-byte quote that is two thirds as much again, so the list reads more memory to do the same work.

A good answer does not stop at "always use vector". Lists have real strengths:

• Stable addresses. A pointer or iterator to a list element stays valid while other elements are inserted and erased. A vector moves all its elements when it reallocates.
• O(1) insertion and removal in the middle, given an iterator to the position. A vector shifts every later element.
• Splicing. splice moves a range of nodes from one list to another without copying or allocating.

In low-latency code these needs are usually met in other ways: a vector of indices, a pool of nodes allocated from one contiguous block, or an intrusive list whose nodes live in an array. Module 3 covers these. The point to make in the interview is that you know what the list buys and that you would choose it for those reasons, not by default.

I would use a vector. The quotes sit contiguously, so walking them reads memory in order: each cache line fetched holds the next few quotes, and the prefetcher can run ahead of the loop. A list allocates each node separately, so every step follows a pointer to wherever that node happens to be, and the next load cannot start until the current one finishes. Both are O(n); the vector does far less waiting per element. I would only reach for a list if I needed stable iterators across insertions or cheap splicing, and even then I would look at a pool-backed or intrusive list first.