3

ペアを保存するには、ある種の優先キューが必要<key, value>です。値は一意ですが、キーは一意ではありません。次の操作を実行します (最も一般的なものを最初に)。

  1. ランダム挿入;
  2. 最小のキーを持つすべての要素を取得 (および削除) します。
  3. ランダムな削除 (値による);

std::priority_queueヘッドの取り外ししか対応していないので使えません。

今のところ、私は unsorted を使用していstd::listます。挿入は、新しい要素を後ろに押すだけで実行されます (O(1))。操作 2list::sortは、実際の取得を実行する前に、(O(N*logN)) でリストを並べ替えます。ただし、除去は O(n) であり、少しコストがかかります。

より良いデータ構造のアイデアはありますか?

4

6 に答える 6

4

コレクションの順序を逆にできますか。つまり、順番に保存できます<value, key>か?

次に、削除のための挿入（コレクション全体のトラバース）と値のランダムな削除（上記のマップのキーとなる）のためstd::mapに時間を使用することができます。O(logn)O(n)O(logn)

mapツリーの代わりにハッシュに基づく実装 ( のような)を見つけることができればstd::map、時間はさらに良くなります: O(1), O(n), O(1).

于 2010-04-01T14:39:58.347 に答える
4

注文が必要な場合は、注文コンテナを使用してください。後で仕分けの費用を払っても意味がありません。

現在の解決策は次のとおりです。

  • 挿入O(1)
  • 検索O(N log N)
  • 削除O(N)(そこに別のインデックスを保持せずに取得できるのと同じくらい良いです)

を使用するだけで、次のstd::multi_mapことができます。

  • 挿入O(log N)
  • 検索O(log N)<- ずっといいですね。範囲の終わりを見つける必要があります
  • 除去O(N)

今、あなたは少し良くすることができますstd::map< key, std::vector<value> >：

  • 個別のキーの数でO(log M)ある挿入M
  • 検索O(1)(begin一定時間償却されることが保証されています)
  • 除去O(N)

ランダムな削除を実際にプッシュすることはできません...そこに別のインデックスを保持したくない場合を除きます。例えば：

typedef std::vector<value_type> data_value_t;
typedef std::map<key_type, data_value_t> data_t;

typedef std::pair<data_t::iterator,size_t> index_value_t;
  // where iterator gives you the right vector and size_t is an index in it

typedef std::unordered_map<value_type, index_value_t> index_t;

しかし、この 2 番目のインデックスを最新の状態に保つと、エラーが発生しやすくなります...そして、他の操作を犠牲にして行われます! たとえば、この構造では、次のようになります。

  • 挿入O(log M)--> ハッシュ マップへの挿入の複雑さはO(1)
  • 取得--> ベクトル内のすべての値O(N/M)のインデックスを作成する必要があります。N/M
  • 削除O(N/M)--> ハッシュ マップO(1)での検索、逆参照O(1)、ベクトルからの削除O(N/M)。ベクトルの内容の約半分をシフトする必要があるためです。a を使用すると ... がlist得られO(1)ますが、高速ではない可能性があります (メモリのトレードオフのため、要素の数によって異なります)。

また、ハッシュ マップの複雑さは償却されることにも注意してください。負荷率が大きくなりすぎたために再割り当てをトリガーします。この特定の挿入には非常に長い時間がかかります。

私は本当にstd::map<key_type, std::vector<value_type> >あなたの代わりに行きたいです。それはお金に見合う最高の価値です。

于 2010-04-01T17:06:00.717 に答える
1

Visual Studio を使用している場合は、hash_multimap があります。また、Boost には順不同のマルチマップがあることも付け加えておく必要があります。順序付きマルチマップ、 STL マルチマップ、または順序付きマルチセットSTLマルチセットが必要な場合

于 2010-04-01T14:38:28.090 に答える
0

私がよく理解していれば、パフォーマンスの目標は（1）と（3）を高速化することであり、（2）はそれほど重要ではありません。この場合、値が一意であることを考えると、なぜ、だけを持ってstd::set<value>、（2）を順次検索するのではないでしょうか。（1）と（3）にはO（log n）があり、（2）にはO（n）があります。さらに良いことに、STLにが含まれている場合、std::hash_set（1）と（3）のO（1）に近くなります。

（2）に対してO（n）よりも優れたものが必要な場合、1つの代替手段は、優先度付きキューのセットを用意することです。

于 2010-04-01T15:01:40.397 に答える
0

std::multimap はあなたが探しているもののようです。

オブジェクトをキー順に格納し、最小/最大のキー値 (begin()、rbegin()) および指定されたキー (equal_range、lower_bound、upper_bound) を持つすべてのオブジェクトを取得できるようにします。

(編集: アイテムが数個しかない場合、たとえば 30 個未満の場合は、deque または vector を使用した場合のパフォーマンスもテストする必要があります)

于 2010-04-01T14:52:44.627 に答える
0

わかりましたので、私は多くのオプションをテストし、Matthieu M.のアイデアに基づいたものに行き着きました。私は現在、削除に役立つ to 自体を含む aを使用しstd::map<key_type, std::list<value_type> >ています。value_typestd::list<value_type>::iterator

削除では、ベクトルが空であるかどうかを確認する必要があります。これは、mapクエリと、場合によっては への呼び出しを意味しますerase。最悪の場合の複雑さは、キーがO(logN)挿入、O(1)取得、およびO(logN)削除で異なる場合です。テスト マシンの他の代替手段と比較して、非常に良い実験結果が得られました。

a を使用するstd::vectorと、理論的な複雑さ (キーが同一の場合、O(N) の最悪の場合の削除) と私が行ってきた実験の両方の点で効率が低下します。

于 2010-04-02T12:24:10.473 に答える