C++ 高性能订单簿（Order Book）核心实现与优化

需要特别注意的是 RemoveOrder 中的指针操作顺序。 这四个 if 语句必须覆盖所有情况：节点既是 head 又是 tail、节点是 head 但不是 tail、节点是 tail 但不是 head、以及节点在中间。如果写成 if-else 的形式会遗漏同时是 head 和 tail 的情况，导致悬空指针。

2.3 内存分配器

在高频交易场景中，new 和 delete 的开销是不可接受的。每笔订单的生命周期很短，如果每次都走系统分配器，频繁的内存分配和释放会造成严重的延迟抖动。

解决方案是使用内存池：预先分配一大块内存，将其切分为等大的 Order 槽位，用空闲链表串联起来。分配时从链表头部取一个，释放时归还到链表头部，都是 O(1) 操作。

struct Allocator {
private:
    std::vector<Order *> pools_;
    Order *free_head_ = nullptr;
    size_t chunksize_ = 16;

    void Extend() {
        free_head_ = static_cast<Order *>(::operator new(chunksize_ * sizeof(Order)));
        pools_.push_back(free_head_);
        for (size_t i = 0; i < chunksize_; i++) {
            free_head_[i].next_ = i + 1 < chunksize_ ? &free_head_[i + 1] : nullptr;
        }
        chunksize_ = std::min(chunksize_ * 2, static_cast<size_t>(1 << 20));
    }

public:
    Allocator() { Extend(); }
    ~Allocator() {
        for (Order *p : pools_) {
            ::operator delete(p);
        }
    }

    Order *Allocate() {
        if (!free_head_) Extend();
        Order *order = free_head_;
        free_head_ = free_head_->next_;
        return order;
    }

    void Deallocate(Order *order) {
        order->next_ = free_head_;
        free_head_ = order;
    }
};

这里有两个容易忽视的问题。第一，chunksize_ 的翻倍增长如果不设上限，经过足够多次扩展后会溢出到零。第二，空闲链表复用了 Order::next_ 指针来串联空闲节点。这意味着被归还到空闲链表的 Order 对象中 next_ 已被覆写，如果此后还有代码试图通过这个指针遍历，读到的将是空闲链表中其他节点的地址。

关于分配器的归属问题： 分配器应该由 OrderBook 持有，而不是作为全局变量。全局分配器在多线程环境下会成为串行化瓶颈。而每个 OrderBook 持有自己的分配器，则天然没有竞争。此外，生命周期管理变得极为简单，且同一个订单簿的订单从同一块连续内存中分配，对 CPU 缓存更加友好。

2.4 订单簿

买方簿使用 std::map<int, Level, std::greater<>> 存储，键是价格，值是对应的价格档位。std::greater 使得迭代器按价格从高到低排列，这样 begin() 就是最优买价。卖方簿使用默认的 std::map<int, Level>，begin() 是最优卖价。

除了两棵价格树之外，还需要一个哈希表将 Order ID 映射到 Order 指针，用于 O(1) 地定位某笔订单以支持取消和修改操作。

class OrderBook {
    Allocator allocator_;
    std::map<int, Level, std::greater<>> buy_book_;
    std::map<int, Level> sell_book_;
    std::unordered_map<uint64_t, Order *> order_map_;
    // ... 后续展开
};

三、撮合逻辑

撮合是订单簿最核心也最容易出错的部分。当一笔买单进入时，它尝试与卖方簿匹配；当一笔卖单进入时，它尝试与买方簿匹配。由于两棵树的排列方向不同，但匹配逻辑完全对称，我们用模板化的 MatchOrder 方法统一处理。

3.1 成交回报

在展示匹配代码之前，先定义成交回报结构。每发生一笔成交，系统需要知道被动方订单 ID、主动方订单 ID、成交价格和成交数量。在生产系统中，通常使用回调而不是返回 std::vector<Fill>，因为回调可以完全内联，避免了每次撮合都分配一个向量的开销。

struct Fill {
    uint64_t passive_order_id;      // 被动方（簿上已有的订单）
    uint64_t aggressive_order_id;   // 主动方（新进入的订单）
    int price;
    uint32_t quantity;
    Side aggressive_side;
};

