写一个订单簿：C++实现和几个容易踩的坑

RemoveOrder 里的四个 if 不是过度防御——它们分别处理节点在头部、尾部、中间、以及同时是头尾（链表只有一个节点）的情况。如果写成 if-else 链，当链表仅有一个节点时，只会命中第一个分支（head），但不会更新 tail，导致 tail 变成悬空指针。我见过不止一个人在这里踩坑。

让内存分配不拖后腿

高频交易里，直接 new/delete 订单对象是灾难。每个订单存活时间极短，大量的分配/释放会让延迟分布的长尾很难看。常见的解决方案是自己维护一个内存池：预先分配一大块内存，切成等大的 Order 槽，用空闲链表串起来。

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_ 倍增时如果不设上限，理论上会翻到溢出，导致分配长度为 0 的块；二是空闲链表复用了 Order::next_ 指针——一旦 Deallocate，该 order 的 next_ 就被写成了空闲链表中的下一个节点地址。之后如果有代码再通过这个 order 去遍历链表，就会读到完全不同的东西。

另外，分配器应该由 OrderBook 对象持有，而不是全局单例。这样每个订单簿有自己的内存池，天然无锁，且销毁时一并回收所有内存，生命周期管理很简单。从缓存局部性角度，同一个订单簿的所有订单都从同一块连续内存中分配，匹配时缓存命中率会更高。

用两棵价格树组织订单簿

买方簿按价格从高到低排序，卖方簿从低到高，这样 begin() 拿到的就是最优价格。这里用 std::map 足够简单，但要注意 Key 的顺序策略。

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_;
    // ...
};

order_map_ 用于 O(1) 通过 ID 找到订单指针，取消和修改操作全靠它。

撮合：事情最多的地方

撮合流程可以总结为一件事：新订单进来，看看对手方簿里有没有能成交的，有就尽量吃，剩下的挂到自己的簿里。买卖两侧逻辑对称，我用了一个模板函数来消除重复代码。

为了演示完整，先定义成交回报 Fill：

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

匹配的核心在下面。遍历对手簿时，只要价格满足条件（买单 ≥ 最低卖价，或卖单 ≤ 最高买价）且剩余量大于零，就进入当前价位。如果剩余量足以扫光整个价位，就把链表从头清到尾——虽然主动方会把整个价位吃掉，但为了逐笔产生成交记录，还是老老实实遍历一遍。如果扫不光，就从链表的尾部（最老的订单）开始消耗，因为 FIFO 规则要求优先匹配先到的订单。

template<typename OnFill>
uint32_t OrderBook::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;
}

遍历中途调用了 RemoveOrder，它会立即调用 Deallocate 把 order 内存归还到空闲池。所以必须先保存 cur->next_（或 prev_）再移除，否则就是典型的 use-after-free。哪怕测试没崩，也离崩不远。

挂单时直接 buy_book_[order.price_] 会自动创建新价位，这是我们期望的。

添加、取消、修改订单里的细节

添加订单前，一定得检查重复 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));
    }
}

取消订单时，必须先找到订单所在的价位，然后从链表移走，还得记得：若价位变空，要立刻从树中删掉，否则空价位会污染 Best Bid/Ask 这类查询。

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);
    // order 内存已归还，不能再碰 order->xxx

    if (level.total_quantity_ == 0) {
        book.erase(level_it);
    }
    order_map_.erase(it);
    return true;
}

这里同样要提防 use-after-free：side 和 price 必须在调用 RemoveOrder 之前保存，因为 order 内存会在那一刻被回收，之后再访问 order->side_ 就是非法操作。

修改订单的语义稍微复杂。减量（新数量 ≤ 原数量）时，订单保持在链表原位置——时间优先权不该因为减仓而丧失。但要小心更新数量的顺序：必须先算出差值去调整 total_quantity_，再改写 order->quantity_。顺序一反，差值恒为零，数据就默默污染了。增量修改时，订单失去时间优先，相当于先取消旧单再挂一张新单。要记得先调用 AddOrder（会在链表头部插入新订单），再 RemoveOrder 移走旧订单，否则中间间隙会导致哈希表里的 order 指针短暂失效。

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;
}

市场数据查询

Best Bid/Ask、中间价、价差这些接口都简单直接，唯一要注意的是簿可能被完全清空，所以返回 std::optional 比 assert 合理。

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;
}

VWAP（成交量加权平均价格）用于快速估算一笔市价单的大致成交价。它从最优价开始逐层消耗虚拟数量，加权求和。有一个小细节：如果传入的 target_quantity 为 0，要直接返回，否则分母为零会引发 NaN。

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};
}

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_);
}

GetLevel(depth) 偶尔用于展示市场深度。std::map 的迭代器不支持随机访问，std::advance 会线性步进，所以频繁取深层数据时要注意性能。如果场景要求很快，后面会提到替代方案。

完整的头文件

上面分块讲了各个部分，下面是把它们拼在一起的完整类声明。有些细节调整了一下，比如 Allocator 禁用了拷贝但允许移动，这都是为了让它安全地作为成员变量存在。

#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) { /* 实现如上 */ }

    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 { /* 同上 */ }

public:
    template<typename OnFill = void(*)(const Fill &)>
    uint32_t AddOrder(Order order, OnFill &&on_fill = [](const Fill &){}) { /* 同上 */ }

    bool CancelOrder(uint64_t order_id) { /* 同上 */ }

    bool ModifyOrder(uint64_t order_id, uint32_t new_quantity) { /* 同上 */ }

    std::optional<std::pair<int, uint32_t>> GetBestBid() const { /* 同上 */ }
    std::optional<std::pair<int, uint32_t>> GetBestAsk() const { /* 同上 */ }
    std::optional<double> GetMid() const { /* 同上 */ }
    std::optional<int> GetSpread() const { /* 同上 */ }

    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;
        }
    }
};

性能测试和优化方向

没有基准测试的优化都是耍流氓。下面这段代码模拟了接近真实交易所的订单流：大约 30% 新增、50% 取消、15% 修改、5% 查询。取消操作最多，因为做市商经常撤销并重新挂单。

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

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[n * 0.50], samples_ns[n * 0.99], samples_ns[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) {
                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 上，换成开放寻址哈希表（如 absl::flat_hash_map）能快不少。p99 到 p999 的跳跃往往暴露出分配器扩展内存的开销，可以通过在构造时就预分配一块足够大的池来化解。

编译记得带 -O2 或 -O3，否则测出来的数字毫无意义。最好在目标硬件上跑，不同 CPU 的缓存和分支预测差异巨大。

至于下一步优化，用平坦数组代替 std::map 是个经典方案。比如限定价格范围在 [P_ref - R, P_ref + R] 之间，就可以用一个 std::array 根据价格偏移直接索引到 Level，插入与查找均摊 O(1)，且内存连续，缓存友好。代价是需要维护最优价的位置，且价格不能越界。

可以加上的订单类型

目前只实现了 GTC 限价单。如果要支持更多类型，改造点并不多：

• IOC（立即或取消）：在 MatchOrder 返回后，如果还有剩余量，直接丢弃，不挂单。
• FOK（全部成交或取消）：先跑一遍"模拟匹配"（只检查对手簿数量，不改状态），确定能完全吃下后再真正匹配。
• 市价单：把价格设成 INT_MAX 或 INT_MIN，匹配的条件自然就永远满足，它会一直吃到对面簿被扫空或者自身剩余量为零。通常会把剩余部分丢弃。

这些都是在现有基础上做减法和分支，实现并不复杂。