20

編集: multimap に重複 キーを含めることができない理由を尋ねているわけではないことに注意してください。

重複するキーと値のペアを許可する multimap の背後にある理論的根拠は何ですか? (ないキー)

#include <map>
#include <string>
#include <iostream>

int
main(int argc, char** argv)
{
    std::multimap<std::string, std::string> m;
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "C"));
    std::cout << m.size() << std::endl;
    return 0;
}

これは 3 を出力しましたが、これは私を少し驚かせました。

直観的には、 ( とは対照的に) が常にマップを変更するとは限らないC++ のstd::map動作とは一致しません。insertoperator[]

その背後には根拠がありますか、それとも恣意的なものですか？

4

7 に答える 7

19

マルチマップには、キーを並べる述語しかありません。値が等しいかどうかを判断する方法はありません。値「A」は値「a」の複製ですか? 値の 2 番目の述語がなければ、何とも言えません。したがって、マルチマップで重複する値について話すことさえ意味がありません。

ペアを格納し、ペアの両方の部分の一意性を強制するコンテナが必要な場合は、 を参照してboost::multi_index_containerください。非常に柔軟ですが、結果として多くの引数が必要になります。

于 2011-04-12T08:31:21.697 に答える
12

編集:この回答は、現在の質問にはもう回答していません。賛成票が多かったのでそのままにしておくので、一部の人にとっては役立つはずです。

マルチインはmultimap、同じキーが複数回発生する可能性があることを表しています。

標準は、値として使用される型に制限を設けていないため、それoperator==()が定義されていると想定することはできません。コードの結果が operator==() が定義されているかどうかに依存することを望まないため、これは使用されません。

std::multimapの代わりにはなりませんstd::map。お気づきのように、同じキーを複数回挿入すると動作が異なります。std::mapの動作が必要な場合は、 を使用しますstd::map。

もありstd::multisetます。

合理的な理由: 同じキーの古いエントリをすべて保持したい場合があります。[未定: ここに例を挿入]

個人的には、ほとんど使っていませんstd::multimap。同じキーに対して複数のエントリが必要な場合は、通常、std::map<std::vector<T> >.

于 2011-04-12T08:14:11.900 に答える
2

値は互いに比較可能である必要がないため、値の重複が許可されます。コンテナーは値をコピーする以外に何もできません。これにより、 のような型が有効になりますmultimap< int, my_class >。

重複するキーと値のペアが望ましくない場合は、set< pair< T, U > >と を使用lower_boundして、特定のキーに最初に一致するものを見つけます。

于 2011-04-12T08:39:18.757 に答える
1

ご存知のmultimapように、複数のキーを持つことができます。値の比較可能性に制約を課さないため、値が 2 倍になっていないかどうかを確認することはできません。

キーと値のペアではなく重複キーを許可する辞書データ構造が必要な場合は、値が比較可能であることを確認する必要があります。

正方形のフィールドの 2D 世界があり、アイテムをフィールドに置くことができる、ある種のゲームがあるとしましょう。を持つことができますmultimap<Field, Item>。これにより、フィールドに2つの同一のアイテムを保持できます。ここではアイテムを比較する必要はありません。

于 2011-04-12T08:21:07.563 に答える
1

私の推論は、マルチマップは値ではなくキーの検索/挿入に基づいているということです。したがって、重複キーの値が同じかどうかは、要素が挿入されているときに関係ありません。

23.3.2クラステンプレートのマルチマップ

1 マルチマップは、同等のキー (同じキー値の複数のコピーを含む可能性がある) をサポートし、キーに基づいて別の型 T の値を高速に取得できる連想コンテナーの一種です。

于 2011-04-12T09:53:47.413 に答える
0

「マルチマップ」は、単純な「マップ」とは異なり、「複数の」キーをサポートするためのものです。複数のキーを使用できるため、それらの値を気にする必要がないため、例では 3 つの要素を示しています。もう 1 つの違いは、 for を使用できないことoperator []ですmultimap。

于 2011-04-12T08:25:40.280 に答える