回调通过模板参数传入，编译器会将其完全内联。不需要成交信息时传入空 lambda，编译器会将其优化为零开销。

3.2 匹配实现

template<typename OnFill>
uint32_t MatchOrder(Order order, auto& book, OnFill &&on_fill) {
    uint32_t matched_quantity = 0;
    uint32_t remaining_quantity = order.quantity_;

    for (auto it = book.begin(); it != book.end();) {
        // 价格不满足条件，停止匹配
        if (order.side_ == Side::BUY && order.price_ < it->first) break;
        if (order.side_ == Side::SELL && order.price_ > it->first) break;
        if (remaining_quantity == 0) break;

        auto& level = it->second;
        if (remaining_quantity >= level.total_quantity_) {
            // 主动方数量足以吃掉整个档位
            Order *cur = level.head_;
            while (cur) {
                on_fill(Fill{cur->order_id_, order.order_id_, it->first, cur->quantity_, order.side_});
                matched_quantity += cur->quantity_;
                remaining_quantity -= cur->quantity_;
                order_map_.erase(cur->order_id_);
                Order *next = cur->next_;
                level.RemoveOrder(allocator_, cur);
                cur = next;
            }
            // 整个档位已清空，从树中移除
            it = book.erase(it);
        } else {
            // 主动方数量不足以吃掉整个档位，从尾部（最老的订单）开始消耗
            Order *cur = level.tail_;
            while (remaining_quantity > 0) {
                if (remaining_quantity >= cur->quantity_) {
                    on_fill(Fill{cur->order_id_, order.order_id_, it->first, cur->quantity_, order.side_});
                    matched_quantity += cur->quantity_;
                    remaining_quantity -= cur->quantity_;
                    order_map_.erase(cur->order_id_);
                    Order *prev = cur->prev_;
                    level.RemoveOrder(allocator_, cur);
                    cur = prev;
                } else {
                    // 部分成交：被动方订单还有剩余
                    on_fill(Fill{cur->order_id_, order.order_id_, it->first, remaining_quantity, order.side_});
                    cur->quantity_ -= remaining_quantity;
                    level.total_quantity_ -= remaining_quantity;
                    matched_quantity += remaining_quantity;
                    remaining_quantity = 0;
                }
            }
            ++it;
        }
    }

    // 未成交的部分挂入订单簿
    if (remaining_quantity > 0) {
        Order *new_order = nullptr;
        if (order.side_ == Side::BUY) {
            new_order = buy_book_[order.price_].AddOrder(allocator_, Side::BUY, order.order_id_, order.price_, remaining_quantity);
        } else {
            new_order = sell_book_[order.price_].AddOrder(allocator_, Side::SELL, order.order_id_, order.price_, remaining_quantity);
        }
        order_map_[order.order_id_] = new_order;
    }
    return matched_quantity;
}

注意这里消耗整个档位时从 head 开始遍历，而部分消耗时从 tail 开始。 看起来矛盾，实则一致：两种情况下最老的订单（tail 端）都优先被成交。整个档位被吃掉时从 head 遍历只是为了方便逐个清理，反正所有订单都会被移除，顺序无所谓。但部分消耗时必须从 tail 开始，这是 FIFO 的核心保证。

还有一个容易被忽视的点： RemoveOrder 中调用了 Deallocate，这意味着 cur 指向的内存已经被归还。因此在遍历中必须先保存 cur->next_（或 cur->prev_），然后再调用 RemoveOrder。如果颠倒顺序，就是经典的 use-after-free。

四、订单操作

4.1 添加订单

添加订单是撮合引擎的入口。它首先检查 Order ID 是否重复——重复 ID 会导致哈希表中旧映射被覆盖，使旧订单变成「幽灵订单」，永远无法被取消或修改，其数量永久污染 total_quantity_。

template<typename OnFill = void(*)(const Fill &)>
uint32_t AddOrder(Order order, OnFill &&on_fill = [](const Fill &){}) {
    if (order_map_.contains(order.order_id_)) return 0;
    if (order.side_ == Side::BUY) {
        return MatchOrderAgainstSell(order, std::forward<OnFill>(on_fill));
    } else {
        return MatchOrderAgainstBuy(order, std::forward<OnFill>(on_fill));
    }
}

4.2 取消订单

