1 Oct 2026

Order Matching Engine Part 2 - Data Structures

Order Matching EngineData StructuresC++

In my previous post I gave an overview of my Order Matching Engine and the two matching strategies it supports: price-time priority and top/priority pro-rata. In this post I'll go into the technical details of the implementation; specifically, the data structures holding the orders and how they evolved (bugs included).

Data Structures

Goal & Approaches

The goal of the strategies is to match orders in a specific way. For Price-Time Priority, it is to match the orders at the best available price and time. This means that the orders need to be sorted by price first and time second. As I mentioned in my previous post, std::priority_queue immediately comes to mind, but on my second commit, my implementation involved simple maps:

std::map<double, std::deque<Order>> buyOrders;
std::map<double, std::deque<Order>> sellOrders;

This way, I was able to simply use push_back() and move on with my testing and strategy implementation. After that, I added a structure to hold all orders for lookup:

map<string, Order> allOrders;

And then I immediately reconsidered my choice for the map's value type and used pointers for all structures:

map<string, map<double, deque<Order*>>> buyOrders;
map<string, map<double, deque<Order*>>> sellOrders;
map<string, Order*> allOrders;

The enclosing map<string, ...>'s were used to map all securities to their orders, something I fixed way later by having a single book per security.

After that, I created buckets that (finally) used std::priority_queue:

class CompareBuy {
public:
  bool operator() (Order* o1, Order* o2) {
    return (o1->price > o2->price) ? o1 : o2;
  }
};
class CompareSell {
public:
  bool operator() (Order* o1, Order* o2) {
    return (o1->price > o2->price) ? o1 : o2;
  }
};
 
class BuyBucket {
public:
  priority_queue<Order*, deque<Order*>, CompareBuy> bucket;
  double total_quantity = 0;
};
 
class SellBucket {
public:
  priority_queue<Order*, deque<Order*>, CompareSell> bucket;
  double total_quantity = 0;
};
 
map<string, map<double, BuyBucket*>> buyOrders;
map<string, map<double, SellBucket*>> sellOrders;

If you pay attention (unlike me at the time), you'll notice three bugs:

The CompareBuy/CompareSell comparators return orders instead of bool.
They both use the same symbol >, which means copy-paste claimed yet another victim.
The timestamp is not used as a tie-breaker in case the price between two orders is the same.

Eventually I fixed the first two, on the same day I tried to fix a double precision error and was reminded why everyone hates floating point arithmetic. Overall, a great day for debugging. The last bug was fixed later.

Current Approach

After a while, I realized I wanted to implement a Cancel Order functionality, which is hard to do using a priority_queue, so I decided to let AI have a go at it and ultimately refactored my bucket implementation:

struct BuyEntry {
	double   price;
	int64_t  timestamp;
	std::string id;
 
	bool operator<(const BuyEntry& o) const {
		if (price     != o.price)     return price > o.price;         // higher price first
		if (timestamp != o.timestamp) return timestamp < o.timestamp; // earlier first
		return id < o.id;
	}
};
 
struct SellEntry {
	double   price;
	int64_t  timestamp;
	std::string id;
 
	bool operator<(const SellEntry& o) const {
		if (price     != o.price)     return price < o.price;         // lower price first
		if (timestamp != o.timestamp) return timestamp < o.timestamp; // earlier first
		return id < o.id;
	}
};
 
template<typename Entry>
struct Bucket {
	std::set<Entry> queue;
	std::unordered_map<std::string, typename std::set<Entry>::iterator> index;
	double total_quantity = 0;
 
	void push(const Entry& e) {
		auto [it, ok] = queue.insert(e);
		if (ok) index.emplace(e.id, it);
	}
 
	void erase(const std::string& id) {
		auto it = index.find(id);
		if (it != index.end()) {
			queue.erase(it->second);
			index.erase(it);
		}
	}
 
	void popTop() {
		auto top = queue.begin();
		index.erase(top->id);
		queue.erase(top);
	}
 
	bool empty() const { return queue.empty(); }
	const Entry& top() const { return *queue.begin(); }
};
 
using BuyBucket  = Bucket<BuyEntry>;
using SellBucket = Bucket<SellEntry>;

First of all, it defines two structs, BuyEntry and SellEntry. These structs hold the information that is necessary to have the orders sorted: the price, the timestamp and the id, which you compare in that order using an overload for the operator <.

After that, a generic template Bucket is introduced using an Entry typename. This bucket will have three fields: the queue that contains all entries, the index that maps ids to the entries and the total_quantity that holds the total quantity of all orders in that bucket (which I wanted to use for the pro-rata algorithm, but I ultimately removed - I'm keeping it in the explanation as it is part of my commits history). Unlike before, a bucket no longer contains a tick-sized price range; instead, each book has one BuyBucket and one SellBucket, which hold the entire buy and sell side respectively.

Bucket also contains five methods: push(), erase(), popTop(), empty() and top(), which are pretty self-explanatory. Due to the need to implement these methods, the following types were chosen for each field (n being the number of resting orders in the bucket):

queue -> std::set: so insertion is O(log n) and deletion is amortized O(1) when given an iterator
index -> std::unordered_map<std::string, typename std::set<Entry>::iterator>: this maps an id to the entry in the set and has insertion, deletion and lookup of average Θ(1) and worst O(n)
total_quantity -> double: same as all prices

Due to the above, this leads to the methods implemented being:

push(): average Θ(log n) due to the set insertion, worst O(n) due to the map insertion
erase(): average, amortized Θ(1) since index gives us the set iterator and erasing by iterator is amortized constant, worst O(n) due to the map lookup and deletion
popTop(): average, amortized Θ(1) since set lookup and deletion is on the first element and map deletion is also Θ(1); map deletion also means that the worst case is O(n)
empty(): O(1) since it checks if the set is empty
top(): O(1) since it retrieves the first element

After all of the above, it defines BuyBucket and SellBucket by using the Bucket template and the BuyEntry and SellEntry structs defined in the beginning.

With the above, we end up with buckets that have an average Θ(log n) for insertion, and an average Θ(1) for the rest of the methods. Given that we need the entries to remain sorted so that we can access the best available prices, I would say this is a good result. At some point I may try to optimize this further, but right now I think the implementation won't hinder us performance-wise - of course, that remains to be seen in the next blog posts.