map, list and deque: when nodes and blocks earn their place

std::map is a balanced binary search tree, a red-black tree in all mainstream libraries. Each element is a node with the key, the value, three pointers (left, right, parent) and a colour bit. Lookups and inserts are O(log n), and iteration visits keys in order.

It is the right choice when you need ordering as well as lookup and the data changes often enough that a sorted vector would spend too long shifting:

• range queries: all orders with price between two values;
• iteration in key order: dumping levels best to worst;
• lower_bound and upper_bound: the first level at or beyond a price;
• stable references across inserts and erases.

Its costs are the node allocations and the pointer chase: a tree of a million elements is twenty levels deep, and each level can be a cache miss. A sorted vector with binary search makes the same number of comparisons on contiguous memory, which is much faster when updates are rare.

std::unordered_map gives no order at all. If you need "the next price up", it cannot help.

A deque stores elements in fixed-size blocks and keeps a small array of pointers to those blocks.

Pushing or popping at either end never moves existing elements: a full end block gets a new neighbour. Indexed access is constant time but costs an extra indirection through the block map. Iteration is contiguous within each block.

It is the right choice for a queue that grows and shrinks at both ends where you need references to stay valid, such as a FIFO of pending requests. Two caveats: block sizes are small in some implementations (libc++ uses 4 KB, libstdc++ 512 bytes, and MSVC's tiny 16-byte blocks make it nearly a list of elements), and a deque still allocates a block when it grows. For a fixed-size FIFO on the hot path, a ring buffer over a preallocated array is usually better (Module 4).

A doubly linked list of nodes. The previous module covered why scanning one is slow. It earns its place when you need:

• O(1) insertion and removal anywhere given an iterator, with no element moving;
• splice, moving nodes between lists without copying or allocating;
• references that survive every insert and erase of other elements.

An LRU cache is the textbook example: a list in recency order plus a hash map from key to list iterator, so that touching an entry splices its node to the front in constant time.

In trading code the same need (stable, O(1) removal from the middle of a queue) arises in price levels, where an order can be cancelled from anywhere in the time-priority queue. The usual implementation is an intrusive list: the previous and next links are fields of the order itself, and orders live in a pool. You get the list's operations without its separate allocations.

struct Order {
    std::uint32_t prev = NIL, next = NIL;   // links as pool indices, not pointers
    std::int64_t price; std::int32_t qty;
    // ...
};

std::map when I need ordered iteration or range queries over data that changes often, such as the far levels of a book. std::deque for a queue with pushes and pops at both ends where elements must not move. std::list for O(1) removal from the middle with stable references, such as an LRU cache, though on a hot path I would make it intrusive over a pool. In each case I would say what I would measure before replacing it with something flat.