取消订单需要通过 order_map_ 找到订单指针，从链表中移除，更新档位总数量，如果档位变空则从树中移除。

bool CancelOrder(uint64_t order_id) {
    auto it = order_map_.find(order_id);
    if (it == order_map_.end()) return false;
    Order *order = it->second;

    // 在 RemoveOrder 释放内存之前保存必要的字段
    Side side = order->side_;
    int price = order->price_;

    // 使用 find 而不是 operator[] 防止意外创建空档位
    auto& book = side == Side::BUY ? buy_book_ : sell_book_;
    auto level_it = book.find(price);
    assert(level_it != book.end());
    auto& level = level_it->second;

    level.RemoveOrder(allocator_, order);
    // order 指针此后不可再访问

    // 档位清空则移除，防止空档位污染 Best Bid/Ask 查询
    if (level.total_quantity_ == 0) {
        book.erase(level_it);
    }
    order_map_.erase(it);
    return true;
}

这段代码中有一个微妙但关键的细节： side 和 price 必须在调用 RemoveOrder 之前保存。因为 RemoveOrder 会将 order 指向的内存归还到空闲链表，此后 order->side_ 和 order->price_ 的内容已经不可靠。这是一种容易在代码审查中被遗漏的 use-after-free。

另一个要点是空档位的清理。如果取消订单后档位的 total_quantity_ 变为零却不从树中移除，那么查询会返回这个空档位的价格和零数量，导致错误的市场数据。

4.3 修改订单

修改订单的语义取决于新数量与原数量的关系。如果新数量更小（减量修改），订单保持在链表中的原位置，因为减量不应该丧失时间优先权。如果新数量更大（增量修改），订单会失去时间优先权——需要将旧订单移除并重新插入到链表头部。

bool ModifyOrder(uint64_t order_id, uint32_t new_quantity) {
    auto it = order_map_.find(order_id);
    if (it == order_map_.end()) return false;
    if (new_quantity == 0) return CancelOrder(order_id);

    Order *order = it->second;
    Side side = order->side_;
    int price = order->price_;
    auto& book = side == Side::BUY ? buy_book_ : sell_book_;
    auto level_it = book.find(price);
    assert(level_it != book.end());
    auto& level = level_it->second;

    if (new_quantity <= order->quantity_) {
        // 减量：保持位置不变，只更新数量
        // 注意：必须先更新 total_quantity_，再更新 order->quantity_
        level.total_quantity_ -= order->quantity_ - new_quantity;
        order->quantity_ = new_quantity;
    } else {
        // 增量：失去时间优先权，移除后重新插入到头部
        order_map_[order_id] = level.AddOrder(allocator_, side, order->order_id_, price, new_quantity);
        level.RemoveOrder(allocator_, order);
    }
    return true;
}

减量修改中两行代码的顺序至关重要。 考虑以下错误写法：先把 order->quantity_ 改成 new_quantity，然后计算 order->quantity_ - new_quantity，得到的永远是零。total_quantity_ 永远不会减少，导致后续所有依赖 total_quantity_ 的逻辑全部出错。这类 Bug 不会导致崩溃，只会产生错误的结果，非常难以发现。

还要注意 new_quantity == 0 的情况必须委托给 CancelOrder 处理，因为 CancelOrder 会在档位清空时将其从树中移除。如果只做 RemoveOrder 而不清理空档位，会留下幽灵档位。

五、市场数据查询

5.1 最优价与价差

std::optional<std::pair<int, uint32_t>> GetBestBid() const {
    if (buy_book_.empty()) return std::nullopt;
    auto it = buy_book_.begin();
    return std::make_pair(it->first, it->second.total_quantity_);
}

std::optional<std::pair<int, uint32_t>> GetBestAsk() const {
    if (sell_book_.empty()) return std::nullopt;
    auto it = sell_book_.begin();
    return std::make_pair(it->first, it->second.total_quantity_);
}

std::optional<double> GetMid() const {
    if (buy_book_.empty() || sell_book_.empty()) return std::nullopt;
    return (buy_book_.begin()->first + sell_book_.begin()->first) / 2.0;
}

std::optional<int> GetSpread() const {
    if (buy_book_.empty() || sell_book_.empty()) return std::nullopt;
    return sell_book_.begin()->first - buy_book_.begin()->first;
}

