如何使用双搜索键分别操作对象？std::multimap高效删除订单方法

先整理你提供的基础代码（修正了插入语句的语法错误）：

class Order
{
public:
    Order(int id, double p) : order_id(id), price(p) {}
    int get_order_id() const { return order_id; }  // 改为const成员函数，更符合场景
    double get_price() const { return price; }

private:
    int order_id;
    double price;
};

std::multimap<double, Order> order_map;
Order a(1, 1.25);
Order b(2, 1.75);
Order c(3, 1.75);
Order d(4, 2.25);
Order e(5, 1.25);
order_map.insert(std::make_pair(a.get_price(), a));
order_map.insert(std::make_pair(b.get_price(), b));
order_map.insert(std::make_pair(c.get_price(), c));
order_map.insert(std::make_pair(d.get_price(), d));
order_map.insert(std::make_pair(e.get_price(), e));

要实现无需遍历即可按订单ID删除，同时保留按价格搜索的能力，最直接的高效方案是新增一个哈希表作为订单ID的索引，关联到multimap中对应元素的迭代器。具体实现如下：

核心思路 #

• 用std::multimap<double, Order>维持订单按价格升序排列，满足按价格搜索的需求（依然用equal_range）。
• 用std::unordered_map<int, std::multimap<double, Order>::iterator>建立订单ID到multimap迭代器的映射，这样通过ID可以O(1)时间定位到目标订单，再O(1)时间删除multimap中的元素（关联容器删除迭代器的时间复杂度是常数级）。

完整实现代码 #

#include <iostream>
#include <map>
#include <unordered_map>

class Order
{
public:
    Order(int id, double p) : order_id(id), price(p) {}
    int get_order_id() const { return order_id; }
    double get_price() const { return price; }

private:
    int order_id;
    double price;
};

// 主容器：按价格升序存储订单
std::multimap<double, Order> price_ordered_orders;
// 索引容器：按订单ID快速定位到主容器的迭代器
std::unordered_map<int, std::multimap<double, Order>::iterator> id_to_order_iter;

// 插入订单函数
void insert_order(const Order& order) {
    // 插入到主容器，获取迭代器
    auto insert_result = price_ordered_orders.insert(std::make_pair(order.get_price(), order));
    // 将订单ID和迭代器存入索引容器
    id_to_order_iter[order.get_order_id()] = insert_result.first;
}

// 按订单ID删除订单函数
bool delete_order_by_id(int order_id) {
    // 查找索引容器中是否存在该ID
    auto id_iter = id_to_order_iter.find(order_id);
    if (id_iter == id_to_order_iter.end()) {
        return false; // 订单不存在
    }

    // 从主容器中删除对应元素
    price_ordered_orders.erase(id_iter->second);
    // 从索引容器中删除该ID的映射
    id_to_order_iter.erase(id_iter);
    return true;
}

// 按价格搜索订单的示例函数
void search_orders_by_price(double target_price) {
    auto range = price_ordered_orders.equal_range(target_price);
    std::cout << "价格为 " << target_price << " 的订单：\n";
    for (auto iter = range.first; iter != range.second; ++iter) {
        std::cout << "订单ID：" << iter->second.get_order_id() << "\n";
    }
}

int main() {
    // 插入测试订单
    insert_order(Order(1, 1.25));
    insert_order(Order(2, 1.75));
    insert_order(Order(3, 1.75));
    insert_order(Order(4, 2.25));
    insert_order(Order(5, 1.25));

    // 按价格搜索
    search_orders_by_price(1.75);

    // 删除订单ID为3的订单
    if (delete_order_by_id(3)) {
        std::cout << "\n成功删除订单ID 3\n";
    }

    // 再次搜索价格1.75的订单
    search_orders_by_price(1.75);

    return 0;
}

关键说明 #

1. 时间复杂度：插入、删除、按ID查找都是O(1)（哈希表操作）+ O(log n)（multimap插入，因为multimap是平衡树结构）；按价格搜索依然是O(k + log n)，k是匹配价格的订单数量，完全满足高效需求。
2. 迭代器有效性：multimap中，除了被删除的元素迭代器失效外，其他元素的迭代器、指针、引用都保持有效，所以索引容器中的迭代器不会因为其他订单的插入/删除而失效，无需额外维护。
3. 可选调整：如果需要订单ID也保持有序，可以把std::unordered_map换成std::map<int, ...>，时间复杂度会变成O(log n)，但依然远低于遍历整个容器。

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