Building a Limit Order Book Engine in C++

Every time you place a trade on a stock exchange, something has to decide whether your order matches with someone else's, at what price, and in what order. That something is a Limit Order Book (LOB) matching engine and I built one from scratch in C++.

The result: 96.62 ns/order average latency and 10.35 million operations per second.

What Even Is a Limit Order Book?

An order book is a real-time record of all buy and sell interest for a given asset. Buyers place bids ("I want to buy 100 shares at $50"), sellers place asks ("I'll sell 100 shares at $51"). When a bid price meets or exceeds an ask price, a trade happens.

The key rules are:

• Price priority: Better prices match first (highest bid, lowest ask)
• Time priority: At the same price, earlier orders match first (FIFO)

This is called price-time priority, and it's the standard used on most exchanges worldwide.

The Data Structure Problem

The engineering challenge is building a structure that's fast at everything

• Insert a new order → fast
• Find the best bid/ask → fast
• Match orders across price levels → fast
• Cancel an order by ID → fast

That last one is the tricky part. Naively, cancellation means searching through all your orders to find the one you want which takes O(n) time or proportionately as long as the number of orders. In a book with hundreds of thousands of resting orders, that does not pass at all.

Here's the three-layer architecture I landed on:

The design above forms the base of implementing the OrderBook class.

class OrderBook
{
public:
    vector<Trade> addOrder(Order order);
    bool cancelOrder(uint64_t orderId);

    uint64_t getBestBid() const;
    uint64_t getBestAsk() const;

private:
    using OrderList = list<Order>;
    using OrderIterator = OrderList::iterator;

    map<uint64_t, OrderList, greater<uint64_t>> bids_; // highest first
    map<uint64_t, OrderList, less<uint64_t>>    asks_; // lowest first

    unordered_map<uint64_t, OrderIterator> orderMap_;

    vector<Trade> matchOrder(Order &order);
};

The bids_ map uses greater<uint64_t> as the comparator so bids_.begin() always gives you the highest bid i.e. the best price, in constant time. Same idea for asks with less<uint64_t>.

The Quick Cancellation Trick

Drawing from my solution to Leetcode 146 LRU Cache, the orderMap_ stores not just a pointer to the order, but a list::iterator directly into the std::list at the right price level. Since std::list guarantees iterator stability (iterators are never invalidated by insertions or other erasures), this iterator remains valid indefinitely.

Cancelling an order then becomes:

bool OrderBook::cancelOrder(uint64_t orderId)
{
    auto mapIt = orderMap_.find(orderId); // O(1) hash map lookup
    if (mapIt == orderMap_.end())
        return false;

    OrderIterator listIt = mapIt->second;
    uint64_t price = listIt->price;
    Side side = listIt->side;

    if (side == Side::BUY)
    {
        bids_[price].erase(listIt); // O(1) list erase via iterator
        if (bids_[price].empty())
            bids_.erase(price);
    }
    else
    {
        asks_[price].erase(listIt); // O(1) list erase via iterator
        if (asks_[price].empty())
            asks_.erase(price);
    }

    orderMap_.erase(mapIt);
    return true;
}

One hash map lookup + one list erase gets the job done in constant time. No searching is involved as we just store the iterator and let the list do the work.

The Matching Loop

When a new order arrives, it first tries to match against resting orders on the opposite side. For a buy order, we walk through asks from lowest to highest price, filling until the order is satisfied or no more matches exist:

vector<Trade> OrderBook::matchOrder(Order &order)
{
    vector<Trade> trades;

    if (order.side == Side::BUY)
    {
        auto it = asks_.begin(); // start at best ask (lowest price)
        while (it != asks_.end() && order.quantity > 0 &&
               (order.type == OrderType::MARKET || order.price >= it->first))
        {
            OrderList &level = it->second;
            auto orderIt = level.begin(); // FIFO: front of queue first

            while (orderIt != level.end() && order.quantity > 0)
            {
                uint64_t matchedQty = min(order.quantity, orderIt->quantity);
                trades.push_back({orderIt->id, order.id, it->first, matchedQty});

                order.quantity -= matchedQty;
                orderIt->quantity -= matchedQty;

                if (orderIt->quantity == 0)
                {
                    orderMap_.erase(orderIt->id);
                    orderIt = level.erase(orderIt);
                }
            }

            if (level.empty())
                it = asks_.erase(it);
            else
                ++it;
        }
    }
    // ... mirror logic for SELL orders
    return trades;
}

After matching, any remaining quantity (for limit orders) gets added to the book as a resting order, with its iterator stored in orderMap_ for future cancellation.

The Order Model

The data types are intentionally minimal with no dynamic allocation, no virtual dispatch, just plain structs:

enum class Side      { BUY, SELL };
enum class OrderType { LIMIT, MARKET };

struct Order {
    uint64_t  id;
    Side      side;
    OrderType type;
    uint64_t  price;
    uint64_t  quantity;
};

struct Trade {
    uint64_t maker_order_id;
    uint64_t taker_order_id;
    uint64_t price;
    uint64_t quantity;
};

Keeping structs small matters at this scale. When you're processing 10 million orders per second, cache line pressure is real.

Performance

Benchmarked on local hardware with 1,000,000 orders after warm-up, compiled with -O3:

Sub-100 nanoseconds per order. For context, a single cache miss costs ~100 ns. The design keeps hot data (best bid/ask at map::begin(), order lookup via hash map) as cache-friendly as possible.

The trade-off I accepted was O(log n) price level insertion in std::map. A production exchange might use a custom flat array indexed by price (a "price ladder") to get O(1) here too. But for the scope of this project, the clean sorted-map was worth it.

CI, Testing, and Memory Safety

In order to ensure performance standards, every push to main triggers:

• Google Test unit suite covering FIFO ordering, partial fills, edge cases, and 10,000+ order stress tests
• Valgrind memory leak checks
• AddressSanitizer in debug builds
• Docker containerisation for reproducible benchmarks

Running the full suite locally:

mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build . -j$(nproc)
ctest --output-on-failure
./benchmarks/run_benchmarks

What I Learned

The most valuable insight from this project was that sometimes solutions are just around us and we have to look closer to find them. Sure, a naive implementation of order cancellations would run in linear time but drawing inspiration from my solution to another problem, I was able to optimize the implementation to achieve constant time.

This also reinforced how much the C++ standard library gives you when you use it correctly. std::list iterator stability, std::map's automatic sort order, std::unordered_map's O(1) average lookup - none of these required me to write a single custom data structure.

The full source is on GitHub. If you're thinking about systems programming, building a matching engine is one of the best exercises to learn or apply the skill as it touches on data structures, performance engineering, and real-world domain logic all at once.

P.S. I am currently working on a project that uses this matching engine as a service, but that story is for a separate post :p