使用 std::optional 处理空簿的情况而不是 assert，因为在正常运行中簿被完全清空是完全合法的场景。

5.2 成交量加权平均价格（VWAP）

VWAP 回答的问题是："如果我要买入/卖出 N 手，平均成交价是多少？"它从最优价开始逐层消耗，加权计算平均价格。

std::pair<double, uint32_t> GetVWAP(uint32_t target_quantity, const auto& book) const {
    if (book.empty() || target_quantity == 0) return {0.0, 0};
    double sum = 0.0;
    uint32_t filled = 0;
    for (auto it = book.begin(); it != book.end() && target_quantity > 0; ++it) {
        auto& level = it->second;
        if (target_quantity >= level.total_quantity_) {
            filled += level.total_quantity_;
            sum += static_cast<double>(it->first) * level.total_quantity_;
            target_quantity -= level.total_quantity_;
        } else {
            filled += target_quantity;
            sum += static_cast<double>(it->first) * target_quantity;
            target_quantity = 0;
        }
    }
    return {sum / filled, filled};
}

注意 target_quantity == 0 的保护。如果没有这个检查，空簿的 guard 通过了但 target_quantity 为零，循环体不执行，filled 为零，最终 sum / filled 产生 NaN。

5.3 获取指定深度的档位

const Level &GetLevel(Side side, int depth) const {
    assert(depth >= 0);
    if (side == Side::BUY) {
        assert(depth < static_cast<int>(buy_book_.size()));
        auto it = buy_book_.begin();
        std::advance(it, depth);
        return it->second;
    } else {
        assert(depth < static_cast<int>(sell_book_.size()));
        auto it = sell_book_.begin();
        std::advance(it, depth);
        return it->second;
    }
}

这个操作的时间复杂度是 O(depth)，因为 std::map 的迭代器不支持随机访问。对于需要频繁查询多层深度的场景，这可能成为瓶颈。

六、完整代码

整合后的完整实现如下：

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <map>
#include <new>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>

enum class Side {
    BUY,
    SELL
};

struct Fill {
    uint64_t passive_order_id;
    uint64_t aggressive_order_id;
    int price;
    uint32_t quantity;
    Side aggressive_side;
};

struct Order {
    Side side_;
    uint64_t order_id_;
    int price_;
    uint32_t quantity_;
    Order *prev_ = nullptr, *next_ = nullptr;

    Order() = default;
    Order(Side side, uint64_t order_id, int price, uint32_t quantity)
        : side_(side), order_id_(order_id), price_(price), quantity_(quantity) {}
};

struct Allocator {
private:
    std::vector<Order *> pools_;
    Order *free_head_ = nullptr;
    size_t chunksize_ = 16;

    void Extend() {
        free_head_ = static_cast<Order *>(::operator new(chunksize_ * sizeof(Order)));
        pools_.push_back(free_head_);
        for (size_t i = 0; i < chunksize_; i++) {
            free_head_[i].next_ = i + 1 < chunksize_ ? &free_head_[i + 1] : nullptr;
        }
        chunksize_ = std::min(chunksize_ * 2, static_cast<size_t>(1 << 20));
    }

public:
    Allocator() { Extend(); }
    ~Allocator() {
        for (Order *p : pools_) {
            ::operator delete(p);
        }
    }
    Allocator(const Allocator &) = delete;
    Allocator &operator=(const Allocator &) = delete;
    Allocator(Allocator &&) = default;
    Allocator &operator=(Allocator &&) = default;

    Order *Allocate() {
        if (!free_head_) Extend();
        Order *order = free_head_;
        free_head_ = free_head_->next_;
        return order;
    }

    void Deallocate(Order *order) {
        order->next_ = free_head_;
        free_head_ = order;
    }
};

struct Level {
    Order *head_, *tail_;
    uint32_t total_quantity_;

    Level() : head_(nullptr), tail_(nullptr), total_quantity_(0) {}

    Order *AddOrder(Allocator &alloc, Side side, uint64_t order_id, int price, uint32_t quantity) {
        Order *order = new (alloc.Allocate()) Order(side, order_id, price, quantity);
        if (!head_) {
            head_ = tail_ = order;
        } else {
            order->next_ = head_;
            head_->prev_ = order;
            head_ = order;
        }
        total_quantity_ += quantity;
        return order;
    }

