订单簿设计¶
方案1：向量订单簿 (Vector-based LOB)
核心:
- 使用
std::vector数组存储价格点 - 通过Tick Size将价格直接映射到数组索引
- 索引计算：
index = price.raw() / tick_size.raw()
优点:
- O(1)确定性性能 - 数组直接访问
- CPU缓存友好 - 连续内存访问
- 无哈希计算开销
缺点:
- 预分配大内存 - 默认需分配3000万个元素
- 内存浪费 - 稀疏订单簿浪费大量空间
- 价格范围受限
#include <cstdint>
#include <optional>
namespace lob {
// 基础类型定义
using OrderId = uint64_t;
enum class Side { Buy, Sell };
class Price {
private:
int64_t raw_value_;
static constexpr int64_t DECIMALS = 100000000; // 8位小数
public:
constexpr static int64_t decimals() { return DECIMALS; }
explicit Price(int64_t raw) : raw_value_(raw) {}
static Price from_raw(int64_t raw) { return Price(raw); }
static Price from_double(double value) {
return Price(static_cast<int64_t>(value * DECIMALS));
}
int64_t raw() const { return raw_value_; }
double to_double() const {
return static_cast<double>(raw_value_) / DECIMALS;
}
bool operator==(const Price& other) const {
return raw_value_ == other.raw_value_;
}
bool operator<(const Price& other) const {
return raw_value_ < other.raw_value_;
}
bool operator<=(const Price& other) const {
return raw_value_ <= other.raw_value_;
}
bool operator>(const Price& other) const {
return raw_value_ > other.raw_value_;
}
bool operator>=(const Price& other) const {
return raw_value_ >= other.raw_value_;
}
};
class Quantity {
private:
int64_t raw_value_;
static constexpr int64_t DECIMALS = 100000000; // 8位小数
public:
explicit Quantity(int64_t raw) : raw_value_(raw) {}
static Quantity from_raw(int64_t raw) { return Quantity(raw); }
static Quantity from_double(double value) {
return Quantity(static_cast<int64_t>(value * DECIMALS));
}
int64_t raw() const { return raw_value_; }
double to_double() const {
return static_cast<double>(raw_value_) / DECIMALS;
}
bool is_zero() const { return raw_value_ == 0; }
Quantity& operator-=(const Quantity& other) {
raw_value_ -= other.raw_value_;
if (raw_value_ < 0) raw_value_ = 0;
return *this;
}
Quantity operator-(const Quantity& other) const {
int64_t result = raw_value_ - other.raw_value_;
return Quantity(result < 0 ? 0 : result);
}
Quantity& operator+=(const Quantity& other) {
raw_value_ += other.raw_value_;
return *this;
}
friend bool operator<(const Quantity& lhs, const Quantity& rhs) {
return lhs.raw_value_ < rhs.raw_value_;
}
friend bool operator<=(const Quantity& lhs, const Quantity& rhs) {
return lhs.raw_value_ <= rhs.raw_value_;
}
};
struct Order {
OrderId id;
Price price;
Quantity quantity;
Side side;
uint64_t timestamp; // 纳秒级时间戳，用于FIFO
Order(OrderId id, Price price, Quantity quantity, Side side,
uint64_t timestamp)
: id(id),
price(price),
quantity(quantity),
side(side),
timestamp(timestamp) {}
};
// 价格点结构 - 存储同一价格级别订单链表的头尾指针
struct PricePoint {
std::optional<size_t> first_order_idx;
std::optional<size_t> last_order_idx;
PricePoint() = default;
bool empty() const { return !first_order_idx.has_value(); }
void clear() {
first_order_idx = std::nullopt;
last_order_idx = std::nullopt;
}
};
// 订单节点 - 形成同价格级别订单的链表
template <typename OrderT>
struct OrderNode {
OrderT order;
std::optional<size_t> next_idx;
explicit OrderNode(OrderT order)
: order(std::move(order)), next_idx(std::nullopt) {}
};
} // namespace lob
#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <stdexcept>
#include <unordered_map>
#include <vector>
#include "common.h"
namespace lob {
// 向量订单簿实现
template <typename OrderT>
class VectorOrderBook {
private:
// 配置参数
const size_t MAX_TICKS = 30000000; // 最大支持3000万价格点
std::string symbol_;
Price tick_size_;
// 核心数据结构
std::vector<PricePoint> bids_; // 买单价格点
std::vector<PricePoint> asks_; // 卖单价格点
std::vector<std::optional<OrderNode<OrderT>>> orders_; // 订单存储池
std::unordered_map<OrderId, size_t> order_index_; // 订单ID到存储索引的映射
// 缓存
std::optional<Price> best_bid_;
std::optional<Price> best_ask_;
std::optional<Price> last_trade_price_;
// 管理
size_t next_slot_;
// 辅助方法：价格转索引
size_t price_to_index(const Price& price) const {
return static_cast<size_t>(price.raw() / tick_size_.raw());
}
// 辅助方法：获取指定价格和方向的价格点
PricePoint* get_price_point(const Price& price, Side side) {
size_t idx = price_to_index(price);
if (idx >= MAX_TICKS) {
return nullptr;
}
return side == Side::Buy ? &bids_[idx] : &asks_[idx];
}
PricePoint* get_price_point_by_index(size_t idx, Side side) {
if (idx >= MAX_TICKS) {
return nullptr;
}
return side == Side::Buy ? &bids_[idx] : &asks_[idx];
}
// 更新最佳价格
void update_best_price(const Price& price, Side side) {
if (side == Side::Buy) {
if (!best_bid_.has_value() || price > best_bid_.value()) {
best_bid_ = price;
}
// 如果这是被移除的最佳价格，需要查找新的最佳价格
if (best_bid_.has_value() && best_bid_.value() == price) {
size_t idx = price_to_index(price);
if (idx < MAX_TICKS) {
auto price_point = get_price_point_by_index(idx, Side::Buy);
if (price_point && !price_point->empty()) {
return; // 当前价格仍有订单
}
}
// 需要从当前价格向下查找新的最佳买价
for (size_t i = idx; i > 0; --i) {
auto pp = get_price_point_by_index(i, Side::Buy);
if (pp && !pp->empty()) {
best_bid_ =
Price::from_raw(static_cast<int64_t>(i) * tick_size_.raw());
return;
}
}
best_bid_ = std::nullopt;
}
} else {
if (!best_ask_.has_value() || price < best_ask_.value()) {
best_ask_ = price;
}
// 如果这是被移除的最佳价格，需要查找新的最佳价格
if (best_ask_.has_value() && best_ask_.value() == price) {
size_t idx = price_to_index(price);
if (idx < MAX_TICKS) {
auto price_point = get_price_point_by_index(idx, Side::Sell);
if (price_point && !price_point->empty()) {
return; // 当前价格仍有订单
}
}
// 需要从当前价格向上查找新的最佳卖价
for (size_t i = idx; i < MAX_TICKS; ++i) {
auto pp = get_price_point_by_index(i, Side::Sell);
if (pp && !pp->empty()) {
best_ask_ =
Price::from_raw(static_cast<int64_t>(i) * tick_size_.raw());
return;
}
}
best_ask_ = std::nullopt;
}
}
}
// 链接订单到价格级别
void link_order_to_price_level(size_t order_idx, const Price& price,
Side side) {
auto price_point = get_price_point(price, side);
if (!price_point) return;
if (price_point->empty()) {
// 新价格点
price_point->first_order_idx = order_idx;
price_point->last_order_idx = order_idx;
} else {
// 链接到现有链表尾部
size_t last_idx = price_point->last_order_idx.value();
orders_[last_idx]->next_idx = order_idx;
price_point->last_order_idx = order_idx;
}
}
// 重建价格点的订单链表
void rebuild_price_level(const Price& price, Side side) {
auto price_point = get_price_point(price, side);
if (!price_point || price_point->empty()) return;
size_t current_idx = price_point->first_order_idx.value();
std::vector<size_t> valid_indices;
while (current_idx < orders_.size() && orders_[current_idx].has_value()) {
valid_indices.push_back(current_idx);
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
if (valid_indices.empty()) {
price_point->clear();
return;
}
// 重建链表
for (size_t i = 0; i < valid_indices.size() - 1; ++i) {
orders_[valid_indices[i]]->next_idx = valid_indices[i + 1];
}
orders_[valid_indices.back()]->next_idx = std::nullopt;
price_point->first_order_idx = valid_indices[0];
price_point->last_order_idx = valid_indices.back();
}
public:
VectorOrderBook(std::string symbol, const Price& tick_size)
: symbol_(std::move(symbol)),
tick_size_(tick_size),
bids_(MAX_TICKS),
asks_(MAX_TICKS),
orders_(10000), // 预分配10000个订单槽位
next_slot_(0) {}
// 添加订单 - O(1)时间复杂度
bool add_order(const OrderT& order) {
// 验证
if (order_index_.find(order.id) != order_index_.end()) {
throw std::runtime_error("Order already exists");
}
size_t idx = price_to_index(order.price);
if (idx >= MAX_TICKS) {
throw std::runtime_error("Price out of range");
}
// 确保有足够的槽位
if (next_slot_ >= orders_.size()) {
orders_.resize(orders_.size() * 2);
}
// 存储订单
orders_[next_slot_] = OrderNode<OrderT>(order);
order_index_[order.id] = next_slot_;
// 链接到价格级别
link_order_to_price_level(next_slot_, order.price, order.side);
// 更新最佳价格
update_best_price(order.price, order.side);
next_slot_++;
return true;
}
// 删除订单 - O(1)时间复杂度
bool remove_order(OrderId order_id) {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return false;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return false;
// 保存价格和方向用于后续更新
const auto& order = orders_[idx]->order;
Price price = order.price;
Side side = order.side;
// 标记为已删除
orders_[idx] = std::nullopt;
order_index_.erase(it);
// 重建该价格级别的链表
rebuild_price_level(price, side);
update_best_price(price, side);
return true;
}
// 修改订单数量
bool modify_order(OrderId order_id, Quantity new_quantity) {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return false;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return false;
auto& order = orders_[idx]->order;
order.quantity = new_quantity;
if (new_quantity.is_zero()) {
return remove_order(order_id);
}
return true;
}
// 查找订单 - O(1)时间复杂度
const OrderT* find_order(OrderId order_id) const {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return nullptr;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return nullptr;
return &(orders_[idx]->order);
}
// 匹配订单 - O(p+k)时间复杂度
std::vector<const OrderT*> match_orders(Side side, const Price& price,
Quantity quantity) {
std::vector<const OrderT*> matched_orders;
matched_orders.reserve(16); // 预分配空间
Quantity remaining = quantity;
if (side == Side::Buy) {
// 买单从最低卖价开始匹配
if (!best_ask_.has_value()) return matched_orders;
size_t start_tick = price_to_index(best_ask_.value());
size_t end_tick = price_to_index(price);
for (size_t tick = start_tick; tick <= end_tick && !remaining.is_zero();
++tick) {
if (tick >= MAX_TICKS) break;
auto& price_point = asks_[tick];
if (price_point.empty()) continue;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value() && !remaining.is_zero()) {
auto& node = orders_[current_idx].value();
auto& order = node.order;
if (order.quantity.raw() > 0) {
Quantity fill_qty =
(remaining < order.quantity) ? remaining : order.quantity;
remaining -= fill_qty;
matched_orders.push_back(&order);
// 更新订单数量
Quantity new_qty = order.quantity - fill_qty;
if (new_qty.is_zero()) {
// 需要删除订单
order_index_.erase(order.id);
orders_[current_idx] = std::nullopt;
} else {
order.quantity = new_qty;
}
}
// 移动到链表中的下一个订单（如果存在）
current_idx = node.next_idx.value_or(orders_.size());
}
// 重建该价格级别的链表
if (!remaining.is_zero()) {
rebuild_price_level(
Price::from_raw(static_cast<int64_t>(tick) * tick_size_.raw()),
Side::Sell);
}
}
} else {
// 卖单从最高买价开始匹配
if (!best_bid_.has_value()) return matched_orders;
size_t start_tick = price_to_index(best_bid_.value());
size_t end_tick = price_to_index(price);
// 从高到低遍历
for (size_t tick = start_tick; tick >= end_tick && !remaining.is_zero();
--tick) {
if (tick >= MAX_TICKS) continue;
auto& price_point = bids_[tick];
if (price_point.empty()) continue;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value() && !remaining.is_zero()) {
auto& node = orders_[current_idx].value();
auto& order = node.order;
if (order.quantity.raw() > 0) {
Quantity fill_qty =
(remaining < order.quantity) ? remaining : order.quantity;
remaining -= fill_qty;
matched_orders.push_back(&order);
// 更新订单数量
Quantity new_qty = order.quantity - fill_qty;
if (new_qty.is_zero()) {
// 需要删除订单
order_index_.erase(order.id);
orders_[current_idx] = std::nullopt;
} else {
order.quantity = new_qty;
}
}
current_idx = node.next_idx.value_or(orders_.size());
}
// 重建该价格级别的链表
if (!remaining.is_zero()) {
rebuild_price_level(
Price::from_raw(static_cast<int64_t>(tick) * tick_size_.raw()),
Side::Buy);
}
if (tick == 0) break; // 防止无符号整数下溢
}
}
// 更新最佳价格
update_best_price(best_bid_.value_or(Price::from_raw(0)), Side::Buy);
update_best_price(best_ask_.value_or(Price::from_raw(0)), Side::Sell);
return matched_orders;
}
// 获取最佳买价/卖价
std::optional<Price> best_bid() const { return best_bid_; }
std::optional<Price> best_ask() const { return best_ask_; }
// 获取市场深度
std::pair<std::vector<std::pair<Price, Quantity>>,
std::vector<std::pair<Price, Quantity>>>
market_depth(size_t levels) {
std::vector<std::pair<Price, Quantity>> bid_depth;
std::vector<std::pair<Price, Quantity>> ask_depth;
bid_depth.reserve(levels);
ask_depth.reserve(levels);
// 获取买方深度
if (best_bid_.has_value()) {
size_t start_tick = price_to_index(best_bid_.value());
for (size_t tick = start_tick; tick > 0 && bid_depth.size() < levels;
--tick) {
if (tick >= MAX_TICKS) continue;
auto& price_point = bids_[tick];
if (price_point.empty()) continue;
Quantity total_qty;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value()) {
total_qty += orders_[current_idx]->order.quantity;
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
bid_depth.emplace_back(
Price::from_raw(static_cast<int64_t>(tick) * tick_size_.raw()),
total_qty);
}
}
// 获取卖方深度
if (best_ask_.has_value()) {
size_t start_tick = price_to_index(best_ask_.value());
for (size_t tick = start_tick;
tick < MAX_TICKS && ask_depth.size() < levels; ++tick) {
auto& price_point = asks_[tick];
if (price_point.empty()) continue;
Quantity total_qty;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value()) {
total_qty += orders_[current_idx]->order.quantity;
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
ask_depth.emplace_back(
Price::from_raw(static_cast<int64_t>(tick) * tick_size_.raw()),
total_qty);
}
}
return {bid_depth, ask_depth};
}
};
} // namespace lob
方案2：哈希订单簿 (Hash-based LOB)
核心:
- 使用
std::unordered_map存储价格点 - Key = Tick数量，Value = PricePoint
- 只存储实际有订单的价格级别
优点:
- 内存高效 - 仅存储有订单的价格点
- 无价格范围限制 - 支持任意价格范围
- 适合低价币和稀疏订单簿
缺点:
- 哈希开销 - 查找有哈希计算成本
- 非确定性O(1) - 存在碰撞风险
- 需要排序 - 匹配时需要收集并排序价格点
#include <algorithm>
#include <cmath>
#include <stdexcept>
#include <unordered_map>
#include <vector>
#include "common.h"
namespace lob {
// 哈希订单簿实现
template <typename OrderT>
class HashOrderBook {
private:
std::string symbol_;
Price tick_size_;
// 使用unordered_map替代vector
std::unordered_map<size_t, PricePoint>
bids_; // Key: tick index, Value: PricePoint
std::unordered_map<size_t, PricePoint> asks_;
std::vector<std::optional<OrderNode<OrderT>>> orders_;
std::unordered_map<OrderId, size_t> order_index_;
// 缓存
std::optional<Price> best_bid_;
std::optional<Price> best_ask_;
std::optional<Price> last_trade_price_;
size_t next_slot_;
size_t price_to_index(const Price& price) const {
return static_cast<size_t>(price.raw() / tick_size_.raw());
}
Price index_to_price(size_t idx) const {
return Price::from_raw(static_cast<int64_t>(idx) * tick_size_.raw());
}
// 获取价格点 - 如果不存在则创建
PricePoint* get_or_create_price_point(const Price& price, Side side) {
size_t idx = price_to_index(price);
auto& container = (side == Side::Buy) ? bids_ : asks_;
auto it = container.find(idx);
if (it != container.end()) {
return &it->second;
} else {
auto [new_it, inserted] = container.emplace(idx, PricePoint());
return &new_it->second;
}
}
// 获取价格点 - 如果不存在则返回nullptr
PricePoint* get_price_point(const Price& price, Side side) {
size_t idx = price_to_index(price);
auto& container = (side == Side::Buy) ? bids_ : asks_;
auto it = container.find(idx);
if (it != container.end()) {
return &it->second;
} else {
return nullptr;
}
}
void update_best_price(const Price& price, Side side) {
if (side == Side::Buy) {
if (!best_bid_.has_value() || price > best_bid_.value()) {
best_bid_ = price;
}
// 检查当前最佳价格是否还有订单
if (best_bid_.has_value()) {
auto pp = get_price_point(best_bid_.value(), Side::Buy);
if (!pp || pp->empty()) {
// 需要查找新的最佳买价
Price new_best;
bool found = false;
for (const auto& [idx, pp] : bids_) {
if (!pp.empty()) {
Price p = index_to_price(idx);
if (!found || p > new_best) {
new_best = p;
found = true;
}
}
}
best_bid_ = found ? new_best : std::nullopt;
}
}
} else {
if (!best_ask_.has_value() || price < best_ask_.value()) {
best_ask_ = price;
}
// 检查当前最佳价格是否还有订单
if (best_ask_.has_value()) {
auto pp = get_price_point(best_ask_.value(), Side::Sell);
if (!pp || pp->empty()) {
// 需要查找新的最佳卖价
Price new_best;
bool found = false;
for (const auto& [idx, pp] : asks_) {
if (!pp.empty()) {
Price p = index_to_price(idx);
if (!found || p < new_best) {
new_best = p;
found = true;
}
}
}
best_ask_ = found ? new_best : std::nullopt;
}
}
}
}
void link_order_to_price_level(size_t order_idx, const Price& price,
Side side) {
auto price_point = get_or_create_price_point(price, side);
if (!price_point) return;
if (price_point->empty()) {
price_point->first_order_idx = order_idx;
price_point->last_order_idx = order_idx;
} else {
size_t last_idx = price_point->last_order_idx.value();
orders_[last_idx]->next_idx = order_idx;
price_point->last_order_idx = order_idx;
}
}
// 重建价格点的订单链表
void rebuild_price_level(const Price& price, Side side) {
auto price_point = get_price_point(price, side);
if (!price_point || price_point->empty()) return;
size_t current_idx = price_point->first_order_idx.value();
std::vector<size_t> valid_indices;
while (current_idx < orders_.size() && orders_[current_idx].has_value()) {
valid_indices.push_back(current_idx);
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
if (valid_indices.empty()) {
size_t idx = price_to_index(price);
if (side == Side::Buy) {
bids_.erase(idx);
} else {
asks_.erase(idx);
}
return;
}
// 重建链表
for (size_t i = 0; i < valid_indices.size() - 1; ++i) {
orders_[valid_indices[i]]->next_idx = valid_indices[i + 1];
}
orders_[valid_indices.back()]->next_idx = std::nullopt;
price_point->first_order_idx = valid_indices[0];
price_point->last_order_idx = valid_indices.back();
}
public:
HashOrderBook(std::string symbol, const Price& tick_size)
: symbol_(std::move(symbol)),
tick_size_(tick_size),
orders_(10000),
next_slot_(0) {}
bool add_order(const OrderT& order) {
if (order_index_.find(order.id) != order_index_.end()) {
throw std::runtime_error("Order already exists");
}
if (next_slot_ >= orders_.size()) {
orders_.resize(orders_.size() * 2);
}
orders_[next_slot_] = OrderNode<OrderT>(order);
order_index_[order.id] = next_slot_;
link_order_to_price_level(next_slot_, order.price, order.side);
update_best_price(order.price, order.side);
next_slot_++;
return true;
}
bool remove_order(OrderId order_id) {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return false;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return false;
// 保存价格和方向用于后续更新
const auto& order = orders_[idx]->order;
Price price = order.price;
Side side = order.side;
// 标记为已删除
orders_[idx] = std::nullopt;
order_index_.erase(it);
// 重建该价格级别的链表
rebuild_price_level(price, side);
update_best_price(price, side);
return true;
}
bool modify_order(OrderId order_id, Quantity new_quantity) {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return false;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return false;
auto& order = orders_[idx]->order;
order.quantity = new_quantity;
if (new_quantity.is_zero()) {
return remove_order(order_id);
}
return true;
}
const OrderT* find_order(OrderId order_id) const {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return nullptr;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return nullptr;
return &(orders_[idx]->order);
}
std::vector<const OrderT*> match_orders(Side side, const Price& price,
Quantity quantity) {
std::vector<const OrderT*> matched_orders;
matched_orders.reserve(16);
Quantity remaining = quantity;
if (side == Side::Buy) {
if (!best_ask_.has_value()) return matched_orders;
// 收集并排序所有卖价
std::vector<size_t> sorted_asks;
sorted_asks.reserve(asks_.size());
for (const auto& [idx, _] : asks_) {
sorted_asks.push_back(idx);
}
std::sort(sorted_asks.begin(), sorted_asks.end()); // 从小到大排序
size_t price_tick = price_to_index(price);
for (size_t tick : sorted_asks) {
if (tick > price_tick || remaining.is_zero()) break;
auto it = asks_.find(tick);
if (it == asks_.end()) continue;
auto& price_point = it->second;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value() && !remaining.is_zero()) {
auto& node = orders_[current_idx].value();
auto& order = node.order;
if (order.quantity.raw() > 0) {
Quantity fill_qty =
(remaining < order.quantity) ? remaining : order.quantity;
remaining -= fill_qty;
matched_orders.push_back(&order);
// 更新订单数量
Quantity new_qty = order.quantity - fill_qty;
if (new_qty.is_zero()) {
// 需要删除订单
order_index_.erase(order.id);
orders_[current_idx] = std::nullopt;
} else {
order.quantity = new_qty;
}
}
current_idx = node.next_idx.value_or(orders_.size());
}
// 重建该价格级别的链表
if (!remaining.is_zero()) {
rebuild_price_level(index_to_price(tick), Side::Sell);
}
}
} else {
// 卖单：收集并排序所有买价
if (!best_bid_.has_value()) return matched_orders;
std::vector<size_t> sorted_bids;
sorted_bids.reserve(bids_.size());
for (const auto& [idx, _] : bids_) {
sorted_bids.push_back(idx);
}
std::sort(sorted_bids.rbegin(), sorted_bids.rend()); // 从大到小排序
size_t price_tick = price_to_index(price);
for (size_t tick : sorted_bids) {
if (tick < price_tick || remaining.is_zero()) break;
auto it = bids_.find(tick);
if (it == bids_.end()) continue;
auto& price_point = it->second;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value() && !remaining.is_zero()) {
auto& node = orders_[current_idx].value();
auto& order = node.order;
if (order.quantity.raw() > 0) {
Quantity fill_qty =
(remaining < order.quantity) ? remaining : order.quantity;
remaining -= fill_qty;
matched_orders.push_back(&order);
// 更新订单数量
Quantity new_qty = order.quantity - fill_qty;
if (new_qty.is_zero()) {
// 需要删除订单
order_index_.erase(order.id);
orders_[current_idx] = std::nullopt;
} else {
order.quantity = new_qty;
}
}
current_idx = node.next_idx.value_or(orders_.size());
}
// 重建该价格级别的链表
if (!remaining.is_zero()) {
rebuild_price_level(index_to_price(tick), Side::Buy);
}
}
}
// 更新最佳价格
update_best_price(best_bid_.value_or(Price::from_raw(0)), Side::Buy);
update_best_price(best_ask_.value_or(Price::from_raw(0)), Side::Sell);
return matched_orders;
}
std::optional<Price> best_bid() const { return best_bid_; }
std::optional<Price> best_ask() const { return best_ask_; }
// 获取市场深度
std::pair<std::vector<std::pair<Price, Quantity>>,
std::vector<std::pair<Price, Quantity>>>
market_depth(size_t levels) {
std::vector<std::pair<Price, Quantity>> bid_depth;
std::vector<std::pair<Price, Quantity>> ask_depth;
bid_depth.reserve(levels);
ask_depth.reserve(levels);
// 获取买方深度
if (best_bid_.has_value() && !bids_.empty()) {
std::vector<size_t> sorted_bids;
sorted_bids.reserve(bids_.size());
for (const auto& [idx, _] : bids_) {
sorted_bids.push_back(idx);
}
std::sort(sorted_bids.rbegin(), sorted_bids.rend()); // 从大到小排序
for (size_t tick : sorted_bids) {
if (bid_depth.size() >= levels) break;
auto it = bids_.find(tick);
if (it == bids_.end()) continue;
auto& price_point = it->second;
if (price_point.empty()) continue;
Quantity total_qty;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value()) {
total_qty += orders_[current_idx]->order.quantity;
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
bid_depth.emplace_back(index_to_price(tick), total_qty);
}
}
// 获取卖方深度
if (best_ask_.has_value() && !asks_.empty()) {
std::vector<size_t> sorted_asks;
sorted_asks.reserve(asks_.size());
for (const auto& [idx, _] : asks_) {
sorted_asks.push_back(idx);
}
std::sort(sorted_asks.begin(), sorted_asks.end()); // 从小到大排序
for (size_t tick : sorted_asks) {
if (ask_depth.size() >= levels) break;
auto it = asks_.find(tick);
if (it == asks_.end()) continue;
auto& price_point = it->second;
if (price_point.empty()) continue;
Quantity total_qty;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value()) {
total_qty += orders_[current_idx]->order.quantity;
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
ask_depth.emplace_back(index_to_price(tick), total_qty);
}
}
return {bid_depth, ask_depth};
}
};
} // namespace lob
方案3：树订单簿 (Tree-based LOB) - 推荐方案
核心:
- 使用
std::map（红黑树）存储价格点 - Key = Tick数量（自动排序），Value = PricePoint
- 利用红黑树的有序性和范围查询
优点:
- 自动排序 - Key自动按升序排列
- 高效范围查询 - lower_bound/upper_bound提供O(log n)范围查询
- 内存高效 - 仅存储有订单的价格点
- 确定性性能 - O(log n)比HashMap的期望O(1)更可预测
- 无价格范围限制
缺点:
- 查找稍慢 - O(log n) vs Vec的O(1)
- 插入开销 - 需要维护树结构
- 链式树内存不连续，缓存不友好
#include <algorithm>
#include <cmath>
#include <map>
#include <stdexcept>
#include <vector>
#include "common.h"
namespace lob {
// 树订单簿实现（推荐）
template <typename OrderT>
class TreeOrderBook {
private:
std::string symbol_;
Price tick_size_;
// 使用std::map替代unordered_map，自动排序
std::map<size_t, PricePoint>
bids_; // Key: tick index (sorted), Value: PricePoint
std::map<size_t, PricePoint> asks_;
std::vector<std::optional<OrderNode<OrderT>>> orders_;
std::unordered_map<OrderId, size_t> order_index_;
// 缓存
std::optional<Price> best_bid_;
std::optional<Price> best_ask_;
size_t next_slot_;
size_t price_to_index(const Price& price) const {
return static_cast<size_t>(price.raw() / tick_size_.raw());
}
Price index_to_price(size_t idx) const {
return Price::from_raw(static_cast<int64_t>(idx) * tick_size_.raw());
}
PricePoint* get_or_create_price_point(const Price& price, Side side) {
size_t idx = price_to_index(price);
auto& container = (side == Side::Buy) ? bids_ : asks_;
auto it = container.find(idx);
if (it != container.end()) {
return &it->second;
} else {
auto [new_it, inserted] = container.emplace(idx, PricePoint());
return &new_it->second;
}
}
PricePoint* get_price_point(const Price& price, Side side) {
size_t idx = price_to_index(price);
auto& container = (side == Side::Buy) ? bids_ : asks_;
auto it = container.find(idx);
if (it != container.end()) {
return &it->second;
} else {
return nullptr;
}
}
void update_best_price(const Price& price, Side side) {
if (side == Side::Buy) {
if (!best_bid_.has_value() || price > best_bid_.value()) {
best_bid_ = price;
}
// 检查当前最佳价格是否还有订单
if (best_bid_.has_value() && !bids_.empty()) {
auto it = bids_.find(price_to_index(best_bid_.value()));
if (it == bids_.end() || it->second.empty()) {
// 需要查找新的最佳买价 - 取map中的最后一个元素
if (!bids_.empty()) {
auto last_it = bids_.end();
--last_it;
while (last_it != bids_.begin() && last_it->second.empty()) {
--last_it;
}
if (!last_it->second.empty()) {
best_bid_ = index_to_price(last_it->first);
} else {
best_bid_ = std::nullopt;
}
} else {
best_bid_ = std::nullopt;
}
}
}
} else {
if (!best_ask_.has_value() || price < best_ask_.value()) {
best_ask_ = price;
}
// 检查当前最佳价格是否还有订单
if (best_ask_.has_value() && !asks_.empty()) {
auto it = asks_.find(price_to_index(best_ask_.value()));
if (it == asks_.end() || it->second.empty()) {
// 需要查找新的最佳卖价 - 取map中的第一个元素
if (!asks_.empty()) {
auto first_it = asks_.begin();
while (first_it != asks_.end() && first_it->second.empty()) {
++first_it;
}
if (first_it != asks_.end() && !first_it->second.empty()) {
best_ask_ = index_to_price(first_it->first);
} else {
best_ask_ = std::nullopt;
}
} else {
best_ask_ = std::nullopt;
}
}
}
}
}
void link_order_to_price_level(size_t order_idx, const Price& price,
Side side) {
auto price_point = get_or_create_price_point(price, side);
if (!price_point) return;
if (price_point->empty()) {
price_point->first_order_idx = order_idx;
price_point->last_order_idx = order_idx;
} else {
size_t last_idx = price_point->last_order_idx.value();
orders_[last_idx]->next_idx = order_idx;
price_point->last_order_idx = order_idx;
}
}
// 重建价格点的订单链表
void rebuild_price_level(const Price& price, Side side) {
auto price_point = get_price_point(price, side);
if (!price_point || price_point->empty()) return;
size_t current_idx = price_point->first_order_idx.value();
std::vector<size_t> valid_indices;
while (current_idx < orders_.size() && orders_[current_idx].has_value()) {
valid_indices.push_back(current_idx);
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
if (valid_indices.empty()) {
size_t idx = price_to_index(price);
if (side == Side::Buy) {
bids_.erase(idx);
} else {
asks_.erase(idx);
}
return;
}
// 重建链表
for (size_t i = 0; i < valid_indices.size() - 1; ++i) {
orders_[valid_indices[i]]->next_idx = valid_indices[i + 1];
}
orders_[valid_indices.back()]->next_idx = std::nullopt;
price_point->first_order_idx = valid_indices[0];
price_point->last_order_idx = valid_indices.back();
}
public:
TreeOrderBook(std::string symbol, const Price& tick_size)
: symbol_(std::move(symbol)),
tick_size_(tick_size),
orders_(10000),
next_slot_(0) {}
bool add_order(const OrderT& order) {
if (order_index_.find(order.id) != order_index_.end()) {
throw std::runtime_error("Order already exists");
}
if (next_slot_ >= orders_.size()) {
orders_.resize(orders_.size() * 2);
}
orders_[next_slot_] = OrderNode<OrderT>(order);
order_index_[order.id] = next_slot_;
link_order_to_price_level(next_slot_, order.price, order.side);
update_best_price(order.price, order.side);
next_slot_++;
return true;
}
bool remove_order(OrderId order_id) {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return false;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return false;
// 保存价格和方向用于后续更新
const auto& order = orders_[idx]->order;
Price price = order.price;
Side side = order.side;
// 标记为已删除
orders_[idx] = std::nullopt;
order_index_.erase(it);
// 重建该价格级别的链表
rebuild_price_level(price, side);
update_best_price(price, side);
return true;
}
bool modify_order(OrderId order_id, Quantity new_quantity) {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return false;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return false;
auto& order = orders_[idx]->order;
order.quantity = new_quantity;
if (new_quantity.is_zero()) {
return remove_order(order_id);
}
return true;
}
const OrderT* find_order(OrderId order_id) const {
auto it = order_index_.find(order_id);
if (it == order_index_.end()) return nullptr;
size_t idx = it->second;
if (idx >= orders_.size() || !orders_[idx].has_value()) return nullptr;
return &(orders_[idx]->order);
}
// 匹配订单 - 利用std::map的有序性
std::vector<const OrderT*> match_orders(Side side, const Price& price,
Quantity quantity) {
std::vector<const OrderT*> matched_orders;
matched_orders.reserve(16);
Quantity remaining = quantity;
if (side == Side::Buy) {
if (!best_ask_.has_value()) return matched_orders;
size_t max_tick = price_to_index(price);
auto it = asks_.lower_bound(price_to_index(best_ask_.value()));
// 从最低卖价开始遍历
while (it != asks_.end() && it->first <= max_tick &&
!remaining.is_zero()) {
auto& price_point = it->second;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value() && !remaining.is_zero()) {
auto& node = orders_[current_idx].value();
auto& order = node.order;
if (order.quantity.raw() > 0) {
Quantity fill_qty =
(remaining < order.quantity) ? remaining : order.quantity;
remaining -= fill_qty;
matched_orders.push_back(&order);
// 更新订单数量
Quantity new_qty = order.quantity - fill_qty;
if (new_qty.is_zero()) {
// 需要删除订单
order_index_.erase(order.id);
orders_[current_idx] = std::nullopt;
} else {
order.quantity = new_qty;
}
}
current_idx = node.next_idx.value_or(orders_.size());
}
// 保存当前迭代器位置，因为rebuild可能修改容器
auto current_it = it++;
// 重建该价格级别的链表
if (orders_.size() > current_idx && orders_[current_idx]) {
rebuild_price_level(index_to_price(current_it->first), Side::Sell);
}
// 检查是否需要删除空价格点
if (current_it->second.empty()) {
asks_.erase(current_it);
}
}
} else {
// 卖单：从最高买价开始（反向遍历）
if (!best_bid_.has_value()) return matched_orders;
size_t min_tick = price_to_index(price);
auto it = bids_.upper_bound(price_to_index(best_bid_.value()));
if (it != bids_.begin())
--it;
else if (it == bids_.end())
return matched_orders;
// 从最高买价开始向下遍历
while (it != bids_.end() && it->first >= min_tick &&
!remaining.is_zero()) {
auto& price_point = it->second;
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() &&
orders_[current_idx].has_value() && !remaining.is_zero()) {
auto& node = orders_[current_idx].value();
auto& order = node.order;
if (order.quantity.raw() > 0) {
Quantity fill_qty =
(remaining < order.quantity) ? remaining : order.quantity;
remaining -= fill_qty;
matched_orders.push_back(&order);
// 更新订单数量
Quantity new_qty = order.quantity - fill_qty;
if (new_qty.is_zero()) {
// 需要删除订单
order_index_.erase(order.id);
orders_[current_idx] = std::nullopt;
} else {
order.quantity = new_qty;
}
}
current_idx = node.next_idx.value_or(orders_.size());
}
// 保存当前迭代器位置，因为rebuild可能修改容器
auto current_it = it;
if (it != bids_.begin())
--it;
else {
// 处理边界情况
it = bids_.end();
}
// 重建该价格级别的链表
if (orders_.size() > current_idx && orders_[current_idx]) {
rebuild_price_level(index_to_price(current_it->first), Side::Buy);
}
// 检查是否需要删除空价格点
if (current_it->second.empty()) {
bids_.erase(current_it);
}
}
}
// 更新最佳价格
update_best_price(best_bid_.value_or(Price::from_raw(0)), Side::Buy);
update_best_price(best_ask_.value_or(Price::from_raw(0)), Side::Sell);
return matched_orders;
}
std::optional<Price> best_bid() const { return best_bid_; }
std::optional<Price> best_ask() const { return best_ask_; }
// 市场深度查询 - 树结构的独特优势
std::pair<std::vector<std::pair<Price, Quantity>>,
std::vector<std::pair<Price, Quantity>>>
market_depth(size_t levels) {
std::vector<std::pair<Price, Quantity>> bid_levels;
std::vector<std::pair<Price, Quantity>> ask_levels;
bid_levels.reserve(levels);
ask_levels.reserve(levels);
// 收集买单深度 - 从最高价开始
auto bid_it = bids_.rbegin(); // 从最高价开始
while (bid_it != bids_.rend() && bid_levels.size() < levels) {
auto& price_point = bid_it->second;
Quantity total_qty = Quantity::from_raw(0);
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() && orders_[current_idx].has_value()) {
total_qty += orders_[current_idx]->order.quantity;
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
if (!total_qty.is_zero()) {
Price price = index_to_price(bid_it->first);
bid_levels.emplace_back(price, total_qty);
}
++bid_it;
}
// 收集卖单深度 - 从最低价开始
auto ask_it = asks_.begin(); // 从最低价开始
while (ask_it != asks_.end() && ask_levels.size() < levels) {
auto& price_point = ask_it->second;
Quantity total_qty = Quantity::from_raw(0);
size_t current_idx = price_point.first_order_idx.value();
while (current_idx < orders_.size() && orders_[current_idx].has_value()) {
total_qty += orders_[current_idx]->order.quantity;
current_idx = orders_[current_idx]->next_idx.value_or(orders_.size());
}
if (!total_qty.is_zero()) {
Price price = index_to_price(ask_it->first);
ask_levels.emplace_back(price, total_qty);
}
++ask_it;
}
return {bid_levels, ask_levels};
}
};
} // namespace lob
方案4：循环数组订单簿(Circular array)
数据结构
-
价格层级（PriceLevel）：管理单价格下的订单
-
存储：循环数组（大小
2^15 = 32768），存[订单ID, 未结数量]，无效订单标记为(-1, -1)。 - 指针：
start/end界定有效订单区间，遍历自动跳过无效项。 -
优化：位运算替代模运算（
v & (size-1)）。 -
订单簿（OrderBook）：管理单方向（买/卖）的所有价格层级
-
存储：循环数组（大小
2^8 = 256）存PriceLevel，absl::flat_hash_map映射价格→数组索引。 -
指针：
start/end界定有效价格区间，买单簿优先匹配start指向的最高价格。 -
订单索引（OrderIndex）：O(1) 定位订单
-
存储：开放地址哈希表（
absl::flat_hash_map），Key=订单ID。 - 合并索引：
Value为位移合并值（高8位=价格层级索引 | 低15位=订单索引），解析时反向位运算。
压缩优化机制
- 触发条件：
start/end区间内无效项占比 > 配置阈值（如 50%）。 -
操作步骤：
-
将有效项移至数组头部，紧凑排列；
- 重置
start/end指针； -
关键：批量更新
OrderIndex中的索引映射（因订单/价格层级索引改变）。 -
权衡：避免频繁触发，平衡“遍历空洞开销”与“压缩+更新索引开销”。
| 操作 | 时间复杂度 | 核心优化点 |
|---|---|---|
| 订单插入 | O(1) |
循环数组 end 位置插入，位运算模运算 |
| 订单取消 | O(1) |
哈希表查索引，仅标记无效 |
| 订单匹配 | O(N) |
遍历 [start..end]，自动跳过无效项 |
| 数组压缩 | O(N) |
阈值触发，需同步更新索引 |
#include <algorithm>
#include <iostream>
#include <optional>
#include <stdexcept>
#include <vector>
#include "absl/container/flat_hash_map.h"
#include "common.h"
namespace lob {
// ====================== 循环数组式订单簿完整实现 ======================
template <typename OrderT>
class CircularArrayOrderBook {
private:
// ====================== 配置常量 ======================
static constexpr size_t PRICE_LEVEL_ARRAY_SIZE =
1 << 8; // 价格层级循环数组大小：2^8 = 256
static constexpr size_t ORDER_ARRAY_SIZE =
1 << 15; // 单价格订单循环数组大小：2^15 = 32768
static constexpr uint32_t PRICE_LEVEL_INDEX_MASK =
0xFF; // 价格层级索引位掩码（高8位）
static constexpr uint32_t ORDER_INDEX_MASK =
0x7FFF; // 订单索引位掩码（低15位）
static constexpr size_t PRICE_LEVEL_INDEX_SHIFT = 15; // 价格层级索引位移位数
static constexpr double COMPACTION_THRESHOLD =
0.5; // 压缩触发阈值：无效项占比 > 50%
// ====================== 核心数据结构定义 ======================
// 1. 价格层级（PriceLevel）：管理单价格下的订单
struct PriceLevel {
// 存储：循环数组，存 [订单ID, 未结数量]，无效订单标记为 (INVALID_ORDER_ID,
// 0)
std::vector<std::pair<OrderId, Quantity>> orders;
// 指针：start/end 界定有效订单区间（左闭右开）
size_t start = 0;
size_t end = 0;
// 统计：区间内无效订单数量（用于触发压缩）
size_t invalid_count = 0;
// 该价格层级的价格值（用于压缩时更新索引）
Price price;
PriceLevel()
: orders(ORDER_ARRAY_SIZE, {INVALID_ORDER_ID, Quantity::from_raw(0)}) {}
};
// 2. 订单簿（OrderBook）：管理单方向（买/卖）的所有价格层级
struct BookSide {
// 存储：循环数组存 PriceLevel
std::vector<PriceLevel> price_levels;
// 映射：absl::flat_hash_map 映射 价格→数组索引
absl::flat_hash_map<Price, size_t> price_to_idx;
// 指针：start/end 界定有效价格区间（左闭右开）
size_t start = 0;
size_t end = 0;
// 统计：区间内无效价格层级数量
size_t invalid_price_count = 0;
// 方向：买/卖
Side side;
// 最佳价格缓存
std::optional<Price> best_price;
explicit BookSide(Side s) : price_levels(PRICE_LEVEL_ARRAY_SIZE), side(s) {}
};
// ====================== 核心成员变量 ======================
std::string symbol_;
Price tick_size_;
BookSide bids_; // 买单簿（Side::Buy）
BookSide asks_; // 卖单簿（Side::Sell）
// 3. 订单索引（OrderIndex）：O(1) 定位订单
// 存储：开放地址哈希表（absl::flat_hash_map），Key=订单ID
// Value：位移合并值（高8位=价格层级索引 | 低15位=订单索引）
absl::flat_hash_map<OrderId, uint32_t> order_index_;
// 完整订单存储（补充设计：PriceLevel 仅存ID和数量，完整订单存此处）
absl::flat_hash_map<OrderId, OrderT> order_store_;
// ====================== 辅助工具：位运算优化 ======================
// 位运算替代模运算（要求 size 为 2 的幂）
static size_t circular_mod(size_t v, size_t size) { return v & (size - 1); }
// 合并索引：高8位=价格层级索引 | 低15位=订单索引
static uint32_t encode_index(size_t price_level_idx, size_t order_idx) {
return (static_cast<uint32_t>(price_level_idx & PRICE_LEVEL_INDEX_MASK)
<< PRICE_LEVEL_INDEX_SHIFT) |
(static_cast<uint32_t>(order_idx & ORDER_INDEX_MASK));
}
// 解析合并索引：反向位运算拆分
static void decode_index(uint32_t encoded, size_t& price_level_idx,
size_t& order_idx) {
price_level_idx =
(encoded >> PRICE_LEVEL_INDEX_SHIFT) & PRICE_LEVEL_INDEX_MASK;
order_idx = encoded & ORDER_INDEX_MASK;
}
// 获取循环数组区间内的元素数量（左闭右开）
static size_t circular_range_size(size_t start, size_t end, size_t size) {
return (end >= start) ? (end - start) : (size - start + end);
}
// ====================== 价格顺序维护辅助（买单从高到低，卖单从低到高）
// ====================== 比较两个价格在指定方向下的优先级（返回 true 表示
// price1 优先于 price2）
static bool price_has_higher_priority(Side side, const Price& price1,
const Price& price2) {
return (side == Side::Buy) ? (price1 > price2) : (price1 < price2);
}
// 在 BookSide 中查找新价格的插入位置（维护价格顺序）
size_t find_price_insert_position(BookSide& side, const Price& price) {
if (side.start == side.end) {
return side.end; // 空区间，直接插入 end
}
// 遍历有效区间，找到第一个优先级低于新价格的位置
size_t current = side.start;
while (current != side.end) {
const PriceLevel& level = side.price_levels[current];
// 跳过无效价格层级（已被标记但未压缩）
if (level.price.raw() ==
0) { // 假设无效价格的 raw() 为 0，需根据实际 Price 类型调整
current = circular_mod(current + 1, PRICE_LEVEL_ARRAY_SIZE);
continue;
}
if (price_has_higher_priority(side.side, price, level.price)) {
return current; // 插入到当前位置之前（即当前位置作为新的
// start/插入点）
}
current = circular_mod(current + 1, PRICE_LEVEL_ARRAY_SIZE);
}
return side.end; // 新价格优先级最低，插入到 end
}
// ====================== 最佳价格更新逻辑 ======================
void update_best_price_on_add(BookSide& side, const Price& price) {
if (!side.best_price.has_value() ||
price_has_higher_priority(side.side, price, side.best_price.value())) {
side.best_price = price;
}
}
void update_best_price_on_remove(BookSide& side, const Price& removed_price) {
if (!side.best_price.has_value() ||
side.best_price.value() != removed_price) {
return; // 移除的不是最佳价格，无需更新
}
// 重新遍历有效区间，查找新的最佳价格
side.best_price = std::nullopt;
size_t current = side.start;
while (current != side.end) {
const PriceLevel& level = side.price_levels[current];
if (level.price.raw() != 0 &&
circular_range_size(level.start, level.end, ORDER_ARRAY_SIZE) >
level.invalid_count) {
// 找到第一个有效价格层级（因区间按优先级排序，第一个即为最佳）
side.best_price = level.price;
break;
}
current = circular_mod(current + 1, PRICE_LEVEL_ARRAY_SIZE);
}
}
// ====================== 压缩优化机制：订单层级压缩 ======================
void try_compact_price_level(BookSide& side, PriceLevel& level,
size_t price_level_idx) {
size_t total_count =
circular_range_size(level.start, level.end, ORDER_ARRAY_SIZE);
if (total_count == 0) return;
double invalid_ratio =
static_cast<double>(level.invalid_count) / total_count;
if (invalid_ratio <= COMPACTION_THRESHOLD) return;
// 压缩步骤 a：将有效项移至数组头部，紧凑排列
std::vector<std::pair<OrderId, Quantity>> compacted;
compacted.reserve(total_count - level.invalid_count);
std::vector<OrderId> valid_order_ids; // 记录有效订单ID，用于批量更新索引
size_t current = level.start;
while (current != level.end) {
auto& [order_id, qty] = level.orders[current];
if (order_id != INVALID_ORDER_ID) {
compacted.emplace_back(order_id, qty);
valid_order_ids.push_back(order_id);
}
current = circular_mod(current + 1, ORDER_ARRAY_SIZE);
}
// 将紧凑后的有效项写回数组头部
for (size_t i = 0; i < compacted.size(); ++i) {
level.orders[i] = compacted[i];
}
// 标记剩余位置为无效
for (size_t i = compacted.size(); i < level.end; ++i) {
level.orders[i] = {INVALID_ORDER_ID, Quantity::from_raw(0)};
}
// 压缩步骤 b：重置 start/end 指针
level.start = 0;
level.end = compacted.size();
level.invalid_count = 0;
// 压缩步骤 c：关键——批量更新 OrderIndex 中的索引映射（订单索引改变）
for (size_t new_order_idx = 0; new_order_idx < valid_order_ids.size();
++new_order_idx) {
OrderId order_id = valid_order_ids[new_order_idx];
uint32_t new_encoded = encode_index(price_level_idx, new_order_idx);
order_index_[order_id] = new_encoded;
}
}
// ======================
// 压缩优化机制：价格层级压缩（补充设计，与订单层级逻辑对称）
// ======================
void try_compact_book_side(BookSide& side) {
size_t total_count =
circular_range_size(side.start, side.end, PRICE_LEVEL_ARRAY_SIZE);
if (total_count == 0) return;
double invalid_ratio =
static_cast<double>(side.invalid_price_count) / total_count;
if (invalid_ratio <= COMPACTION_THRESHOLD) return;
// 压缩步骤 a：将有效价格层级移至数组头部，紧凑排列
std::vector<std::pair<Price, size_t>>
old_to_new_idx; // 记录旧索引→新索引映射
std::vector<PriceLevel> compacted_levels;
compacted_levels.reserve(total_count - side.invalid_price_count);
size_t current = side.start;
while (current != side.end) {
PriceLevel& level = side.price_levels[current];
if (level.price.raw() != 0) { // 有效价格层级
old_to_new_idx.emplace_back(level.price, compacted_levels.size());
compacted_levels.push_back(std::move(level));
// 重置原位置为无效
side.price_levels[current] = PriceLevel();
}
current = circular_mod(current + 1, PRICE_LEVEL_ARRAY_SIZE);
}
// 将紧凑后的价格层级写回数组头部
for (size_t i = 0; i < compacted_levels.size(); ++i) {
side.price_levels[i] = std::move(compacted_levels[i]);
}
// 压缩步骤 b：重置 start/end 指针
side.start = 0;
side.end = compacted_levels.size();
side.invalid_price_count = 0;
// 压缩步骤 c：批量更新索引映射
// 1. 更新 price_to_idx（价格→新索引）
for (auto& [price, new_idx] : old_to_new_idx) {
side.price_to_idx[price] = new_idx;
}
// 2. 更新 order_index_（所有订单的高8位价格层级索引）
for (auto& [order_id, encoded] : order_index_) {
size_t old_price_idx, order_idx;
decode_index(encoded, old_price_idx, order_idx);
// 查找旧价格对应的新索引
Price price =
side.price_levels[old_price_idx]
.price; // 这里原位置已被移动，需通过 order_store_ 查价格
// 通过 order_store_ 获取订单价格，再查 price_to_idx 得新索引
auto it_order = order_store_.find(order_id);
if (it_order == order_store_.end()) continue;
Price order_price = it_order->second.price;
auto it_price = side.price_to_idx.find(order_price);
if (it_price == side.price_to_idx.end()) continue;
size_t new_price_idx = it_price->second;
// 更新编码
order_index_[order_id] = encode_index(new_price_idx, order_idx);
}
}
// ====================== 内部操作：获取或创建价格层级（解决循环数组有序插入）
// ======================
PriceLevel& get_or_create_price_level(BookSide& side, const Price& price,
size_t& out_idx) {
// 1. 价格已存在：直接返回
auto it = side.price_to_idx.find(price);
if (it != side.price_to_idx.end()) {
out_idx = it->second;
return side.price_levels[out_idx];
}
// 2. 价格不存在：先检查并触发压缩（避免数组满了无法插入）
try_compact_book_side(side);
// 3. 检查循环数组是否已满（压缩后仍满则报错，2^8=256 足够容纳活跃价格层级）
if (circular_mod(side.end + 1, PRICE_LEVEL_ARRAY_SIZE) == side.start) {
throw std::runtime_error(
"Price level array full, compaction failed to free space");
}
// 4. 找到严格按优先级排序的插入位置
size_t insert_pos = find_price_insert_position(side, price);
// 5. 在循环数组中腾出 insert_pos 位置：将 [insert_pos, end)
// 的元素向后移动一位 循环数组移动需分“非环绕段”和“环绕段”处理
size_t current = side.end;
while (current != insert_pos) {
// 计算前一个位置（循环数组中向左移动一位）
size_t prev = circular_mod(current - 1, PRICE_LEVEL_ARRAY_SIZE);
// 移动元素：prev → current
side.price_levels[current] = std::move(side.price_levels[prev]);
// 更新被移动价格的 price_to_idx 映射
const Price& moved_price = side.price_levels[current].price;
if (moved_price.raw() != 0) { // 跳过无效价格层级
side.price_to_idx[moved_price] = current;
// 批量更新该价格下所有订单的 order_index_（高8位价格层级索引改变）
PriceLevel& moved_level = side.price_levels[current];
size_t order_current = moved_level.start;
while (order_current != moved_level.end) {
auto& [order_id, _] = moved_level.orders[order_current];
if (order_id != INVALID_ORDER_ID) {
auto it_order_idx = order_index_.find(order_id);
if (it_order_idx != order_index_.end()) {
size_t old_price_idx, order_idx;
decode_index(it_order_idx->second, old_price_idx, order_idx);
// 重新编码：高8位用新的价格层级索引 current
order_index_[order_id] = encode_index(current, order_idx);
}
}
order_current = circular_mod(order_current + 1, ORDER_ARRAY_SIZE);
}
}
current = prev;
}
// 6. 在 insert_pos 位置初始化新的价格层级
PriceLevel& new_level = side.price_levels[insert_pos];
new_level = PriceLevel(); // 重置为干净状态
new_level.price = price;
new_level.start = 0;
new_level.end = 0;
new_level.invalid_count = 0;
// 7. 更新元数据
side.price_to_idx[price] = insert_pos;
out_idx = insert_pos;
side.end =
circular_mod(side.end + 1, PRICE_LEVEL_ARRAY_SIZE); // 扩展有效区间
// 8. 更新最佳价格
update_best_price_on_add(side, price);
return new_level;
}
public:
// ====================== 构造函数 ======================
CircularArrayOrderBook(std::string symbol, const Price& tick_size)
: symbol_(std::move(symbol)),
tick_size_(tick_size),
bids_(BookSide(Side::Buy)),
asks_(BookSide(Side::Sell)) {}
// ====================== 核心操作：订单插入（O(1)，严格对应设计）
// ======================
bool add_order(const OrderT& order) {
if (order_index_.contains(order.id)) {
throw std::runtime_error("Order already exists");
}
// 选择买卖方向
BookSide& side = (order.side == Side::Buy) ? bids_ : asks_;
// 1. 获取或创建价格层级
size_t price_level_idx;
PriceLevel& level =
get_or_create_price_level(side, order.price, price_level_idx);
// 2. 循环数组 end 位置插入订单
size_t order_idx = level.end;
level.orders[order_idx] = {order.id, order.quantity};
level.end = circular_mod(level.end + 1, ORDER_ARRAY_SIZE);
// 3. 存储完整订单 & 建立合并索引
order_store_[order.id] = order;
order_index_[order.id] = encode_index(price_level_idx, order_idx);
// 4. 尝试压缩价格层级（仅检查，不满足阈值则跳过）
try_compact_price_level(side, level, price_level_idx);
try_compact_book_side(side);
return true;
}
// ====================== 核心操作：订单取消（O(1)，严格对应设计）
// ======================
bool remove_order(OrderId order_id) {
auto it_index = order_index_.find(order_id);
if (it_index == order_index_.end()) return false;
// 1. 解析合并索引，定位价格层级和订单位置
size_t price_level_idx, order_idx;
decode_index(it_index->second, price_level_idx, order_idx);
// 2. 确定买卖方向（通过订单存储获取价格和方向）
auto it_order = order_store_.find(order_id);
if (it_order == order_store_.end()) return false;
const OrderT& order = it_order->second;
BookSide& side = (order.side == Side::Buy) ? bids_ : asks_;
PriceLevel& level = side.price_levels[price_level_idx];
// 3. 仅标记无效（不立即删除）
auto& [stored_id, stored_qty] = level.orders[order_idx];
if (stored_id == INVALID_ORDER_ID) return false; // 已被标记
stored_id = INVALID_ORDER_ID;
stored_qty = Quantity::from_raw(0);
level.invalid_count++;
// 4. 清理索引和订单存储
order_index_.erase(it_index);
Price removed_price = order.price;
order_store_.erase(it_order);
// 5. 检查价格层级是否为空，标记为无效（用于价格层级压缩）
size_t total_orders =
circular_range_size(level.start, level.end, ORDER_ARRAY_SIZE);
if (level.invalid_count == total_orders) {
level.price = Price::from_raw(0); // 标记为无效价格
side.invalid_price_count++;
side.price_to_idx.erase(removed_price);
update_best_price_on_remove(side, removed_price);
}
// 6. 尝试压缩
try_compact_price_level(side, level, price_level_idx);
try_compact_book_side(side);
return true;
}
// ====================== 核心操作：订单修改（补充设计）
// ======================
bool modify_order(OrderId order_id, Quantity new_quantity) {
auto it_index = order_index_.find(order_id);
if (it_index == order_index_.end()) return false;
// 解析索引，定位订单
size_t price_level_idx, order_idx;
decode_index(it_index->second, price_level_idx, order_idx);
auto it_order = order_store_.find(order_id);
if (it_order == order_store_.end()) return false;
OrderT& order = it_order->second;
BookSide& side = (order.side == Side::Buy) ? bids_ : asks_;
PriceLevel& level = side.price_levels[price_level_idx];
// 更新数量
order.quantity = new_quantity;
level.orders[order_idx].second = new_quantity;
// 数量为0时移除订单
if (new_quantity.is_zero()) {
return remove_order(order_id);
}
return true;
}
// ====================== 核心操作：订单查找（O(1)） ======================
const OrderT* find_order(OrderId order_id) const {
auto it = order_store_.find(order_id);
if (it == order_store_.end()) return nullptr;
return &(it->second);
}
// ====================== 核心操作：订单匹配（O(N)，严格对应设计）
// ======================
std::vector<const OrderT*> match_orders(Side side, const Price& price,
Quantity quantity) {
std::vector<const OrderT*> matched_orders;
matched_orders.reserve(16);
Quantity remaining = quantity;
// 选择对手方簿
BookSide& opposite_side = (side == Side::Buy) ? asks_ : bids_;
if (!opposite_side.best_price.has_value()) return matched_orders;
// 检查价格是否可匹配（买单价格 >= 对手最佳卖价，卖单价格 <= 对手最佳买价）
bool can_match = (side == Side::Buy)
? (price >= opposite_side.best_price.value())
: (price <= opposite_side.best_price.value());
if (!can_match) return matched_orders;
// 遍历有效价格区间 [start..end]，自动跳过无效项
size_t current_price_idx = opposite_side.start;
while (current_price_idx != opposite_side.end && !remaining.is_zero()) {
PriceLevel& level = opposite_side.price_levels[current_price_idx];
// 跳过无效价格层级
if (level.price.raw() == 0) {
current_price_idx =
circular_mod(current_price_idx + 1, PRICE_LEVEL_ARRAY_SIZE);
continue;
}
// 检查价格是否在匹配范围内
bool price_in_range =
(side == Side::Buy) ? (level.price <= price) : (level.price >= price);
if (!price_in_range) break; // 价格区间按优先级排序，超出范围后无需继续
// 遍历该价格下的有效订单区间 [start..end]
size_t current_order_idx = level.start;
while (current_order_idx != level.end && !remaining.is_zero()) {
auto& [order_id, qty] = level.orders[current_order_idx];
// 自动跳过无效项
if (order_id == INVALID_ORDER_ID || qty.is_zero()) {
current_order_idx =
circular_mod(current_order_idx + 1, ORDER_ARRAY_SIZE);
continue;
}
// 匹配逻辑
auto it_order = order_store_.find(order_id);
if (it_order == order_store_.end()) {
current_order_idx =
circular_mod(current_order_idx + 1, ORDER_ARRAY_SIZE);
continue;
}
const OrderT& matched_order = it_order->second;
Quantity fill_qty = (remaining < qty) ? remaining : qty;
remaining -= fill_qty;
matched_orders.push_back(&matched_order);
// 更新订单数量
Quantity new_qty = qty - fill_qty;
if (new_qty.is_zero()) {
// 标记为无效
level.orders[current_order_idx] = {INVALID_ORDER_ID,
Quantity::from_raw(0)};
level.invalid_count++;
order_index_.erase(order_id);
order_store_.erase(order_id);
} else {
level.orders[current_order_idx].second = new_qty;
order_store_[order_id].quantity = new_qty;
}
current_order_idx =
circular_mod(current_order_idx + 1, ORDER_ARRAY_SIZE);
}
// 检查价格层级是否为空
size_t total_orders =
circular_range_size(level.start, level.end, ORDER_ARRAY_SIZE);
Price level_price = level.price;
if (level.invalid_count == total_orders) {
level.price = Price::from_raw(0);
opposite_side.invalid_price_count++;
opposite_side.price_to_idx.erase(level_price);
update_best_price_on_remove(opposite_side, level_price);
}
// 尝试压缩
try_compact_price_level(opposite_side, level, current_price_idx);
try_compact_book_side(opposite_side);
current_price_idx =
circular_mod(current_price_idx + 1, PRICE_LEVEL_ARRAY_SIZE);
}
return matched_orders;
}
// ====================== 辅助接口：最佳价格 & 市场深度 ======================
std::optional<Price> best_bid() const { return bids_.best_price; }
std::optional<Price> best_ask() const { return asks_.best_price; }
std::pair<std::vector<std::pair<Price, Quantity>>,
std::vector<std::pair<Price, Quantity>>>
market_depth(size_t levels) {
std::vector<std::pair<Price, Quantity>> bid_depth;
std::vector<std::pair<Price, Quantity>> ask_depth;
bid_depth.reserve(levels);
ask_depth.reserve(levels);
// 买方深度（从最佳买价开始遍历）
if (bids_.best_price.has_value()) {
size_t current = bids_.start;
while (current != bids_.end && bid_depth.size() < levels) {
const PriceLevel& level = bids_.price_levels[current];
if (level.price.raw() != 0) {
Quantity total_qty;
size_t curr_order = level.start;
while (curr_order != level.end) {
const auto& [id, qty] = level.orders[curr_order];
if (id != INVALID_ORDER_ID) {
total_qty += qty;
}
curr_order = circular_mod(curr_order + 1, ORDER_ARRAY_SIZE);
}
if (!total_qty.is_zero()) {
bid_depth.emplace_back(level.price, total_qty);
}
}
current = circular_mod(current + 1, PRICE_LEVEL_ARRAY_SIZE);
}
}
// 卖方深度（从最佳卖价开始遍历）
if (asks_.best_price.has_value()) {
size_t current = asks_.start;
while (current != asks_.end && ask_depth.size() < levels) {
const PriceLevel& level = asks_.price_levels[current];
if (level.price.raw() != 0) {
Quantity total_qty;
size_t curr_order = level.start;
while (curr_order != level.end) {
const auto& [id, qty] = level.orders[curr_order];
if (id != INVALID_ORDER_ID) {
total_qty += qty;
}
curr_order = circular_mod(curr_order + 1, ORDER_ARRAY_SIZE);
}
if (!total_qty.is_zero()) {
ask_depth.emplace_back(level.price, total_qty);
}
}
current = circular_mod(current + 1, PRICE_LEVEL_ARRAY_SIZE);
}
}
return {bid_depth, ask_depth};
}
};
} // namespace lob