1

私は持っていstd::unordered_map<int, int>ます。ツリーなどの他の構造は使用したくありませんが、遅延要件が発生するものは何もありません。しかし、いつでも現在の最大キーと最小キーを知る必要があります。どうやってやるの？分布は均一ではなく、代わりに最大値と最小値が頻繁に削除および挿入されます。したがって、「現在の最大値/最小値が削除されたときに、マップ全体をスキャンして新しい最大値/最小値を取得する」よりもスマートなものが必要です。

私は他の構造を使用したくありません。使いたい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;
4

2 に答える 2

7

あなたの正確な要件を満たすことはできません:要素を順序付けしないため、std::unordered_map高速です(つまり、挿入/消去/検索)。O(1)これは、最小/最大を見つけるのにかかることを意味しますO(N)。

std::mapその挿入/消去/ルックアップ (最小値/最大値の検索を含む)によって支払われる注文の価格はすべて になりO(log N)ます。

Boost を使用してもかまわない場合は、Boost.MultiIndexライブラリをご覧ください。これにより、複数のインターフェイスから同時にデータにアクセスできます。これは、MRU キャッシュ データ構造 (高速アクセスと順序付けの追跡も組み合わせます) にも使用できる、非常に用途が広く高性能なライブラリです。

主要なstd::unordered_mapインターフェイスは、関数オブジェクト (Boost.MultiIndex によって提供される)hashed_uniqueを使用するインデックスによって提供されます。identityセカンダリ インターフェイスは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>ますstd::unordered_map<Key, set<Value>::iterator>。これは、ルックアップと消去の両方がO(1). がイテレータをand isに返すO(1)ため、消去が行われる可能性があります。unordered_map::erase(value)setstd::set<Value>::erase(iterator)O(1)

ただし、O(log N)順序付けられたシーケンス内で新しく挿入された値のランクを短時間で見つけることは避けられないため、挿入は残ります。

ルックアップ/消去と比較したこの改善では、要素スペース オーバーヘッドごとに数個のポインターしかstd::mapかかりません。

于 2014-01-22T09:21:10.640 に答える