    void RemoveOrder(Allocator &alloc, Order *order) {
        if (order == head_) head_ = head_->next_;
        if (order == tail_) tail_ = tail_->prev_;
        if (order->prev_) order->prev_->next_ = order->next_;
        if (order->next_) order->next_->prev_ = order->prev_;
        total_quantity_ -= order->quantity_;
        alloc.Deallocate(order);
    }
};

class OrderBook {
    Allocator allocator_;
    std::map<int, Level, std::greater<>> buy_book_;
    std::map<int, Level> sell_book_;
    std::unordered_map<uint64_t, Order *> order_map_;

    template<typename OnFill>
    uint32_t MatchOrder(Order order, auto& book, OnFill &&on_fill) {
        uint32_t matched_quantity = 0;
        uint32_t remaining_quantity = order.quantity_;

        for (auto it = book.begin(); it != book.end();) {
            if (order.side_ == Side::BUY && order.price_ < it->first) break;
            if (order.side_ == Side::SELL && order.price_ > it->first) break;
            if (remaining_quantity == 0) break;

            auto& level = it->second;
            if (remaining_quantity >= level.total_quantity_) {
                Order *cur = level.head_;
                while (cur) {
                    on_fill(Fill{cur->order_id_, order.order_id_, it->first, cur->quantity_, order.side_});
                    matched_quantity += cur->quantity_;
                    remaining_quantity -= cur->quantity_;
                    order_map_.erase(cur->order_id_);
                    Order *next = cur->next_;
                    level.RemoveOrder(allocator_, cur);
                    cur = next;
                }
                it = book.erase(it);
            } else {
                Order *cur = level.tail_;
                while (remaining_quantity > 0) {
                    if (remaining_quantity >= cur->quantity_) {
                        on_fill(Fill{cur->order_id_, order.order_id_, it->first, cur->quantity_, order.side_});
                        matched_quantity += cur->quantity_;
                        remaining_quantity -= cur->quantity_;
                        order_map_.erase(cur->order_id_);
                        Order *prev = cur->prev_;
                        level.RemoveOrder(allocator_, cur);
                        cur = prev;
                    } else {
                        on_fill(Fill{cur->order_id_, order.order_id_, it->first, remaining_quantity, order.side_});
                        cur->quantity_ -= remaining_quantity;
                        level.total_quantity_ -= remaining_quantity;
                        matched_quantity += remaining_quantity;
                        remaining_quantity = 0;
                    }
                }
                ++it;
            }
        }

        if (remaining_quantity > 0) {
            Order *new_order = nullptr;
            if (order.side_ == Side::BUY) {
                new_order = buy_book_[order.price_].AddOrder(allocator_, Side::BUY, order.order_id_, order.price_, remaining_quantity);
            } else {
                new_order = sell_book_[order.price_].AddOrder(allocator_, Side::SELL, order.order_id_, order.price_, remaining_quantity);
            }
            order_map_[order.order_id_] = new_order;
        }
        return matched_quantity;
    }

    template<typename OnFill>
    uint32_t MatchOrderAgainstBuy(Order order, OnFill &&on_fill) {
        assert(order.side_ == Side::SELL);
        return MatchOrder(order, buy_book_, std::forward<OnFill>(on_fill));
    }

    template<typename OnFill>
    uint32_t MatchOrderAgainstSell(Order order, OnFill &&on_fill) {
        assert(order.side_ == Side::BUY);
        return MatchOrder(order, sell_book_, std::forward<OnFill>(on_fill));
    }

    std::pair<double, uint32_t> GetVWAPImpl(uint32_t target_quantity, const auto& book) const {
        if (book.empty() || target_quantity == 0) return {0.0, 0};
        double sum = 0.0;
        uint32_t filled = 0;
        for (auto it = book.begin(); it != book.end() && target_quantity > 0; ++it) {
            auto& level = it->second;
            if (target_quantity >= level.total_quantity_) {
                filled += level.total_quantity_;
                sum += static_cast<double>(it->first) * level.total_quantity_;
                target_quantity -= level.total_quantity_;
            } else {
                filled += target_quantity;
                sum += static_cast<double>(it->first) * target_quantity;
                target_quantity = 0;
            }
        }
        return {sum / filled, filled};
    }

public:
    template<typename OnFill = void(*)(const Fill &)>
    uint32_t AddOrder(Order order, OnFill &&on_fill = [](const Fill &){}) {
        if (order_map_.contains(order.order_id_)) return 0;
        if (order.side_ == Side::BUY) return MatchOrderAgainstSell(order, std::forward<OnFill>(on_fill));
        else return MatchOrderAgainstBuy(order, std::forward<OnFill>(on_fill));
    }

