unordered_multimapの使用法と演算子の上書き

Question

私のNoteオブジェクトにはunordered_multimapを使用する必要があり、そのキーは自分のオブジェクトのmeasureNumberメンバーになります。私はそれを実装しようとしているas shown hereしかし、私は立ち往生しています。

まず、operator==を上書きしなければならない理由が分かりません。私はなぜハッシュが必要か、それを実装する方法についても混乱しています。 In this example here、これらの2つのことは実行されません。

だから、最初の例に基づいて、これは私が持っているものです。

class Note { 
private: 
    int measureNumber; 
public: 
    inline bool operator== (const Note &noteOne, const Note &noteTwo); 
} 

inline bool Note::operator ==(const Note& noteOne, const Note& noteTwo){ 
    return noteOne.measureNumber == noteTwo.measureNumber; 
} 

私もハッシュ部分を実装する方法がわかりません。何か案は？

Answer 1

std::multimapはソートされたバイナリツリーに基づいています。ソートされたバイナリツリーは、より小さい演算を使用してノードをソートします。

std::unordered_multimapは、ハッシュおよび等価演算を使用してソートせずにノードを整理するハッシュテーブルに基づいています。

ソートまたはハッシングは、キー値に基づいています。オブジェクトがキーの場合は、これらの操作を定義する必要があります。キーがintまたはstringのような事前定義されたタイプである場合は、それを心配する必要はありません。

擬似コードの問題は、measureNumberがプライベートなので、Noteのユーザーはマップにキーを簡単に指定できません。 measureNumberを公開したり、デザインを再考することをおすすめします。 （本当に良いキー値はありますか？私は、これは楽譜で推測している小節番号です。）

std::multimap< int, Note > notes; 
Note myNote(e_sharp, /* octave */ 3, /* measure */ 5); 
notes.insert(std::make_pair(myNote.measureNumber, myNote)); 

あなたがstd::multisetやstd::unordered_multisetを使用している場合、オブジェクトはその中で、キーを同時にと値をすることができオペレータのオーバーロードを定義したい場合があります（場合によってはハッシュ）。 operator==（またはoperator<）がメンバー関数である場合、左辺はthisになり、右辺が唯一の引数になります。通常、これらの機能はメンバー以外の友達である必要があります。だから、あなたは

class Note { 
private: 
    int measureNumber; 
public: 
    friend bool operator< (const Note &noteOne, const Note &noteTwo); 
} 

inline bool operator <(const Note& noteOne, const Note& noteTwo){ 
    return noteOne.measureNumber < noteTwo.measureNumber; 
} 

このクラスはstd::multisetで使用することができなければなりません。基本ルックアップを実行するには、measureNumber以外の初期化されていない値を持つダミーオブジェクトを作成できます。これは単純なオブジェクト型に対してのみ機能します。

Answer 2

私のNoteオブジェクトにはunordered_multimapを使用する必要があり、キー は自分のオブジェクトのmeasureNumberメンバーになります。

OK - 私はあなたがmultiset、unordered_multiset、multimap、またはunordered_multimap後にしているかどうかはわかりません。私はあなたのタイトルがunordered_multimapを指していることを知っていますが、あなたが提供したリンクはunordered_multisetにつながります。コンテナを選択する際に考慮する必要がある多数の考慮事項がありますが、プロファイリングなしで最高のパフォーマンスになる第2の推測は危険なビジネスです。

なぜ私は演算子==を上書きする必要があるのか​​分かりません。 なぜ私にハッシュが必要なのか、それを実装する方法についても混乱しています。 この例では、これらの2つのことは実行されていません。

彼らはunordered_multimapとunordered_multisetによって内部的に使用しているとして、あなたはoperator==とstd::hashを必要としています。リンク先の例では、キーのタイプはintなので、operator==とstd::hash<int>がすでに定義されています。 Noteをキーとして使用することを選択した場合は、これを自分で定義する必要があります。

あなたが頻繁に要素を変更する必要はありません場合、私はmultisetから始まるお勧めします。 の場合の場合、消去と挿入を行わずにNoteを変更できるようにするには、NoteのメンバーとしてのメンバーとしてmeasureNumberを削除することをおすすめします。

コンテナの​​バージョンがお客様のニーズに適していると思われる場合は、まだset対mapの選択肢があります。 unordered_multimap<int, Note>（NoteからmeasureNumberが削除されている）を選択した場合、リンクされた例のように、キーはintです。このために特別なことを定義する必要はありません。 measureNumberを会員としてNoteに設定し、unordered_multiset<Note>を使用する場合は、Noteが重要なので、さらに作業する必要があります。

std::unordered_multiset<Note>を作成して使用することができます。しかし、私はこのがであるかどうかは分かりません。あなたはソートされたstd::vector<Note>があなたのために最善であることを見つけることさえできます。あなたのコンテナをどのように使ってプロファイリングを行うのかについてのさらなる研究と考えは、最良の答えを与えるはずです。