构建限价订单簿：C++ 中价格时间优先撮合的实现

限价订单簿是任何电子交易所的核心数据结构。它维护未成交的买卖订单，在价格交叉时撮合。本文逐步构建一个简洁的 C++ 实现，涵盖部分成交、重复拒绝、O(1) 撤单以及微妙的 aggressor 识别问题。

---

核心规则

每个限价订单簿都遵循价格时间优先：

1. 最优价格优先 —— 最高买价始终与最低卖价撮合。
2. 同价 FIFO —— 同一价格的订单按到达顺序撮合。
3. 触发交易条件 best_bid_price >= best_ask_price。
4. 允许部分成交 —— 未成交的数量留在簿中，直到成交或撤单。

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。

---

核心要点

1. std::map + std::vector 是务实的选择——对 99% 的限价订单簿实现足够好
2. 优先级计数器 解决了 aggressor 识别问题，无需在线程调用栈中传递元数据
3. 撮合必须在插入之前 处理 aggressor 的剩余数量——进来的订单走过订单簿，先吃掉被动流动性
4. erase-remove 惯用法 在实际深度下撤单性能足够；仅在 profiling 显示瓶颈时优化
5. 缓存局部性 在热撮合循环中比渐进复杂度更重要

理解限价订单簿内部机制是每个量化开发面试的基本功。同样的原则——价格时间优先、部分成交、aggressor 识别——适用于股票、期货、加密货币的撮合引擎开发。