Building a Limit Order Book: Price-Time Priority Matching in C++

A limit order book is the central data structure of any electronic exchange. It holds outstanding buy and sell orders and matches them when prices cross. This article walks through a clean C++ implementation that handles partial fills, duplicate rejection, O(1) cancellation, and the subtle aggressor-identification problem.

---

The Core Rules

Every limit order book operates under price-time priority:

1. Best price first — the highest bid (buy order) always matches against the lowest ask (sell order).
2. FIFO within each price level — orders at the same price are matched in arrival order.
3. A trade occurs iff best_bid_price >= best_ask_price.
4. Partial fills are allowed — an order’s remaining quantity stays in the book until filled or canceled.

The aggressor is always the newcomer — the order being added “walks the book” and consumes resting liquidity. The aggressor pays the resting order’s price, not its own.

---

Data Model

Order

using Id = size_t;
using Price = long;
using Quantity = int;

class Order {
public:
    Order(Id orderId, Price level, bool isBuy, Quantity quantity)
        : orderId_{orderId}, level_{level},
          isBuy_{isBuy}, quantity_{quantity},
          initialQuantity_{quantity} {}

    // Auto-incrementing priority for FIFO within each price level
    Id Priority() const { return instance_; }
    Id OrderId()     const { return orderId_; }
    Price Level()    const { return level_; }
    bool IsBuy()     const { return isBuy_; }

    Quantity GetRemainingQuantity() const { return quantity_; }
    bool IsFilled() const { return quantity_ == 0; }

    void Fill(Quantity qty) {
        if (qty > quantity_)
            throw std::logic_error("Overfill");
        quantity_ -= qty;
    }

private:
    Id orderId_;
    Price level_;
    bool isBuy_;
    Quantity quantity_;
    Quantity initialQuantity_;

    Id instance_{InstanceId++};
    static inline Id InstanceId = 0;
};

The key design choice here is the instance_ field: it’s a monotonically increasing counter assigned at construction. This gives every order a globally unique Priority() that represents its arrival time, enabling deterministic aggressor identification — critical when both sides of a match were added in the same microsecond.

Trade

struct Trade {
    Id       OrderIdA;          // Resting (passive) order
    Id       OrderIdB;          // Incoming (aggressor) order  
    Id       AggressorOrderId;  // Same as OrderIdB
    bool     AggressorIsBuy;
    Price    Level;             // Price of the resting order
    Quantity Size;
};
using Trades = std::vector<Trade>;

---

Data Structures

The order book needs three capabilities:

Operation	Requirement	Solution
Find best bid/ask	O(1)	std::map ordered by price
Match within a price level	FIFO	std::vector<Order> with .front() access
Look up by ID (cancel)	O(1)	std::unordered_map<Id, OrderMetadata>

class Orderbook {
private:
    std::map<Price, std::vector<Order>> bids_;  // Descending via reverse iteration
    std::map<Price, std::vector<Order>> asks_;  // Ascending (default)
    std::unordered_map<Id, OrderMetadata> data_; // ID → (price, side)
};

Why std::map? std::map is ordered by key, so bids_.rbegin() gives the highest bid in O(1) and asks_.begin() gives the lowest ask in O(1). Yes, std::map has O(log N) insertion — but in practice, a limit order book rarely has more than a few hundred price levels, and the constant factors of a red-black tree are excellent. For nanosecond-scale matching, a custom array-based index over tick-aligned prices would be faster.

Why std::vector for orders within a level? Orders are always consumed from the front (oldest first) and appended at the back (newest last). std::vector wins on cache locality — all orders at a price level sit in contiguous memory. std::deque or std::list would spread them across the heap, hurting the matching loop’s performance.

Why the data_ lookup map? Without it, canceling an order would require scanning every price level. With it, we jump directly to the order in O(1). The map stores metadata (price, side) since the actual Order object lives in the bids_ or asks_ vector.

---

Implementation

Adding an Order

Trades AddOrder(const Order& order) {
    // 1. Reject duplicates
    if (data_.contains(order.OrderId()))
        return {};

    // 2. Record in lookup map
    data_.insert({order.OrderId(), order.ToMetadata()});

    // 3. Insert into price level
    if (order.IsBuy())
        bids_[order.Level()].push_back(order);
    else
        asks_[order.Level()].push_back(order);

    // 4. Match (aggressor is the last-inserted order)
    return Match();
}

Steps 3 and 4 are order-dependent: the aggressor must already be in the book before Match() runs, because Match() compares Priority() to determine which order is the aggressor.

Matching

