【C/C++】Order Book实现（一）

Ne0inhk

16 Mar 2026 — 26 min read

从零构建高性能订单簿（Order Book）

一、什么是订单簿

在金融交易系统中，订单簿是撮合引擎（Matching Engine）的核心数据结构。它维护着所有尚未成交的限价订单（Limit Order），按照买卖方向分为买方簿（Bid Book）和卖方簿（Ask Book）。买方簿中价格最高的订单称为最优买价（Best Bid），卖方簿中价格最低的订单称为最优卖价（Best Ask）。两者之间的差值称为买卖价差（Spread），它们的均值称为中间价（Mid Price）。

当一笔新订单进入系统时，撮合引擎会尝试将其与对手方簿中的现有订单进行匹配。如果价格满足条件——买单价格不低于卖方挂单价格，或卖单价格不高于买方挂单价格——则发生成交（Fill）。未成交的部分会被挂入对应的订单簿中等待后续匹配。

绝大多数交易所采用价格优先、时间优先（Price-Time Priority，也称 FIFO）的撮合规则：在同一价格档位（Price Level）上，先到的订单优先被成交。这个规则直接决定了我们的数据结构设计。

二、核心数据结构

2.1 订单（Order）

订单是整个系统中最基本的单元。每笔订单至少包含方向（Side）、唯一标识（Order ID）、价格（Price）和数量（Quantity）。由于同一价格档位上的订单需要按照先后顺序组织，我们使用双向链表（Doubly Linked List）将它们串联起来，因此每个订单还需要前驱和后继指针。

// 买卖方向enumclassSide{ BUY, SELL };structOrder{ 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){}};

这里有一个值得注意的设计决策：价格使用 int 而不是 double。在真实交易系统中，价格通常表示为最小价格单位（Tick）的整数倍。例如，某只股票的最小变动单位是 0.01 元，那么 100.23 元就表示为整数 10023。这样做的好处是完全消除浮点精度问题，同时整数比较和运算也比浮点更快。

2.2 价格档位（Price Level）

价格档位是同一价格上所有订单的集合。它维护一个双向链表和该档位的总数量。新订单插入链表头部（head），匹配时从链表尾部（tail）开始消耗——尾部是最早到达的订单，这样就实现了 FIFO 语义。

structLevel{ 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;}// 从链表中移除任意位置的订单voidRemoveOrder(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);}};

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

2.3 内存分配器（Allocator）

在高频交易场景中，new 和 delete 的开销是不可接受的。每笔订单的生命周期很短——大量订单被添加后很快就被取消——如果每次都走系统分配器，频繁的内存分配和释放会造成严重的延迟抖动（Latency Jitter）。

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

