C++中聚合含订单向量的更优实现方案咨询

本人已有多年未编写实用C++代码，近期主要使用Python/Java。现需处理金融订单簿：订单簿以std::vector存储，每个元素包含订单价格（Order Price）、订单数量（Order Size）及买卖方向（Bid/Ask），存在多个相同价格的订单条目，例如：

A : 99 : 5000     
A : 99 : 2342     
A : 98 : 6640    
A : 98 : 1800      
A : 97.78 : 2731       
A : 97 : 14704       
A : 97 : 5281      
A : 97 : 75641      
A : 96 : 3200   

其中A代表Ask（卖盘），第二列为订单价格，第三列为订单数量。需合并为如下形式：

A : 99 : 7342    
A : 98 : 8440    
A : 97.78 : 2731     
A : 97 : 95626     
A : 96 : 3200

当前使用的代码如下：

for (auto i = 0u; i + 1 < mboAggreg.size();) {
    if (mboAggreg[i].OrderPrc == mboAggreg[i + 1].OrderPrc)
    {
        mboAggreg[i].OrderSize += mboAggreg[i + 1].OrderSize;
        mboAggreg.erase(mboAggreg.begin() + i + 1);
        // dont increment index - as we may have more than two orders with the same price
    }
    else
        i++;
}   

该代码可正常运行，但希望找到更简洁、高效的C++ STL实现方式，需处理数千个高波动订单簿，对性能有较高要求。

方案1：排序+合并+清理（原地处理） #

如果允许先对订单簿排序，这个方法用STL算法实现，代码简洁且性能大幅优于原代码：

1. 排序：按「买卖方向+订单价格」排序，让同方向同价格的订单连续排列（价格排序规则可根据需求调整，比如Ask按降序、Bid按升序）；
2. 合并数量：遍历排序后的容器，合并连续的同价格订单数量；
3. 清理冗余：用std::unique标记重复元素，再用erase移除。

示例代码：

// 假设订单结构体定义如下
struct Order {
    char Side;
    double OrderPrc;
    long long OrderSize;
};

// 排序规则：先区分买卖方向，再按价格降序（适配Ask盘展示逻辑，可自行调整）
std::sort(mboAggreg.begin(), mboAggreg.end(), [](const Order& a, const Order& b) {
    if (a.Side != b.Side) return a.Side < b.Side;
    return a.OrderPrc > b.OrderPrc;
});

// 合并同价格订单，std::unique会标记重复元素
auto last = std::unique(mboAggreg.begin(), mboAggreg.end(), [](const Order& a, const Order& b) {
    if (a.Side == b.Side && a.OrderPrc == b.OrderPrc) {
        // 将后一个订单数量合并到前一个
        const_cast<Order&>(a).OrderSize += b.OrderSize;
        return true; // 标记为重复元素，后续会被清理
    }
    return false;
});

// 移除所有被标记的冗余元素
mboAggreg.erase(last, mboAggreg.end());

注：这里用const_cast是因为std::unique的谓词参数默认是const，但我们仅修改前一个元素的数量，逻辑上是安全的。若对此写法有顾虑，也可以先单独遍历合并，再调用std::unique。

方案2：用哈希表/有序映射聚合（非原地） #

如果不需要保留原订单的顺序，用std::unordered_map或std::map来统计同价格订单的总数量，是性能最优的选择之一：

用std::map（有序输出） #

适合需要保持订单按价格有序的场景，时间复杂度O(n log n)：

// 用「买卖方向+价格」作为键，统计总数量
std::map<std::pair<char, double>, long long> aggregator;

for (const auto& order : mboAggreg) {
    aggregator[{order.Side, order.OrderPrc}] += order.OrderSize;
}

// 将统计结果转换回vector
mboAggreg.clear();
for (const auto& [key, totalSize] : aggregator) {
    mboAggreg.push_back({key.first, key.second, totalSize});
}

用std::unordered_map（更快的聚合） #

如果不需要有序结果，平均时间复杂度O(n)，性能比std::map更高，但需要自定义哈希函数（因为标准库没有std::pair的默认哈希实现）：

// 自定义哈希函数，组合买卖方向和价格的哈希值
struct OrderKeyHash {
    size_t operator()(const std::pair<char, double>& key) const {
        size_t hashSide = std::hash<char>{}(key.first);
        // 注意：double作为哈希键可能有精度问题，若价格是固定小数位（如两位），建议转成long long后哈希
        size_t hashPrice = std::hash<double>{}(key.second);
        return hashSide ^ (hashPrice << 1);
    }
};

std::unordered_map<std::pair<char, double>, long long, OrderKeyHash> aggregator;

for (const auto& order : mboAggreg) {
    aggregator[{order.Side, order.OrderPrc}] += order.OrderSize;
}

// 转换回vector
mboAggreg.clear();
for (const auto& [key, totalSize] : aggregator) {
    mboAggreg.push_back({key.first, key.second, totalSize});
}

性能对比 #

• 原代码：时间复杂度O(n²)，每次erase都会移动后续元素，订单数量多时性能极差；
• 排序+合并方案：时间复杂度O(n log n)，原地处理内存占用小，代码简洁；
• std::map方案：O(n log n)，需要额外内存，但输出有序，实现最简单；
• std::unordered_map方案：平均O(n)，性能最优，但需处理哈希键的精度问题。

对于数千级别的订单处理，后三种方案都能大幅提升性能，其中排序+合并或unordered_map方案更适合高波动场景。

内容的提问来源于stack exchange，提问作者NULseg