Trades Match() {
    Trades trades;

    while (true) {
        if (bids_.empty() || asks_.empty())
            break;

        auto& [bidPrice, bidOrders] = *bids_.rbegin(); // Highest bid
        auto& [askPrice, askOrders] = *asks_.begin();   // Lowest ask

        if (askPrice > bidPrice)  // No crossing — stop
            break;

        // Match within this price level
        while (!bidOrders.empty() && !askOrders.empty()) {
            auto& bid = bidOrders.front();
            auto& ask = askOrders.front();

            Quantity matchQty = std::min(
                bid.GetRemainingQuantity(),
                ask.GetRemainingQuantity()
            );

            bid.Fill(matchQty);
            ask.Fill(matchQty);

            // Determine aggressor: the one that arrived later
            bool bidIsAggressor = bid.Priority() > ask.Priority();

            trades.push_back({
                bid.OrderId(),
                ask.OrderId(),
                bidIsAggressor ? bid.OrderId() : ask.OrderId(),
                bidIsAggressor,
                askPrice,   // Trade at resting order's price
                matchQty,
            });

            if (bid.IsFilled()) {
                bidOrders.erase(bidOrders.begin());
                data_.erase(bid.OrderId());
            }
            if (ask.IsFilled()) {
                askOrders.erase(askOrders.begin());
                data_.erase(ask.OrderId());
            }
        }

        // Clean up empty price levels
        if (bidOrders.empty()) bids_.erase(bidPrice);
        if (askOrders.empty()) asks_.erase(askPrice);
    }

    return trades;
}

The aggressor identification problem is the subtlest part. Consider this scenario:

Time 0: AddOrder(Buy @100, qty=10)  → added to bids
Time 0: AddOrder(Sell @99, qty=5)   → matches!

Which order is the aggressor? The sell order — it crossed the spread and consumed the resting buy. But both were added in the same call chain (AddOrder → Match). Without explicit priority tracking, we’d need to pass the aggressor ID through the call stack. The Priority() counter cleanly solves this: the order with the higher instance number is the aggressor.

Canceling an Order

void CancelOrder(Id orderId) {
    if (!data_.contains(orderId))
        return;

    const auto& meta = data_.at(orderId);

    // Locate the correct price level
    auto& levels = meta.IsBuy ? bids_ : asks_;
    auto it = levels.find(meta.Level);
    if (it == levels.end()) return;

    auto& orders = it->second;
    orders.erase(
        std::remove_if(orders.begin(), orders.end(),
            [&](const Order& o) { return o.OrderId() == orderId; }
        ),
        orders.end()
    );

    if (orders.empty())
        levels.erase(it);

    data_.erase(orderId);
}

std::remove_if + erase is the standard erase-remove idiom. For a vector, this is O(N) in the price level’s order count — typically small enough that it’s fine. If cancellation throughput needs to be higher, a std::list or intrusive linked list within the level would enable O(1) removal.

---

Edge Cases

Scenario	Behavior
Single order, no match	Insert silently, return empty Trades
Non-crossing prices	Bid @99, Ask @100 → no trade, both stay
Partial fill	Bid 100 @50, Sell 70 @50 → trade 70, bid 30 remains
Duplicate order ID	Second AddOrder with same ID → rejected silently
Cancel non-existent ID	No-op, no error
Cancel partially filled	Remaining quantity removed, no trade generated
Multi-level matching	Aggressor sweeps through multiple price levels → multiple trades

---

The vector vs list Trade-off

A common interview follow-up question: why use std::vector instead of std::list for orders within a price level?

Property	std::vector	std::list
Cache locality	✅ Contiguous memory	❌ Scattered across heap
Front access	✅ O(1)	✅ O(1)
Front removal	❌ O(N) shift	✅ O(1)
Append	✅ O(1) amortized	✅ O(1)
Memory overhead	✅ Minimal (just the data)	❌ Two pointers per node
Iteration	✅ Fast, prefetchable	❌ Pointer chasing

For a matching engine, the dominant operation is consuming orders from the front — and std::vector’s O(N) shift is paid at removal. In practice, with typical price-level depths of 10-100 orders, the shift cost is dwarfed by the cache benefits during iteration. For extreme depth (thousands of orders at one price), std::deque or boost::container::devector can be a better balance.

---

Key Takeaways

1. std::map + std::vector is a pragmatic choice — good enough for 99% of limit order book implementations
2. Priority counters solve the aggressor identification problem without threading metadata through the call stack
3. Matching must happen before inserting the aggressor’s residual quantity — the incoming order walks the book, consuming resting liquidity first
4. The erase-remove idiom works fine for cancellation at realistic depths; optimize only when profiled
5. Cache locality matters more than asymptotic complexity for the hot matching loop

Understanding limit order book internals is table stakes for any quant developer interview. The same principles — price-time priority, partial fills, aggressor identification — apply whether you’re building a matching engine for equities, futures, or crypto.