structAllocator{private: std::vector<Order *> pools_;// 所有已分配的内存块 Order *free_head_ =nullptr;// 空闲链表头 size_t chunksize_ =16;// 当前块大小，每次翻倍voidExtend(){// 分配一块原始内存（不调用构造函数） free_head_ =static_cast<Order *>(::operatornew(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;}// 翻倍增长，但设置上限防止 size_t 溢出 chunksize_ = std::min(chunksize_ *2,static_cast<size_t>(1<<20));}public:Allocator(){Extend();}~Allocator(){for(Order *p : pools_){::operatordelete(p);}} Order *Allocate(){if(!free_head_){Extend();// 空闲链表耗尽，扩展} Order *order = free_head_; free_head_ = free_head_->next_;return order;}voidDeallocate(Order *order){ order->next_ = free_head_; free_head_ = order;}};

这里有两个容易忽视的问题。第一，chunksize_ 的翻倍增长如果不设上限，经过足够多次 Extend() 后会溢出到零，导致零长度分配，后续访问未初始化内存。第二，空闲链表复用了 Order::next_ 指针来串联空闲节点。这意味着被归还到空闲链表的 Order 对象中 next_ 已被覆写，如果此后还有代码试图通过这个指针遍历（即发生了 use-after-free），读到的将是空闲链表中其他节点的地址，造成极难排查的 Bug。

关于分配器的归属问题：分配器应该由 OrderBook 持有，而不是作为全局变量。 全局分配器在多线程环境下会成为串行化瓶颈——要么加锁，要么用无锁（Lock-Free）结构，都有额外开销。而每个 OrderBook 持有自己的分配器，则天然没有竞争。此外，当一个 OrderBook 被销毁时，其分配器一并销毁，不需要逐个释放订单，生命周期管理变得极为简单。从缓存局部性（Cache Locality）的角度看，同一个订单簿的订单从同一块连续内存中分配，匹配时访问的内存地址更加集中，对 CPU 缓存更加友好。

2.4 订单簿（OrderBook）

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

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

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

三、撮合逻辑（Matching）

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

3.1 成交回报（Execution Callback）

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

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

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

// 使用方式示例：// 将成交发送到网关 book.AddOrder(order,[&](const Fill &f){ gateway.SendExecutionReport(f);});// 收集成交记录 std::vector<Fill> fills; book.AddOrder(order,[&](const Fill &f){ fills.push_back(f);});// 不关心成交细节 book.AddOrder(order,[](const Fill &){});

3.2 匹配实现

template<typenameOnFill>uint32_tMatchOrder(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 开始，因为 tail 是最早到达的订单，这是 FIFO 的核心保证。

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

四、订单操作

4.1 添加订单（Add Order）

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

template<typenameOnFill=void(*)(const Fill &)>uint32_tAddOrder(Order order, OnFill &&on_fill =[](const Fill &){}){// 防止重复 Order IDif(order_map_.contains(order.order_id_)){return0;}if(order.side_ == Side::BUY){returnMatchOrderAgainsSell(order, std::forward<OnFill>(on_fill));}else{returnMatchOrderAgainstBuy(order, std::forward<OnFill>(on_fill));}}

4.2 取消订单（Cancel Order）

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

boolCancelOrder(uint64_t order_id){auto it = order_map_.find(order_id);if(it == order_map_.end()){returnfalse;} 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());// 不变量：order_map_ 中的订单必有对应档位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);returntrue;}

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

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

4.3 修改订单（Modify Order）

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

boolModifyOrder(uint64_t order_id,uint32_t new_quantity){auto it = order_map_.find(order_id);if(it == order_map_.end()){returnfalse;}// 数量为零等同于取消if(new_quantity ==0){returnCancelOrder(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);}returntrue;}

减量修改中两行代码的顺序至关重要。 考虑以下错误写法：

// 错误！ order->quantity_ = new_quantity;// 先覆写 level.total_quantity_ -= order->quantity_ - new_quantity;// 差值恒为零

先把 order->quantity_ 改成 new_quantity，然后计算 order->quantity_ - new_quantity，得到的永远是零。total_quantity_ 永远不会减少，导致后续所有依赖 total_quantity_ 的逻辑（匹配、VWAP 计算、最优价查询）全部出错。这类 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（Volume-Weighted Average Price）回答的问题是："如果我要买入/卖出 N 手，平均成交价是多少？"它从最优价开始逐层消耗，加权计算平均价格。

std::pair<double,uint32_t>GetVWAP(uint32_t target_quantity,constauto&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 的迭代器不支持随机访问。对于需要频繁查询多层深度的场景（例如行情推送），这可能成为瓶颈，后面讨论优化时会提到替代方案。

六、完整代码

以下是经过所有 Bug 修复和设计改进后的完整实现：

#include<algorithm>#include<cassert>#include<cstddef>#include<cstdint>#include<iterator>#include<map>#include<new>#include<optional>#include<unordered_map>#include<utility>#include<vector>enumclassSide{ BUY, SELL };// 成交回报structFill{uint64_t passive_order_id;uint64_t aggressive_order_id;int price;uint32_t quantity; Side aggressive_side;};structOrder{ 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){}};structAllocator{private: std::vector<Order *> pools_; Order *free_head_ =nullptr; size_t chunksize_ =16;voidExtend(){ free_head_ =static_cast<Order *>(::operatornew(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_){::operatordelete(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;}voidDeallocate(Order *order){ order->next_ = free_head_; free_head_ = order;}};structLevel{ 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;}voidRemoveOrder(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);}};classOrderBook{ 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<typenameOnFill>uint32_tMatchOrder(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<typenameOnFill>uint32_tMatchOrderAgainstBuy(Order order, OnFill &&on_fill){assert(order.side_ == Side::SELL);returnMatchOrder(order, buy_book_, std::forward<OnFill>(on_fill));}template<typenameOnFill>uint32_tMatchOrderAgainstSell(Order order, OnFill &&on_fill){assert(order.side_ == Side::BUY);returnMatchOrder(order, sell_book_, std::forward<OnFill>(on_fill));} std::pair<double,uint32_t>GetVWAPImpl(uint32_t target_quantity,constauto&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<typenameOnFill=void(*)(const Fill &)>uint32_tAddOrder(Order order, OnFill &&on_fill =[](const Fill &){}){if(order_map_.contains(order.order_id_))return0;if(order.side_ == Side::BUY)returnMatchOrderAgainstSell( order, std::forward<OnFill>(on_fill));elsereturnMatchOrderAgainstBuy( order, std::forward<OnFill>(on_fill));}boolCancelOrder(uint64_t order_id){auto it = order_map_.find(order_id);if(it == order_map_.end())returnfalse; 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);returntrue;}boolModifyOrder(uint64_t order_id,uint32_t new_quantity){auto it = order_map_.find(order_id);if(it == order_map_.end())returnfalse;if(new_quantity ==0)returnCancelOrder(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);}returntrue;} 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)returnGetVWAPImpl(target_quantity, buy_book_);elsereturnGetVWAPImpl(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_ 指针后再用它做遍历——这些都会导致读到无效数据。这类 Bug 的可怕之处在于它往往不会立即崩溃，而是产生微妙的错误结果，直到压力测试或生产环境中才暴露。防范方法是养成习惯：在任何可能释放内存的调用之前，把后续需要的字段保存到局部变量中。

运算顺序导致的逻辑错误 是第二类常见问题。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 查找通常是整个系统中最热的路径，因为每笔取消和修改都要走它。标准库实现使用链式哈希（Chained Hashing），每个桶是一个链表，缓存不友好。替换为开放寻址（Open Addressing）的 flat hash map（例如 absl::flat_hash_map 或 robin_hood::unordered_map）通常能带来 30-50% 的查找提速。

九、基准测试（Benchmark）

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

#include<chrono>#include<cmath>#include<cstdio>#include<random>#include<algorithm>#include<vector>// 包含上面定义的 OrderBookstructLatencyStats{ std::vector<double> samples_ns;voidRecord(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));}voidReport(constchar*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]);}};intmain(){constexprint NUM_OPS =1'000'000;constexprint PRICE_RANGE =200;constexprint MID_PRICE =10000;constexprint 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++;}elseif(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();}}elseif(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());return0;}

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

编译时务必开启优化（-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），价格条件检查自然通过。但要注意，如果市场订单吃穿整个对手方簿仍未完全成交，是否将剩余部分丢弃（通常是的）需要明确。