What is an efficient data structure to model order book of prices and quantities to ensure:
- constant look up
- iteration in order of prices
- retrieving best bid and ask in constant time
- fast quantity updates
I do not know in which context you want to implement a matching engine (ME). But according to me the two nice challenges in this context are:
The last point is about simulating one day in few seconds.
To answer more directly your question, the reference is Josh Levine's code of Island in foxpro. Levin's has been one of the pioneer in the raise of electronic trading. It is not only an executable spec, but a piece of history.
If you assume that most updates will happen near the top of the book (a fair assumption) a linked-list ordered by price levels will be very efficient.
You can check CoralMD for an example of a very fast, garbage-free market data book implementation that provides not just the global view of the market (all exchanges) but also a per-exchange book view. It also provides the infra-structure to write exchange feeds and to distribute market data internally.
Disclaimer: I am one of the developers of CoralMD
Since Quant Cup 1's objective was an efficient price/time matching engine, the data structure of the winning implementation might partly be what you are looking for.
Else the setup of LOBSTER is supposed to be quick.