Ask a C++ developer to design a limit order book, and you will almost always get the same answer: std::map<Price, Level>. It is the answer every tutorial gives, the answer that passes the coding screen, and the answer that feels obviously right: an order book is a collection of price levels that must stay sorted, and std::map is the sorted container. Case closed.
Except that if you look at how production trading systems are actually built, you will struggle to find a red-black tree anywhere near the hot path. The container that “obviously” fits the problem is quietly absent from the systems where the problem matters most.
This article explains why, by putting three candidates through the same test: std::unordered_map, std::map, and — the one nobody suggests in interviews — std::vector.
1.Refresher on std::map, std::unordered_map and std::vectors
What are maps?
A std::map is a sorted associative container storing key-value pairs with unique keys, typically implemented as a red-black tree.
Lookups, insertions, and deletions are all O(log n), and iterating gives you elements in key order.
A good summary video:
What are unordered maps?
A std::unordered_map is a hash table storing key-value pairs with unique keys but no ordering guarantee.
Average O(1) lookup, insert, and erase, degrading to O(n) in the worst case (hash collisions).
The trade-offs: it needs a hash function for the key type, iteration order is unspecified, and the node-based bucket implementation means pointer chasing that can hurt cache performance — which is why HFT code often reaches for open-addressing alternatives like absl::flat_hash_map.
What are vectors?
std::vector is C++’s dynamic array: it stores elements in contiguous memory, gives fast indexed access, and automatically grows when you add more elements.
How to use them to create an order book? But, by the way, what’s an order book?
2. Refresher on order books
An order book is the mechanism that allows a market to match buyers and sellers.
A trader can send:
Buy 100 shares at 99.98
Sell 200 shares at 100.02
Buy 50 shares at market
Cancel order #123
Modify order #456The exchange maintains the book and decides what happens next.
An order book is the live list of buyers and sellers for a financial instrument.
At first, it is often shown as a table:
| Bid Size | Bid Price | Ask Price | Ask Size |
|---|---|---|---|
| 500 | 99.98 | 100.02 | 300 |
| 1,200 | 99.97 | 100.03 | 700 |
| 800 | 99.96 | 100.04 | 1,500 |
The bid side represents buyers.
The ask side represents sellers.
Here, “size” means quantity.
So:
500 at 99.98 means buyers want to buy 500 shares at 99.98.
300 at 100.02 means sellers want to sell 300 shares at 100.02.
Each row is also called a price level.
Level 1 is the best available price on each side:
Level 1 bid = 99.98 x 500
Level 1 ask = 100.02 x 300Level 2 is the next best price:
Level 2 bid = 99.97 x 1,200
Level 2 ask = 100.03 x 700Level 3 is the next one after that:
Level 3 bid = 99.96 x 800
Level 3 ask = 100.04 x 1,500A more natural way to visualize the book is vertically:
ASK SIDE
Level 3 100.04 x 1,500
Level 2 100.03 x 700
Level 1 100.02 x 300 <- best ask
spread = 0.04
Level 1 99.98 x 500 <- best bid
Level 2 99.97 x 1,200
Level 3 99.96 x 800
BID SIDEThe best bid is the highest price someone is willing to buy at.
The best ask is the lowest price someone is willing to sell at.
3. Model an Order Book in C++: Various Attempts
Attempt 1: hash the price levels with std::unordered_map
The message flow suggests an obvious first design. Cancels dominate, and cancels are lookups — so we optimize for lookup. A hash map from price to level gives us O(1) access to any level, and std::unordered_map is sitting right there in the standard library:
cpp
std::unordered_map<Price, Level> bids_;
std::unordered_map<Price, Level> asks_;Adds are O(1). Cancels are O(1). Modifies are O(1). On paper we’ve made the dominant operations constant-time, and for a few minutes this feels like a solved problem.
Then we implement best_bid().
There is no “first element” in a hash map. Hashing deliberately destroys ordering — that’s what makes it fast — so the only way to find the highest bid is to scan every populated level. The book’s single most frequent query, the one strategy code calls on effectively every tick, has become O(n) over the entire side. Depth walks are worse: there’s no notion of “the next level down” at all; we’d re-scan or sort on demand.
We didn’t build a slow order book. We built something that structurally isn’t an order book. An order book’s defining property is that its levels are ordered — it’s in the name — and we chose the one container whose entire design premise is discarding order. The lookup speed was real, but we optimized the operation that was never going to be the bottleneck and broke the one that defines the product.
Attempt 2: the tree with std::map
So ordering is non-negotiable. The standard library’s ordered associative container is std::map, a red-black tree, and it fixes everything the hash map broke:
std::map<Price, Level, std::greater<Price>> bids_; // begin() is best bid
std::map<Price, Level> asks_; // begin() is best askBest bid is bids_.begin() — O(1). Depth walks are in-order traversal. Adds, cancels, and modifies are O(log n), and with a few hundred populated levels, log n is under ten comparisons. This is the textbook answer, it’s correct, and it’s what most order book implementations you’ll find online actually use.
Now replay a day of market data through it and watch what the hardware does.
A full implementation of that version that would make you pass the quant interview in C++ has been proposed in our first article on order books:
using OrderId = uint64_t;
using Qty = int64_t; // signed for partial fills math
using Px = int64_t; // price in ticks
enum Side { Buy, Sell };
struct Order {
OrderId id;
Side side;
Px price;
Qty qty; // remaining
uint64_t ts; // exchange/seq time for tie-breaks
// intrusive list pointers for O(1) erase
Order* prev = nullptr;
Order* next = nullptr;
};
struct Level {
Px price;
Order* head = nullptr;
Order* tail = nullptr;
inline void push_back(Order* o);
inline void erase(Order* o);
bool empty() const { return head == nullptr; }
};
// price → level; bids need descending, asks ascending
using BookSide = std::map<Px, Level, std::greater<Px>>; // bids
using BookSideAsk = std::map<Px, Level, std::less<Px>>; // asks
struct OrderBook {
BookSide bids;
BookSideAsk asks;
std::unordered_map<OrderId, Order*> by_id; // direct handle for cancel/replace
// API
void add_limit(OrderId id, Side side, Px px, Qty qty, uint64_t ts);
void cancel(OrderId id);
void replace(OrderId id, Px new_px, Qty new_qty, uint64_t ts); // cancel+add semantics
void match_market(Side side, Qty qty);
// helpers
Level& level(BookSide& s, Px px);
Level& level(BookSideAsk& s, Px px);
};
Attempt 3: keep it sorted, make it contiguous
If pointer chasing is the disease, contiguity is the cure. A sorted std::vector<Level> with binary search keeps the ordering guarantee but lays every level out in a single flat allocation:
cpp
std::vector<Level> bids_; // sorted; back() is best bidLookup is std::lower_bound — still O(log n) comparisons, but now the search touches a handful of cache lines in one array instead of five scattered heap nodes, and the hardware prefetcher can see where we’re going. Best bid is back(). Insertion of a new level requires shifting elements — O(n) in theory — but here the workload rescues us: adds cluster near the touch, so if the vector is sorted with the best price at the back, the memmove is almost always a few elements. In practice this structure embarrasses the tree on a realistic feed.
And yet, benchmark it honestly and there’s a residue we can’t scrub out. Every operation still begins with a search — a binary search is a series of dependent loads, each one’s address unknown until the previous compare resolves, so the pipeline stalls on each step. We’ve made searching cheap. We haven’t asked whether we need to search at all.
Attempt 4: stop searching
Every structure so far has treated the price as an opaque key — something to hash, compare, or binary-search for. But a price in a limit order book is none of those things. Exchanges don’t accept arbitrary prices: every instrument trades on a fixed grid, an integer number of ticks. Two consecutive price levels don’t just happen to be close — they differ by exactly one tick, always. That’s not a statistical tendency we can exploit; it’s a hard constraint the venue enforces on every order.
Once you see prices as grid positions rather than keys, the search problem dissolves. If we know the tick size and pick an anchor price for index zero, then the level for any price isn’t something we find — it’s something we compute.
index = (price − anchor) / tickOne subtraction, one division by a constant, one indexed load into a flat array. No hash function, no comparisons, no dependent loads waiting on the previous step to resolve. The lookup that cost the tree five scattered pointer dereferences and cost the sorted vector a pipeline-stalling binary search is now cheaper than either structure’s first step.
4. A Proposition of Implementation for Attempt 4
In the approach we’re presenting, prices are ticks on a fixed grid, so the book is a flat array of price levels where a price is converted to an index by one subtraction — no hashing, no tree, no search — with a cached best index and each level holding a FIFO of pool-allocated orders linked intrusively.
Adds, cancels, and executions each cost an arithmetic index or an O(1) ID lookup plus an O(1) unlink, touching two or three cache lines and zero heap allocations on the hot path.
Let’s start with an order_book.hpp:
// order_book.hpp — tick-indexed limit order book
//
// Design (see article): contiguous array of price levels indexed by tick
// offset, intrusive doubly-linked FIFO per level, pre-allocated order pool,
// open-addressing map for OrderId -> Order*. Zero heap allocation on the
// hot path after construction.
//
// Conventions:
// - Price is an integer number of ticks (scale at the feed decoder).
// - OrderId 0 and ~0 are reserved (empty / tombstone sentinels in IdMap).
#pragma once
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>
using Price = std::int64_t;
using Qty = std::int64_t;
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Bid, Ask };
// ---------------------------------------------------------------------------
// Order: 64 bytes, cache-line aligned. prev/next are intrusive — the order
// *is* its own list node, so joining/leaving a level allocates nothing.
// ---------------------------------------------------------------------------
struct alignas(64) Order {
OrderId id;
Qty qty;
Price price;
Side side;
Order* prev;
Order* next;
};
static_assert(sizeof(Order) == 64, "one order per cache line");
// ---------------------------------------------------------------------------
// OrderPool: all orders live in one contiguous slab allocated at startup.
// alloc/release are a free-list push/pop — no new/delete on the hot path.
// ---------------------------------------------------------------------------
class OrderPool {
public:
explicit OrderPool(std::size_t capacity) : slots_(capacity) {
free_.reserve(capacity);
for (std::size_t i = capacity; i-- > 0;)
free_.push_back(&slots_[i]);
}
Order* alloc() {
assert(!free_.empty() && "pool exhausted — size it to the session");
Order* o = free_.back();
free_.pop_back();
return o;
}
void release(Order* o) { free_.push_back(o); }
private:
std::vector<Order> slots_;
std::vector<Order*> free_;
};
// ---------------------------------------------------------------------------
// Level: FIFO queue of resting orders at one price. head is oldest (first to
// fill), tail is where adds append — price-time priority falls out of the
// list order. total_qty is maintained incrementally so top-of-book snapshots
// never walk the list.
// ---------------------------------------------------------------------------
struct Level {
Order* head = nullptr;
Order* tail = nullptr;
Qty total_qty = 0;
bool empty() const { return head == nullptr; }
void push_back(Order* o) {
o->prev = tail;
o->next = nullptr;
if (tail) tail->next = o; else head = o;
tail = o;
total_qty += o->qty;
}
// O(1) given the order pointer — no search. This is why cancels, the
// dominant message type, stay cheap.
void unlink(Order* o) {
if (o->prev) o->prev->next = o->next; else head = o->next;
if (o->next) o->next->prev = o->prev; else tail = o->prev;
total_qty -= o->qty;
}
};
// ---------------------------------------------------------------------------
// BookSide: the tick-indexed array. Price -> level is one subtraction and
// one indexed load; no hashing, no comparisons, no pointer chasing.
// best_ caches the top of book; when the top level empties we scan linearly
// toward the interior — adjacent prices are adjacent cache lines, and the
// next populated level is almost always within a few ticks.
// ---------------------------------------------------------------------------
template <bool IsBid>
class BookSide {
public:
static constexpr std::size_t kLevels = std::size_t{1} << 16;
static constexpr std::size_t kNone = ~std::size_t{0};
explicit BookSide(Price anchor)
: levels_(kLevels), anchor_(anchor) {}
void add(Order* o) {
const std::size_t idx = index(o->price);
levels_[idx].push_back(o);
if (best_ == kNone || better(idx, best_)) best_ = idx;
}
void remove(Order* o) {
const std::size_t idx = index(o->price);
levels_[idx].unlink(o);
if (idx == best_ && levels_[idx].empty()) advance_best();
}
void reduce(Order* o, Qty by) {
o->qty -= by;
levels_[index(o->price)].total_qty -= by;
}
bool empty() const { return best_ == kNone; }
Price best_price() const { return anchor_ + static_cast<Price>(best_); }
Qty best_qty() const { return levels_[best_].total_qty; }
const Order* best_order() const { return levels_[best_].head; }
private:
std::size_t index(Price p) const {
assert(p >= anchor_ &&
static_cast<std::size_t>(p - anchor_) < kLevels &&
"price outside book range — re-anchor on the slow path");
return static_cast<std::size_t>(p - anchor_);
}
static bool better(std::size_t a, std::size_t b) {
if constexpr (IsBid) return a > b; // best bid = highest price
else return a < b; // best ask = lowest price
}
void advance_best() {
if constexpr (IsBid) {
while (best_ != 0) {
--best_;
if (!levels_[best_].empty()) return;
}
} else {
while (best_ + 1 < kLevels) {
++best_;
if (!levels_[best_].empty()) return;
}
}
best_ = kNone; // side is empty
}
std::vector<Level> levels_; // one flat allocation, made once
Price anchor_; // price at index 0
std::size_t best_ = kNone;
};
// ---------------------------------------------------------------------------
// IdMap: OrderId -> Order*, open addressing with linear probing. Flat slot
// array — one hash, then a short contiguous probe. Sized 2x expected load
// at construction; erases leave tombstones (fine for a trading session,
// rebuild between sessions if reusing).
// ---------------------------------------------------------------------------
// ---------------------------------------------------------------------------
// IdMap: OrderId -> Order*, open addressing with linear probing. Flat slot
// array — one hash, then a short contiguous probe. Sized 2x expected load
// at construction; erases leave tombstones (fine for a trading session,
// rebuild between sessions if reusing).
// ---------------------------------------------------------------------------
class IdMap {
public:
explicit IdMap(std::size_t expected) {
std::size_t cap = 1;
while (cap < expected * 2) cap <<= 1;
slots_.assign(cap, Slot{kEmpty, nullptr});
mask_ = cap - 1;
}
void insert(OrderId id, Order* o) {
std::size_t i = hash(id) & mask_;
while (slots_[i].key != kEmpty && slots_[i].key != kTomb)
i = (i + 1) & mask_;
slots_[i] = Slot{id, o};
}
Order* find(OrderId id) const {
std::size_t i = hash(id) & mask_;
while (slots_[i].key != kEmpty) {
if (slots_[i].key == id) return slots_[i].val;
i = (i + 1) & mask_;
}
return nullptr;
}
void erase(OrderId id) {
std::size_t i = hash(id) & mask_;
while (slots_[i].key != kEmpty) {
if (slots_[i].key == id) {
slots_[i].key = kTomb;
slots_[i].val = nullptr;
return;
}
i = (i + 1) & mask_;
}
}
private:
static constexpr OrderId kEmpty = 0;
static constexpr OrderId kTomb = ~OrderId{0};
struct Slot { OrderId key; Order* val; };
static std::size_t hash(OrderId id) { // splitmix64 finalizer
std::uint64_t x = id;
x ^= x >> 33; x *= 0xff51afd7ed558ccdULL;
x ^= x >> 33; x *= 0xc4ceb9fe1a85ec53ULL;
x ^= x >> 33;
return static_cast<std::size_t>(x);
}
std::vector<Slot> slots_;
std::size_t mask_;
};
// ---------------------------------------------------------------------------
// OrderBook: ties the pieces together. The three feed-driven mutations map
// onto it directly:
// Add -> pool alloc, arithmetic index, list append (0 allocations)
// Cancel -> id lookup, O(1) unlink, pool release (0 allocations)
// Execute -> id lookup, reduce or remove (0 allocations)
// ---------------------------------------------------------------------------
class OrderBook {
public:
struct Quote { Price price; Qty qty; bool valid; };
OrderBook(Price anchor, std::size_t max_live_orders)
: bids_(anchor), asks_(anchor),
pool_(max_live_orders), ids_(max_live_orders) {}
void add(OrderId id, Side side, Price price, Qty qty) {
Order* o = pool_.alloc();
*o = Order{id, qty, price, side, nullptr, nullptr};
if (side == Side::Bid) bids_.add(o); else asks_.add(o);
ids_.insert(id, o);
}
void cancel(OrderId id) {
if (Order* o = ids_.find(id)) remove(o);
}
// Execution reported by the feed against a resting order.
void execute(OrderId id, Qty exec_qty) {
Order* o = ids_.find(id);
if (!o) return;
if (exec_qty >= o->qty) {
remove(o);
} else if (o->side == Side::Bid) {
bids_.reduce(o, exec_qty);
} else {
asks_.reduce(o, exec_qty);
}
}
Quote best_bid() const {
return bids_.empty() ? Quote{0, 0, false}
: Quote{bids_.best_price(), bids_.best_qty(), true};
}
Quote best_ask() const {
return asks_.empty() ? Quote{0, 0, false}
: Quote{asks_.best_price(), asks_.best_qty(), true};
}
private:
void remove(Order* o) {
if (o->side == Side::Bid) bids_.remove(o); else asks_.remove(o);
ids_.erase(o->id);
pool_.release(o);
}
BookSide<true> bids_;
BookSide<false> asks_;
OrderPool pool_;
IdMap ids_;
};How to test this approach?
Create a demo.cpp:
#include "order_book.hpp"
#include <cstdio>
static void print_top(const OrderBook& book, const char* tag) {
auto b = book.best_bid();
auto a = book.best_ask();
std::printf("%-28s bid: ", tag);
if (b.valid) std::printf("%lld x %lld", (long long)b.qty, (long long)b.price);
else std::printf("--");
std::printf(" ask: ");
if (a.valid) std::printf("%lld x %lld", (long long)a.qty, (long long)a.price);
else std::printf("--");
std::printf("\n");
}
int main() {
// Anchor at tick 10'000, capacity for 1M live orders.
OrderBook book(/*anchor=*/10'000, /*max_live_orders=*/1'000'000);
book.add(1, Side::Bid, 10'100, 500);
book.add(2, Side::Bid, 10'101, 300); // better bid
book.add(3, Side::Bid, 10'101, 200); // joins queue behind id 2
book.add(4, Side::Ask, 10'103, 400);
book.add(5, Side::Ask, 10'102, 250); // better ask
print_top(book, "after adds");
book.cancel(2); // partial drain of best bid level
print_top(book, "cancel id 2");
book.cancel(3); // best bid level empties -> scan inward
print_top(book, "cancel id 3");
book.execute(5, 100); // partial execution at best ask
print_top(book, "execute 100 vs id 5");
book.execute(5, 150); // fills remainder -> level empties
print_top(book, "execute 150 vs id 5");
book.cancel(1);
book.cancel(4);
print_top(book, "book emptied");
return 0;
}Let’s compile and run:
g++ -std=c++20 -O2 -Wall -Wextra -o demo demo.cpp && ./demo
Which gives:
after adds bid: 500 x 10101 ask: 250 x 10102
cancel id 2 bid: 200 x 10101 ask: 250 x 10102
cancel id 3 bid: 500 x 10100 ask: 250 x 10102
execute 100 vs id 5 bid: 500 x 10100 ask: 150 x 10102
execute 150 vs id 5 bid: 500 x 10100 ask: 400 x 10103
book emptied bid: -- ask: --