c++ - 使用指针在常数时间内从集合中删除

Question

假设我有一个表单结构。

struct Order {
    int id;
    double price;
    // more data
}

ID 是唯一标识符。现在我要跟踪这些 Orders在OrderBook .我需要提供一个插入(创建一个新的订单对象)和一个删除方法(删除具有特定 ID 的订单)。这个想法当然是尽可能高效。

struct OrderBook {
    unordered_map<int, Order> orders; // ID -> Orders
    // ...
}

此外，我必须能够快速访问当前 OrderBook 中价格最高的订单。

我正在考虑包含一对 pair<double, id> (对于价格和 ID)在数据结构中按字典顺序排序(可能是 set？)。插入将是高效的 (O(log n))，但由于数据结构是按价格排序的，而不是按 ID 排序的，因此从该数据结构中查找和删除元素将在 (O(n)) 中进行。那么我可以在指向 Price/ID 对的 Order 对象中存储一个指针吗？但这仍然不会在集合中删除它吗？有什么想法吗？

Answer 1

have fast access to the Order with the highest price

什么是“快”？持续的？ O(logn)?

这是经典的时间内存权衡。您可以拥有另一种数据结构“最大堆”，它保存指向您的对象的指针，并具有通过指向对象的价格比较两个指针的比较函数。