Why did that order fill first?
An order book is the queue of orders waiting to trade: buys on one side, sells on the other, each with a price and a size. Anything that can trade does so at the price already in the book, and the rest wait in line. Better prices go first, meaning the highest buy or the lowest sell, and at the same price the older order goes first.
Below is one small example, one event at a time. The prices are invented for the example, and the section under the book shows the code that produced every number in it.
The same four units fill in a different order when the older bid is re-sent before the sell arrives.
0 / 0
← and → step through
Events
Starting position
The book starts empty. Move through the list to see orders queue and match.
A resting order waits until a new order can trade with it.
Predict
Fills on this step
No fill on this step.
The order book
No orders yet
Bar length is size from the touch, summed outward. A − marks size the order just filled.
Cumulative depth after each event, in event order, not time
Read the matcher
Every queue, price and fill above is what lob::OrderBook returned when orda_replay replayed the scenario. This page runs no matching logic of its own.
Prices sort best first on each side
Bids are keyed by a descending comparator and asks by an ascending one, so the first level in each map is the best price on that side. Matching never searches for the touch. It starts there and walks outward, which is why the bars above grow leftward from the best bid and rightward from the best ask.
using BidLevels = std::map<Price, PriceLevel, std::greater<Price>>;
using AskLevels = std::map<Price, PriceLevel, std::less<Price>>;A price level is a queue
Inside a level the orders are a list in the order they arrived, and nothing reorders it. The queue beside the ladder is that list: the number on each ticket is its position counted from the front, and that is the position which decides who fills first.
struct PriceLevel {
Price price{};
Quantity total_qty{};
std::list<Order> orders;
};A new order joins the back
A resting order is appended, so arriving at a price that already has orders puts the newcomer behind everyone standing there. That is the time half of price-time priority in one call.
PriceLevel& level = ensure_level(side, price);
level.orders.push_back(Order{order_id, side, price, qty});A fill takes the front
A fill takes the front of the level and shrinks it, and an order leaves the queue only when its size reaches zero. The sell on the last event of the default run takes three units from order 1 and one from order 2, because that is the order the two are standing in.
Order& resting = level.orders.front();
const Quantity fill_qty = std::min(incoming_qty, resting.qty);A modify is a cancel and a replace
An accepted modify removes the order first and then matches the replacement, so whatever is left rests at the back of its price queue. Re-sending order 1 at the same price and size changes nothing about the order except its place, which is why the re-sent run above fills order 2 first, on the same two prices and the same four units.
const Side side = it->second.order_it->side;
remove_order(order_id, it->second);
const Quantity remaining = match_incoming(order_id, side, new_price, new_qty, trades);
if (remaining > 0) {
add_resting_order(order_id, side, new_price, remaining);
}Why a map and a list, and what that costs
The ordered map puts the best price first on each side, so matching walks outward from the touch without searching for it, and the list inside a level keeps arrival order: appending is constant time and a fill takes the front. Because a list never moves its existing elements, the order index can hold an iterator straight to the order it belongs to, so a cancel unlinks in constant time too.
That is what it costs. A level lookup is O(log L) in the number of distinct prices, and both containers are node-based, so every order and every level is its own small allocation and the book is scattered rather than contiguous. The other two backends in this repository trade differently: pooled_order_book preallocates order slots, and ladder_order_book replaces the map with a bounded price array. The baseline is the one whose correctness is easiest to argue, which is why this page steps through it.