Order Book Data Structures in C++

TL;DR

An order book tracks all outstanding limit orders at every price level. HFT systems process millions of updates per second, requiring sub-microsecond add/cancel/modify. The key data structure choice is between price-level arrays (O(1) for sparse prices, cache-unfriendly) and sorted maps (cache-friendly for dense books, O(log n)). Most production systems use a hybrid.

Order book anatomy

cpp

Godbolt

Ask (sell) side:           Best ask: 150.05 → 300 shares
  150.10 → [Order C: 200]
  150.05 → [Order A: 100, Order B: 200]
  ─────── spread ────────
  150.00 → [Order D: 150, Order E: 50]
  149.95 → [Order F: 300]
Bid (buy) side:            Best bid: 150.00 → 200 shares

Operations:

add(order) — insert at price level, maintain FIFO queue within level
cancel(order_id) — O(1) lookup by ID, remove from level
modify(order_id, new_qty) — reduce qty or cancel+add (loses queue priority)
execute(order_id, qty) — partial or full fill, remove if fully filled

Price-level array implementation

For instruments with bounded price ranges (futures, FX), a flat array indexed by price is fastest:

cpp

Godbolt

struct PriceLevel {
    uint64_t total_qty = 0;
    // Intrusive linked list of orders at this price
    Order* head = nullptr;
    Order* tail = nullptr;
};

class OrderBook {
public:
    // Price encoded as integer ticks: price * 100 (2 decimal places)
    static constexpr int64_t TICK_SIZE = 100;
    static constexpr int64_t MIN_PRICE = 0;
    static constexpr int64_t MAX_PRICE = 100000 * TICK_SIZE;  // 0 to 1000.00

    PriceLevel& bidLevel(int64_t price_ticks) { return bids_[price_ticks]; }
    PriceLevel& askLevel(int64_t price_ticks) { return asks_[price_ticks]; }

    int64_t bestBid() const { return best_bid_; }
    int64_t bestAsk() const { return best_ask_; }

    void add(Order* o) {
        auto& levels = o->side == Side::Bid ? bids_ : asks_;
        auto& level  = levels[o->price_ticks];
        // Append to FIFO queue
        o->next = nullptr;
        if (level.tail) level.tail->next = o;
        else            level.head = o;
        level.tail = o;
        level.total_qty += o->qty;
        updateBestPrices(o->side, o->price_ticks);
    }

    void cancel(Order* o) {
        auto& level = (o->side == Side::Bid ? bids_ : asks_)[o->price_ticks];
        removeFromLevel(level, o);
        level.total_qty -= o->qty;
        if (level.total_qty == 0)
            reclaimBestPrice(o->side, o->price_ticks);
    }

private:
    void updateBestPrices(Side side, int64_t ticks) {
        if (side == Side::Bid && ticks > best_bid_) best_bid_ = ticks;
        if (side == Side::Ask && ticks < best_ask_) best_ask_ = ticks;
    }

    void reclaimBestPrice(Side side, int64_t ticks) {
        if (side == Side::Bid && ticks == best_bid_) {
            while (best_bid_ >= 0 && bids_[best_bid_].total_qty == 0)
                --best_bid_;
        }
        if (side == Side::Ask && ticks == best_ask_) {
            while (best_ask_ < MAX_PRICE && asks_[best_ask_].total_qty == 0)
                ++best_ask_;
        }
    }

    // Direct-mapped arrays — O(1) access, but large memory footprint
    std::vector<PriceLevel> bids_;
    std::vector<PriceLevel> asks_;
    int64_t best_bid_ = -1;
    int64_t best_ask_ = MAX_PRICE;
};

Trade-off: MAX_PRICE - MIN_PRICE entries allocated upfront. For a stock trading 0–$1000 at $0.01 tick: 100,000 entries × 24 bytes = 2.4MB per side. Fits in L3 cache.

Order ID index — O(1) cancel

Fast cancel requires O(1) lookup from order ID to order pointer:

cpp

Godbolt

#include <unordered_map>

// Or a flat hash map (faster)
class OrderIndex {
public:
    void insert(uint64_t id, Order* o) { index_[id] = o; }

    Order* find(uint64_t id) const {
        auto it = index_.find(id);
        return it != index_.end() ? it->second : nullptr;
    }

    void remove(uint64_t id) { index_.erase(id); }

private:
    // ankerl::unordered_dense or absl::flat_hash_map preferred in prod
    std::unordered_map<uint64_t, Order*> index_;
};

Map-based book for equities (sparse prices)

When the price range is unbounded or very sparse, a sorted map is better:

cpp

Godbolt

#include <map>

class SparseOrderBook {
public:
    // Bids: descending price (highest first)
    // Asks: ascending price (lowest first)
    using BidMap = std::map<double, PriceLevel, std::greater<double>>;
    using AskMap = std::map<double, PriceLevel>;

