c++ - 「マルチセット」と「マルチマップ」 - ポイントは何ですか?

Question

multiset質問が述べているように... s / multimapsについての要点がわかりません。

それで、目的は何ですか？

score 45 · Accepted Answer

いくつかの使用例:

マルチマップ

郵便番号をキーにして、その郵便番号を持っている人全員
口座 ID をキーとして、その個人/口座のすべてのオープン注文
辞書、キーワードごとにさまざまな説明

マルチセット

本質的には、キーと整数カウントを持つマップです。

ショップの在庫、すべての製品にはキーがあり、まだ利用可能な量が値です
ショップの累積販売データ。製品が販売されるたびに、製品 ID がマルチセットに追加され、それによって販売額が増加します。

score 4 · Accepted Answer

ベクトル/リスト (またはその他のコンテナー) よりもマルチセットを使用することの最も重要な利点は、検索操作の時間の複雑さです。multiset の平均ケース時間の複雑さは O(logn) で、unordered_multiset は O(1) です。同じことが multimap と ordered_multimap にも当てはまります。

score 2 · Accepted Answer

ほとんどの場合、キーが一意であるが、一意ではない場合がある場合に、マルチマップが役立つ 1 つの例です。

たとえば、ハッシュをキーとして使用するキャッシュクラスを作成していたとします。ほとんどの場合、2 つの異なるオブジェクトは同じハッシュを持たないため、キーは一意になります。ただし、さまざまなオブジェクトでハッシュ衝突が発生する可能性があるため、その状況をカバーするにはマルチマップが必要です。

もう 1 つの例は、一意でないインデックス (データベースなど) です。

マルチセットについては、あまり役に立たないと思います。私が考えることができる唯一のことは、一種の自動的にソートされたリストとして使用することです.

score 2 · Accepted Answer

multiset または multimap は、特定のアイテムが複数存在する可能性がある場合にのみ使用されます。たとえば、本の索引を作成したいとします。テキストをスキャンし、本当に一般的な意味のない単語 (「a」、「an」、「the」など) をすべて捨ててから、残りのすべてのリストを作成し、それぞれが本のどこにあるかをリストします。発生した。

かなりの数の単語が複数のページに表示されます。その場合、1 つの単語から別のページに複数のエントリがマッピングされます。これを処理する 1 つの方法は、単語からページ番号へのマルチマップです。

score 1 · Accepted Answer

http://www.cplusplus.com/reference/stl/multimap/

マップは、キー値とマップされた値の組み合わせによって形成される要素を格納する連想コンテナーの一種であり、マップコンテナーによく似ていますが、異なる要素が同じキー値を持つことができます。

要素がキーを共有できる一種のレジストリです。企業や従業員を思い浮かべることができます。住所がキーで、従業員が値です。

score 1 · Accepted Answer

ウィキペディアには、用途について次のように書かれています。

学生が複数のクラスに同時に登録される可能性がある学生登録システムでは、キーが学生 ID で値がコース ID である、コース内の学生の登録ごとに関連付けが存在する場合があります。学生が 3 つのコースに登録されている場合、同じキーを含む 3 つの関連付けが存在します。

書籍のインデックスは、特定のインデックスタームの任意の数の参照を報告する場合があるため、インデックスタームから任意の数の参照場所へのマルチマップとしてコード化される場合があります。

score -2 · Accepted Answer

ツリーのような構造を使用したい場合はいつでもマルチマップを使用してください。

c++ - 「マルチセット」と「マルチマップ」 - ポイントは何ですか?

7 に答える 7

Related

Reference