构建限价订单簿：C++ 中价格时间优先撮合的实现
限价订单簿是任何电子交易所的核心数据结构。它维护未成交的买卖订单，在价格交叉时撮合。本文逐步构建一个简洁的 C++ 实现，涵盖部分成交、重复拒绝、O(1) 撤单以及微妙的 aggressor 识别问题。
核心规则
每个限价订单簿都遵循价格时间优先：
- 最优价格优先 —— 最高买价始终与最低卖价撮合。
- 同价 FIFO —— 同一价格的订单按到达顺序撮合。
- 触发交易条件
best_bid_price >= best_ask_price。 - 允许部分成交 —— 未成交的数量留在簿中，直到成交或撤单。
Aggressor（主动方） 始终是新来者——被添加的订单”走过订单簿”，吃掉被动挂单。Aggressor 以被动订单的价格成交，而非自己的价格。
数据模型
Order（订单）
using Id = size_t;
using Price = long;
using Quantity = int;
class Order {
public:
Order(Id orderId, Price level, bool isBuy, Quantity quantity)
: orderId_{orderId}, level_{level},
isBuy_{isBuy}, quantity_{quantity},
initialQuantity_{quantity} {}
// 自增优先级，保证同价 FIFO
Id Priority() const { return instance_; }
Id OrderId() const { return orderId_; }
Price Level() const { return level_; }
bool IsBuy() const { return isBuy_; }
Quantity GetRemainingQuantity() const { return quantity_; }
bool IsFilled() const { return quantity_ == 0; }
void Fill(Quantity qty) {
if (qty > quantity_)
throw std::logic_error("Overfill");
quantity_ -= qty;
}
private:
Id orderId_;
Price level_;
bool isBuy_;
Quantity quantity_;
Quantity initialQuantity_;
Id instance_{InstanceId++};
static inline Id InstanceId = 0;
};关键设计：instance_ 字段是一个单调递增计数器，在构造时分配。这赋予每个订单全局唯一的 Priority() 代表到达时间，实现对 aggressor 的确定性识别——当撮合双方在同一微秒内被添加时至关重要。
Trade（成交）
struct Trade {
Id OrderIdA; // 被动（挂单）
Id OrderIdB; // 主动（吃单）
Id AggressorOrderId; // 同 OrderIdB
bool AggressorIsBuy;
Price Level; // 被动订单的价格
Quantity Size;
};
using Trades = std::vector<Trade>;数据结构选择
订单簿需要三种能力：
| 操作 | 要求 | 方案 |
|---|---|---|
| 找到最佳买卖价 | O(1) | std::map 按价格排序 |
| 同价撮合 | FIFO | std::vector<Order> .front() 访问 |
| 按 ID 查找（撤单） | O(1) | std::unordered_map<Id, OrderMetadata> |
class Orderbook {
private:
std::map<Price, std::vector<Order>> bids_; // 降序通过反向迭代
std::map<Price, std::vector<Order>> asks_; // 升序（默认）
std::unordered_map<Id, OrderMetadata> data_; // ID → (价格, 方向)
};为什么用 std::map？ std::map 按键排序，bids_.rbegin() 给出最高买价 O(1)，asks_.begin() 给出最低卖价 O(1)。是的，std::map 插入是 O(log N)——但实际订单簿很少有超过几百个价位，且红黑树的常数因子极好。追求纳秒级撮合可以用自定义数组索引（按 tick 对齐价格）。
为什么用 std::vector 存同价订单？ 订单总是从前端消费（最旧的先成交）、从后端追加（最新的最后）。std::vector 胜在缓存局部性——同价位的所有订单在连续内存中。std::deque 或 std::list 会把它们散落在堆上，损害撮合循环的性能。
为什么要 data_ 查找表？ 没有它，撤单需要遍历每个价位。有了它，O(1) 直接定位。表中存元数据（价格、方向），因为实际的 Order 对象在 bids_ 或 asks_ 的 vector 中。
实现
添加订单
Trades AddOrder(const Order& order) {
// 1. 拒绝重复
if (data_.contains(order.OrderId()))
return {};
// 2. 记入查找表
data_.insert({order.OrderId(), order.ToMetadata()});
// 3. 插入对应价位
if (order.IsBuy())
bids_[order.Level()].push_back(order);
else
asks_[order.Level()].push_back(order);
// 4. 撮合（aggressor 是最后插入的那个）
return Match();
}步骤 3 和 4 有顺序依赖：aggressor 必须在 Match() 运行前已经在簿中，因为 Match() 通过比较 Priority() 判断谁是 aggressor。
撮合
Trades Match() {
Trades trades;
while (true) {
if (bids_.empty() || asks_.empty())
break;
auto& [bidPrice, bidOrders] = *bids_.rbegin(); // 最高买
auto& [askPrice, askOrders] = *asks_.begin(); // 最低卖
if (askPrice > bidPrice) // 无交集——停止
break;
// 此价位内撮合
while (!bidOrders.empty() && !askOrders.empty()) {
auto& bid = bidOrders.front();
auto& ask = askOrders.front();
Quantity matchQty = std::min(
bid.GetRemainingQuantity(),
ask.GetRemainingQuantity()
);
bid.Fill(matchQty);
ask.Fill(matchQty);
// 判断 aggressor：后到达的
bool bidIsAggressor = bid.Priority() > ask.Priority();
trades.push_back({
bid.OrderId(),
ask.OrderId(),
bidIsAggressor ? bid.OrderId() : ask.OrderId(),
bidIsAggressor,
askPrice, // 以被动方价格成交
matchQty,
});
if (bid.IsFilled()) {
bidOrders.erase(bidOrders.begin());
data_.erase(bid.OrderId());
}
if (ask.IsFilled()) {
askOrders.erase(askOrders.begin());
data_.erase(ask.OrderId());
}
}
// 清理空的价位
if (bidOrders.empty()) bids_.erase(bidPrice);
if (askOrders.empty()) asks_.erase(askPrice);
}
return trades;
}Aggressor 识别问题 是最微妙的部分。考虑这个场景：
时间 0: AddOrder(买 @100, qty=10) → 加入 bids
时间 0: AddOrder(卖 @99, qty=5) → 撮合！谁是 aggressor？卖单——它穿过价差吃掉了被动买单。但两者在同一调用链中被添加（AddOrder → Match）。没有显式优先级追踪，就需要通过调用栈传递 aggressor ID。Priority() 计数器优雅地解决了这个问题：instance 号更大的就是 aggressor。
撤单
void CancelOrder(Id orderId) {
if (!data_.contains(orderId))
return;
const auto& meta = data_.at(orderId);
auto& levels = meta.IsBuy ? bids_ : asks_;
auto it = levels.find(meta.Level);
if (it == levels.end()) return;
auto& orders = it->second;
orders.erase(
std::remove_if(orders.begin(), orders.end(),
[&](const Order& o) { return o.OrderId() == orderId; }
),
orders.end()
);
if (orders.empty())
levels.erase(it);
data_.erase(orderId);
}std::remove_if + erase 是标准的 erase-remove 惯用法。对 vector 这是 O(N) 在该价位订单数上的操作——通常很小，没问题。如果撤单吞吐量需要更高，可以用 std::list 或侵入式链表实现 O(1) 删除。
边界情况
| 场景 | 行为 |
|---|---|
| 单个订单，无撮合 | 静默插入，返回空 Trades |
| 价格不交叉 | 买 @99，卖 @100 → 不成交，两者都在 |
| 部分成交 | 买 100 @50，卖 70 @50 → 成交 70，买剩 30 |
| 重复订单 ID | 第二次 AddOrder 同 ID → 静默拒绝 |
| 撤不在的 ID | 无操作，无报错 |
| 撤部分成交的 | 剩余数量移除，不产生成交 |
| 多价位穿透 | Aggressor 扫过多个价位 → 多笔成交 |
vector vs list 的取舍
常见的面试追问：同一价位内的订单为什么用 std::vector 而不是 std::list？
| 属性 | std::vector | std::list |
|---|---|---|
| 缓存局部性 | ✅ 连续内存 | ❌ 散落堆上 |
| 前端访问 | ✅ O(1) | ✅ O(1) |
| 前端删除 | ❌ O(N) 移动 | ✅ O(1) |
| 追加 | ✅ O(1) 均摊 | ✅ O(1) |
| 内存开销 | ✅ 最小（仅数据） | ❌ 每节点两个指针 |
| 遍历 | ✅ 快，可预取 | ❌ 指针追逐 |
对撮合引擎，主导操作是从前端消费订单——std::vector 的 O(N) 移动在删除时支付。实际上，典型价位深度 10-100 个订单，移动成本远小于迭代时的缓存收益。极端深度（一个价位上千个订单）可以选 std::deque 或 boost::container::devector。
核心要点
std::map+std::vector是务实的选择——对 99% 的限价订单簿实现足够好- 优先级计数器 解决了 aggressor 识别问题，无需在线程调用栈中传递元数据
- 撮合必须在插入之前 处理 aggressor 的剩余数量——进来的订单走过订单簿，先吃掉被动流动性
- erase-remove 惯用法 在实际深度下撤单性能足够；仅在 profiling 显示瓶颈时优化
- 缓存局部性 在热撮合循环中比渐进复杂度更重要
理解限价订单簿内部机制是每个量化开发面试的基本功。同样的原则——价格时间优先、部分成交、aggressor 识别——适用于股票、期货、加密货币的撮合引擎开发。