    double bestBid() const {
        return bids_.empty() ? 0.0 : bids_.begin()->first;
    }
    double bestAsk() const {
        return asks_.empty() ? std::numeric_limits<double>::max()
                              : asks_.begin()->first;
    }

    void add(Order* o) {
        auto& levels = o->side == Side::Bid ? bids_ : asks_;
        auto& level  = levels[o->price];
        appendToLevel(level, o);
    }

    void cancel(Order* o) {
        auto& levels = o->side == Side::Bid ? bids_ : asks_;
        auto it = levels.find(o->price);
        if (it == levels.end()) return;
        removeFromLevel(it->second, o);
        if (it->second.total_qty == 0)
            levels.erase(it);  // clean up empty level
    }

    // Top-of-book snapshot: N levels on each side
    struct Level { double price; uint64_t qty; };
    std::vector<Level> topOfBook(size_t depth) const {
        std::vector<Level> out;
        out.reserve(depth * 2);
        size_t n = 0;
        for (auto& [px, lv] : bids_) {
            out.push_back({px, lv.total_qty});
            if (++n >= depth) break;
        }
        n = 0;
        for (auto& [px, lv] : asks_) {
            out.push_back({px, lv.total_qty});
            if (++n >= depth) break;
        }
        return out;
    }

private:
    BidMap bids_;
    AskMap asks_;
};

Intrusive list for order queues

Standard std::list allocates one node per insertion. Intrusive lists embed the link in the Order itself — zero allocation:

cpp

Godbolt

struct Order {
    uint64_t id;
    double   price;
    uint64_t qty;
    Side     side;
    Order*   prev = nullptr;  // intrusive list links
    Order*   next = nullptr;
};

class IntrList {
public:
    void pushBack(Order* o) {
        o->prev = tail_;
        o->next = nullptr;
        if (tail_) tail_->next = o;
        else       head_ = o;
        tail_ = o;
    }

    void remove(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;
        o->prev = o->next = nullptr;
    }

    Order* front() const { return head_; }

private:
    Order* head_ = nullptr;
    Order* tail_ = nullptr;
};

Market data feed processing

Real-world order book maintains delta updates from exchange feed:

cpp

Godbolt

enum class UpdateType { Add, Cancel, Modify, Execute };

struct MarketDataUpdate {
    UpdateType type;
    uint64_t   order_id;
    double     price;
    uint64_t   qty;
    Side       side;
};

class FeedHandler {
public:
    void onUpdate(const MarketDataUpdate& upd) {
        switch (upd.type) {
        case UpdateType::Add: {
            auto* o = order_pool_.construct(upd.order_id, upd.price, upd.qty, upd.side);
            index_.insert(upd.order_id, o);
            book_.add(o);
            break;
        }
        case UpdateType::Cancel: {
            Order* o = index_.find(upd.order_id);
            if (!o) return;  // unknown order — gap in feed?
            book_.cancel(o);
            index_.remove(upd.order_id);
            order_pool_.destroy(o);
            break;
        }
        case UpdateType::Modify: {
            Order* o = index_.find(upd.order_id);
            if (!o) return;
            book_.cancel(o);
            o->qty = upd.qty;
            book_.add(o);  // re-add at back of queue (qty increase loses priority)
            break;
        }
        case UpdateType::Execute: {
            Order* o = index_.find(upd.order_id);
            if (!o) return;
            o->qty -= upd.qty;
            auto& level = book_.levelAt(o->side, o->price);
            level.total_qty -= upd.qty;
            if (o->qty == 0) {
                book_.cancel(o);
                index_.remove(upd.order_id);
                order_pool_.destroy(o);
            }
            break;
        }
        }
    }

private:
    SparseOrderBook book_;
    OrderIndex index_;
    SlabAllocator<Order, 1 << 20> order_pool_;  // 1M orders pre-allocated
};

Mid-price and spread calculation

cpp

Godbolt

double midPrice(const SparseOrderBook& book) {
    double bid = book.bestBid();
    double ask = book.bestAsk();
    return (bid + ask) / 2.0;
}

double spread(const SparseOrderBook& book) {
    return book.bestAsk() - book.bestBid();
}

// Weighted mid-price (accounts for imbalance)
double weightedMid(const SparseOrderBook& book) {
    auto bids = book.topOfBook(1);
    auto asks = book.topOfBook(1);
    if (bids.empty() || asks.empty()) return midPrice(book);

    double bid_qty = bids[0].qty;
    double ask_qty = bids.size() > 1 ? bids[1].qty : asks[0].qty;
    double total   = bid_qty + ask_qty;
    return (bids[0].price * ask_qty + asks[0].price * bid_qty) / total;
}