    bool CancelOrder(uint64_t order_id) {
        auto it = order_map_.find(order_id);
        if (it == order_map_.end()) return false;
        Order *order = it->second;
        Side side = order->side_;
        int price = order->price_;
        auto& book = side == Side::BUY ? buy_book_ : sell_book_;
        auto level_it = book.find(price);
        assert(level_it != book.end());
        auto& level = level_it->second;
        level.RemoveOrder(allocator_, order);
        if (level.total_quantity_ == 0) book.erase(level_it);
        order_map_.erase(it);
        return true;
    }

    bool ModifyOrder(uint64_t order_id, uint32_t new_quantity) {
        auto it = order_map_.find(order_id);
        if (it == order_map_.end()) return false;
        if (new_quantity == 0) return CancelOrder(order_id);
        Order *order = it->second;
        Side side = order->side_;
        int price = order->price_;
        auto& book = side == Side::BUY ? buy_book_ : sell_book_;
        auto level_it = book.find(price);
        assert(level_it != book.end());
        auto& level = level_it->second;
        if (new_quantity <= order->quantity_) {
            level.total_quantity_ -= order->quantity_ - new_quantity;
            order->quantity_ = new_quantity;
        } else {
            order_map_[order_id] = level.AddOrder(allocator_, side, order->order_id_, price, new_quantity);
            level.RemoveOrder(allocator_, order);
        }
        return true;
    }

    std::optional<std::pair<int, uint32_t>> GetBestBid() const {
        if (buy_book_.empty()) return std::nullopt;
        auto it = buy_book_.begin();
        return std::make_pair(it->first, it->second.total_quantity_);
    }

    std::optional<std::pair<int, uint32_t>> GetBestAsk() const {
        if (sell_book_.empty()) return std::nullopt;
        auto it = sell_book_.begin();
        return std::make_pair(it->first, it->second.total_quantity_);
    }

    std::optional<double> GetMid() const {
        if (buy_book_.empty() || sell_book_.empty()) return std::nullopt;
        return (buy_book_.begin()->first + sell_book_.begin()->first) / 2.0;
    }

    std::optional<int> GetSpread() const {
        if (buy_book_.empty() || sell_book_.empty()) return std::nullopt;
        return sell_book_.begin()->first - buy_book_.begin()->first;
    }

    std::pair<double, uint32_t> GetVWAP(Side side, uint32_t target_quantity) const {
        if (side == Side::BUY) return GetVWAPImpl(target_quantity, buy_book_);
        else return GetVWAPImpl(target_quantity, sell_book_);
    }

    const Level &GetLevel(Side side, int depth) const {
        assert(depth >= 0);
        if (side == Side::BUY) {
            assert(depth < static_cast<int>(buy_book_.size()));
            auto it = buy_book_.begin();
            std::advance(it, depth);
            return it->second;
        } else {
            assert(depth < static_cast<int>(sell_book_.size()));
            auto it = sell_book_.begin();
            std::advance(it, depth);
            return it->second;
        }
    }
};

七、常见陷阱总结

在开发这个订单簿的过程中，我们遇到并修复了多个 Bug，它们代表了这类系统中最常见的几类问题。

Use-after-free（释放后使用） 是最危险的一类。在链表遍历中移除节点后继续访问其指针、在 RemoveOrder 释放内存后再读取订单字段、在 Deallocate 覆写 next_ 指针后再用它做遍历——这些都会导致读到无效数据。防范方法是养成习惯：在任何可能释放内存的调用之前，把后续需要的字段保存到局部变量中。

运算顺序导致的逻辑错误 是第二类常见问题。ModifyOrder 中先覆写 quantity_ 再计算差值导致差值恒为零，就是典型案例。这类 Bug 在代码审查中不容易发现，因为两行代码各自看起来都没有问题，错误只在它们的组合中产生。

