订单簿重建
Full Order Book Reconstruct
题目详情
从交易流（增量更新）中重建完整订单簿是交易所核心基础设施的一部分。必须处理新增、修改和取消订单，以及网络丢包导致的序列号跳变。
任务：实现一个订单簿重建器，从增量更新流中维护完整的买卖盘深度。
英文原题
In modern electronic trading, market data feeds broadcast via UDP often result in out-of-order or dropped packets. A robust trading system must reconstruct the limit order book by processing messages in their exact sequence and buffering out-of-order messages to maintain an accurate view of market liquidity.
Task
Implement a class OrderBookReconstructor that processes a stream of market data messages and responds to queries about the current state of the order book.
The class must implement tw
解析
问题分析
从交易流重建完整订单簿需要处理增量更新（增/删/改）、丢包检测和乱序到达。订单簿通过维护双向链表（按价格排序）和哈希表（按订单 ID 查找）实现 O(log N) 的更新和 O(1) 的查找。
实现
class OrderBook {
struct Level { double price; int volume; int orders; };
std::map<double, Level, std::greater<>> bids_;
std::map<double, Level> asks_;
std::unordered_map<uint64_t, std::pair<double, int>> orders_; // id->{price, vol}
uint32_t last_seq_ = 0;
public:
enum Side { BUY, SELL };
bool apply(uint32_t seq, Side side, double price, int volume, uint64_t orderId) {
if (seq <= last_seq_) return false; // 忽略重复或乱序
last_seq_ = seq;
auto& book = (side == BUY) ? bids_ : asks_;
if (volume == 0) book[price].volume -= orders_[orderId].second;
else { book[price].volume += volume; book[price].orders++; }
orders_[orderId] = {price, volume};
if (book[price].volume <= 0) book.erase(price);
return true;
}
};复杂度与边界
- 时间复杂度：单次更新 O(log N)，N 为价格档位数
- 空间复杂度：O(N + M)，N 档位 + M 活跃订单
- 边界条件：(1) 序列号跳变(丢包)时触发全量重建 (2) volume=0 表示订单取消 (3) 负价格或零价格应拒绝 (4) 同一 orderId 重复出现时以最新为准
英文解析
Analysis
Reconstructing a full order book from trade streams requires handling incremental updates (add/delete/modify), packet loss detection, and out-of-order arrival. The order book uses a bidirectional sorted linked list (by price) and a hash table (by order ID) to achieve O(log N) updates and O(1) lookups.
Solution
class OrderBook {
struct Level { double price; int volume; int orders; };
std::map<double, Level, std::greater<>> bids_;
std::map<double, Level> asks_;
std::unordered_map<uint64_t, std::pair<double, int>> orders_; // id->{price, vol}
uint32_t last_seq_ = 0;
public:
enum Side { BUY, SELL };
bool apply(uint32_t seq, Side side, double price, int volume, uint64_t orderId) {
if (seq <= last_seq_) return false; // ignore duplicate or out-of-order
last_seq_ = seq;
auto& book = (side == BUY) ? bids_ : asks_;
if (volume == 0) book[price].volume -= orders_[orderId].second;
else { book[price].volume += volume; book[price].orders++; }
orders_[orderId] = {price, volume};
if (book[price].volume <= 0) book.erase(price);
return true;
}
};Complexity & Edge Cases
- Time complexity: Single update O(log N), where N is the number of price levels
- Space complexity: O(N + M), N price levels + M active orders
- Edge cases: (1) Sequence number gap (packet loss) triggers full reconstruction (2) volume=0 indicates order cancellation (3) negative or zero prices should be rejected (4) Duplicate orderId uses the latest update
Key Considerations
- Incremental vs snapshot: Real systems blend both — periodic snapshots plus incremental deltas; handle gaps by requesting full refresh
- Sequence numbers: Each update carries a monotonically increasing sequence; missing sequences indicate data loss requiring reconnection
- Side aggregation: Book must aggregate orders at same price level by side; crossing orders should trigger match logic, not appear in book
- Memory limits: Deep books with thousands of levels need bounded-depth storage; drop levels beyond configured maximum