4

O(lgn) または O(1) で一意のキーを検索し、O(1) で最大値を取得するキー値データ構造を実装する必要があります。私は考えています

boost::bimap< unordered_set_of<key> ,multiset_of<value> >

キーと値のデータ セットに重複したキーがないことに注意してください。ただし、2 つのキーが同じ値を持つ場合があります。したがって、値を格納するために multiset を使用しました。

キーと値のペアを頻繁に挿入/削除/更新する必要がある

どのように聞こえますか？

4

2 に答える 2

2

それはあなたが何をしたいかによります。したがって、繰り返しの構築で最大値を取得するためにそれを使用したいことは明らかです。

質問 1:キーでも要素にアクセスしますか?

  • はいの場合は、次の 2 つの解決策が考えられます。

    1. 使用boost::bimap- 対数ランタイムを使用した簡単でテスト済みのソリューション。

    2. std::map（またはキーアクセスによりさらに高速化するためstd::unordered_map）とヒープ実装（std::priority_queue<std::map<key, value>::iterator>+カスタムコンパレーターなど）を含むカスタムコンテナーを作成し、それらを同期させます。これは難しい方法ですが、おそらく高速です。両方のほとんどの操作は O(logn) (挿入、get&pop max、キーによる取得、削除) ですが、定数が重要になる場合があります。キー操作によるアクセスを使用std::unordered_mapしていますが、O(1) になります。

      新しいコンテナーのテストも作成し、最もよく使用する操作に合わせて最適化することができます。

  • no の場合、実際には最大値を使用して要素を使用してアクセスするだけです

    質問 2:要素をランダムに挿入/削除/更新しますか?それとも、最初にすべての要素を 1 回で挿入してから、1 つずつ削除しますか?

    • ランダムな挿入/削除/更新用std::priority_queue<std::pair<value, key>>

    • 最初に要素を入れてから、それらを 1 つずつ削除する場合は、最初の削除操作の前にandstd::vector<std::pair<value, key>>とit を使用します。std::sort()要素を実際に削除するのではなく、繰り返し処理するだけです。

于 2013-01-23T12:14:40.800 に答える
1

std::mapとを使用してこれを構築できstd::setます。

  1. 実際の値を保持する 1 つのマップstd::map<key, value> m;。これは、値が保存される場所です。マップへの要素の挿入は O(log n) です。

  2. マップを指すイテレータのセット。このセットは、それぞれのマップ エントリの値によって並べ替えられます。つまりstd::set<std::map<key, value>::iterator, CompareBySecondField> s;、(未テスト):

    template <class It>
struct CompareBySecondField : std::binary_function<It, It, bool> {
    bool operator() ( const T &lhs, const T &rhs ) const {
        return lhs->second > rhs->second;
    }
};

    次に、 を使用して、最大値を持つマップ エントリへのイテレータを取得できます*s.begin();。

これはかなり簡単に作成できますが、要素を追加/削除するたびに両方のコンテナーを更新する必要があります。

于 2013-01-23T13:06:58.983 に答える