资源泄漏——不是内存泄漏，而是数据结构泄漏。 空档位没有从树中移除、哈希表中残留已失效的映射、重复 Order ID 覆盖旧映射导致旧订单成为幽灵——这些不会导致内存错误，但会使系统状态逐渐腐化，最终产生错误的撮合结果或市场数据。

整数类型不匹配 是 C++ 特有的问题。uint32_t 和 int 之间的隐式转换、无符号减法的回绕、循环变量与边界条件的符号不一致——这些在编译时可能只产生 Warning，但在运行时会造成严重后果。

八、性能优化方向

当前实现使用 std::map（红黑树）存储价格档位。它的优势是实现简单、自动排序、迭代有序。但在真正的低延迟场景中，std::map 有几个问题：每个节点独立分配内存，导致缓存不友好；插入和查找都是 O(log n)；树旋转带来的分支预测失败也是延迟来源。

一个常见的优化是将价格树替换为以价格偏移量为索引的平坦数组。例如，假设价格范围在 $[P_{ref} - R, P_{ref} + R]$ 之间，用一个大小为 $2R + 1$ 的数组，array[price - P_ref + R] 直接索引到对应的 Level。查找变为 O(1)，遍历也变为顺序内存访问，对缓存极为友好。代价是需要维护最优价的位置，并且价格范围不能超出数组边界。

std::unordered_map 的 Order ID 查找通常是整个系统中最热的路径。标准库实现使用链式哈希，每个桶是一个链表，缓存不友好。替换为开放寻址的 flat hash map（例如 absl::flat_hash_map 或 robin_hood::unordered_map）通常能带来 30-50% 的查找提速。

九、基准测试

优化必须以测量为前提。以下是一个自包含的基准测试框架，模拟真实交易所的订单流分布——大约 30% 添加、50% 取消、15% 修改、5% 查询。取消操作占比最高，这符合真实市场中做市商频繁更新报价的模式。

#include <chrono>
#include <cmath>
#include <cstdio>
#include <random>
#include <algorithm>
#include <vector>

// 包含上面定义的 OrderBook
struct LatencyStats {
    std::vector<double> samples_ns;
    void Record(std::chrono::steady_clock::time_point start, std::chrono::steady_clock::time_point end) {
        auto ns = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        samples_ns.push_back(static_cast<double>(ns));
    }
    void Report(const char* label) {
        std::sort(samples_ns.begin(), samples_ns.end());
        size_t n = samples_ns.size();
        if (n == 0) return;
        double sum = 0;
        for (double s : samples_ns) sum += s;
        double mean = sum / n;
        std::printf("%-12s n=%-8zu mean=%-8.0f p50=%-8.0f p99=%-8.0f p999=%-8.0f max=%-8.0f (ns)\n",
                    label, n, mean, samples_ns[static_cast<size_t>(n * 0.50)],
                    samples_ns[static_cast<size_t>(n * 0.99)], samples_ns[static_cast<size_t>(n * 0.999)],
                    samples_ns[n - 1]);
    }
};

