1

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

我不想使用任何其他结构。我想用std::unordered_map！

根据答案更新创建了这样的结构：

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;
4

2 回答 2

7

无法满足您的确切要求：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 将其大致实现为 astd::set<Value>和 a std::unordered_map<Key, set<Value>::iterator>。这意味着查找和擦除都是O(1). 擦除可能是O(1)因为unordered_map::erase(value)将迭代器返回到setandstd::set<Value>::erase(iterator)中O(1)。

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

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

于 2014-01-22T09:21:10.640 回答
-1

你可以写一个包装器。有了它，您可以获得每个插入/删除并可以保留最小/最大值。

#pragma once

#include <unordered_map>

using std::unordered_map;

class my_unordered_map
{
public:
    void insert(int key, int value)
    {
        _map[key] = value;
        if (_max < value)
            _max = value;
        if (_min> value)
            _min = value;
    }
    int get(int key)
    {
        auto it = _map.find(key);
        if (it != _map.end())
            return it->second;
        return 0; // or some error handling here.
    }
    int getMin()
    {
        return _min;
    }
    int getMax()
    {
        return _max;
    }
    // more functionality here.
private:
    unordered_map<int, int> _map;
    int _min = 0;
    int _max = 0;
};
于 2014-01-22T09:01:35.423 回答