std :: unordered_map - 如何随时"跟踪"最大/最小键

Question

我有std::unordered_map<int, int>.我不想使用树或其他任何其他结构导致延迟要求.但是在任何时候我都需要知道当前的最大键和最小键.我怎样才能做到这一点？分布不均匀,而是经常删除和插入max和min.因此,我需要比"只删除当前最大/最小值时扫描整个地图以获得新的最大值/分钟"更聪明的东西.

我不想使用任何其他结构.我想用std::unordered_map!

UPD根据答案创建这样的结构:

struct OrderBookItem {
    int64_t price;
    int32_t lots;
};

typedef multi_index_container
    <OrderBookItem, indexed_by<

    hashed_unique<
    BOOST_MULTI_INDEX_MEMBER(OrderBookItem,int64_t,price)
    >,

    ordered_unique<
    BOOST_MULTI_INDEX_MEMBER(OrderBookItem,int64_t,price),
    std::greater<int64_t>
    >

    >> OrderBookContainer;

Answer 1

无法满足您的确切要求:std::unordered_map快速(即O(1)插入/删除/查找)因为它没有对其元素进行排序.这意味着找到最小/最大值O(N).

通过std::map插入/擦除/查找(包括查找最小/最大)所支付的订购价格全部变为O(log N).

如果您不介意使用Boost,可以查看Boost.MultiIndex库.这允许您同时通过多个接口访问您的数据.它是一个极其通用和高性能的库,也可用于MRU缓存数据结构(它还结合了快速访问和订购跟踪).

您的主要std::unordered_map接口由hashed_unique索引提供,您可以在其中使用identity函数对象(由Boost.MultiIndex提供).您的辅助界面将模仿std::set.这允许查找最小/最大的价值O(1)作为时间*begin()和*rbegin().

您可以通过添加ordered_unique带有用户定义MyOrder函数对象的索引来计算您想要用于订购它们的任何条件.小代码示例(在boost::任何地方省略命名空间)

using MyContainer = multi_index_container<
    Item,
    indexed_by<
        hashed_unique<identity<Item>>, // O(1) erasure/lookup, O(log N) insertion
        ordered_unique<MyOrder<Item>>  // track minimum/maximum in O(log N)
    >
>;

在幕后,Boost.MultiIndex大致将其实现为std::set<Value>a std::unordered_map<Key, set<Value>::iterator>.这意味着查找和删除都是O(1).擦除可能是O(1)因为unordered_map::erase(value)将迭代器返回到set和std::set<Value>::erase(iterator)中O(1).

但是,插入仍然存在O(log N),因为您无法避免在更短的时间内在有序序列中查找新插入值的等级.

与std::map查找/擦除相比,这种改进仅花费每个元素空间开销的几个指针.