int main() {
    const int NUM_OPS = 1'000'000;
    const int PRICE_RANGE = 200;
    const int MID_PRICE = 10000;
    const int MAX_QTY = 100;
    std::mt19937_64 rng(42);
    std::uniform_int_distribution<int> op_dist(1, 100);
    std::uniform_int_distribution<int> side_dist(0, 1);
    std::uniform_int_distribution<uint32_t> qty_dist(1, MAX_QTY);

    OrderBook book;
    LatencyStats add_stats, cancel_stats, modify_stats;
    uint64_t next_id = 1;
    std::vector<uint64_t> live_ids;
    live_ids.reserve(NUM_OPS);

    // 预热：在买卖两侧各插入一批订单，建立初始簿深度
    for (int i = 0; i < 10000; i++) {
        Side side = side_dist(rng) ? Side::BUY : Side::SELL;
        int offset = static_cast<int>(rng() % PRICE_RANGE);
        int price = side == Side::BUY ? MID_PRICE - offset : MID_PRICE + offset;
        book.AddOrder(Order(side, next_id, price, qty_dist(rng)));
        live_ids.push_back(next_id);
        next_id++;
    }

    for (int i = 0; i < NUM_OPS; i++) {
        int op = op_dist(rng);
        if (op <= 30) {
            // 添加订单
            Side side = side_dist(rng) ? Side::BUY : Side::SELL;
            int offset = static_cast<int>(rng() % PRICE_RANGE);
            int price = side == Side::BUY ? MID_PRICE - offset : MID_PRICE + offset;
            Order o(side, next_id, price, qty_dist(rng));
            auto t0 = std::chrono::steady_clock::now();
            book.AddOrder(o);
            auto t1 = std::chrono::steady_clock::now();
            add_stats.Record(t0, t1);
            live_ids.push_back(next_id);
            next_id++;
        } else if (op <= 80 && !live_ids.empty()) {
            // 取消订单
            size_t idx = rng() % live_ids.size();
            uint64_t id = live_ids[idx];
            auto t0 = std::chrono::steady_clock::now();
            bool ok = book.CancelOrder(id);
            auto t1 = std::chrono::steady_clock::now();
            cancel_stats.Record(t0, t1);
            if (ok) {
                // O(1) 删除：与末尾元素交换
                live_ids[idx] = live_ids.back();
                live_ids.pop_back();
            }
        } else if (op <= 95 && !live_ids.empty()) {
            // 修改订单
            size_t idx = rng() % live_ids.size();
            uint64_t id = live_ids[idx];
            auto t0 = std::chrono::steady_clock::now();
            book.ModifyOrder(id, qty_dist(rng));
            auto t1 = std::chrono::steady_clock::now();
            modify_stats.Record(t0, t1);
        } else {
            // 查询（不计时，保持状态真实）
            book.GetMid();
            book.GetSpread();
            if (auto bid = book.GetBestBid(); bid.has_value()) {
                book.GetVWAP(Side::BUY, bid->second);
            }
        }
    }

    std::printf("\n订单簿基准测试 (%d 次操作)\n", NUM_OPS);
    std::printf("============================================\n");
    add_stats.Report("AddOrder");
    cancel_stats.Report("CancelOrder");
    modify_stats.Report("ModifyOrder");
    auto mid = book.GetMid();
    auto spread = book.GetSpread();
    std::printf("\n最终状态：mid=%.1f spread=%d 存活订单=%zu\n", mid.value_or(0.0), spread.value_or(0), live_ids.size());
    return 0;
}

解读基准测试结果时需要关注几个关键指标。p50（中位数）反映典型操作的延迟，p99 反映尾部延迟。如果 AddOrder 的 p99 远高于 p50，说明有些添加操作触发了跨多个档位的扫单，这是预期行为。如果 CancelOrder 的 p50 就很高，瓶颈很可能在 unordered_map 的查找上，换用 flat hash map 会有显著改善。p99 和 p999 之间的跳跃通常暴露出分配器扩展的开销——可以通过预分配足够大的初始池来消除。

编译时务必开启优化（-O2 或 -O3），否则测出来的数字毫无参考价值。同时建议在目标机器上运行，而非开发机器，因为不同 CPU 的缓存层次和分支预测能力差异很大。

十、后续扩展

本文实现的是最基本的限价 GTC（Good-Til-Cancel）订单。在此基础上，最自然的扩展包括以下几种订单类型。

IOC（Immediate-Or-Cancel）订单要求立即尽可能多地成交，未成交部分直接丢弃而不挂入订单簿。实现方式是在 MatchOrder 返回后跳过挂单逻辑——将 if (remaining_quantity > 0) 这个分支改为仅在 GTC 订单时执行即可。

FOK（Fill-Or-Kill）订单要求完全成交或完全不成交。实现方式是先做一次「模拟匹配」（Dry Run）——只检查对手方簿中是否有足够的数量满足完全成交，但不修改任何状态。只有确认可以完全成交后才执行真正的匹配。

市场订单（Market Order）没有价格限制，会以当前市场上最优的价格尽可能成交。实现方式最简单——将价格设为极端值（买方设为 INT_MAX，卖方设为 INT_MIN），价格条件检查自然通过。但要注意，如果市场订单吃穿整个对手方簿仍未完全成交，是否将剩余部分丢弃（通常是的）需要明确。