unordered_multimap Nutzung und Betreiber zu überschreiben

Question

Ich brauche eine unordered_multimap für meinen Hinweis Objekte zu verwenden und die Schlüssel das measureNumber Mitglied meiner Objekte sein. Ich versuche es zu implementieren as shown here, aber ich stecke fest.

Zunächst einmal verstehe ich nicht, warum ich die operator== überschreiben muss, bevor ich es verwenden kann. Ich bin auch verwirrt darüber, warum ich einen Hash brauche und wie ich ihn implementiere. In this example here, keines dieser beiden Dinge ist getan.

auf dem ersten Beispiel So basiert, ist es das, was ich habe:

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; 
} 

Ich weiß nicht, wie wenn der Hash-Teil zu implementieren. Irgendwelche Ideen?

Answer 1

std::multimap basiert auf einem sortierten Binärbaum, der zum Sortieren der Knoten eine Kleiner-als-Operation verwendet.

basiert auf einer Hash-Tabelle, die Hash- und Gleichheitsoperationen verwendet, um die Knoten zu organisieren, ohne sie zu sortieren.

Das Sortieren oder Hashing basiert auf den Schlüsselwerten. Wenn die Objekte die Schlüssel sind, müssen Sie diese Operationen definieren. Wenn die Schlüssel vordefiniert sind wie int oder string, müssen Sie sich keine Sorgen machen.

Das Problem mit Ihrem Pseudocode ist, dass measureNumber ist privat, so dass der Benutzer von Note kann nicht einfach den Schlüssel für die Karte angeben. Ich würde empfehlen, measureNumber öffentlich zu machen oder das Design zu überdenken. (Ist Maßzahl wirklich einen guten Schlüsselwert? Ich vermute, diese musikalische Notation ist.)

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

Die Objekte können Tasten und Werte zur gleichen Zeit, wenn Sie std::multiset oder std::unordered_multiset verwenden, in denen Falls Sie die Operatorüberladung (und möglicherweise Hash) definieren möchten. Wenn operator== (oder operator<) ist eine Elementfunktion, so ist die linke Seite wird this und die rechte Seite wird das einzige Argument. Normalerweise sollten diese Funktionen nicht Mitglieder sein. Also würden Sie

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; 
} 

Diese Klasse mit std::multiset verwendet werden könnten. Um eine grundlegende Suche durchführen, können Sie ein Dummy-Objekt mit nicht initialisierten Werten mit Ausnahme von measureNumber konstruieren - funktioniert dies nur für einfache Objekttypen.

Answer 2

Ich brauche eine unordered_multimap für meine Notiz Objekte und die Schlüssel werden das measureNumber Mitglied meiner Objekte sein.

OK - ich bin mir nicht sicher, ob Sie nach einem multiset, sind unordered_multiset, multimap oder unordered_multimap. Ich weiß, dass Ihr Titel unordered_multimap bezieht, aber der Link zur Verfügung gestellt, führt zu unordered_multiset. Es gibt eine Vielzahl von Überlegungen, die berücksichtigt werden sollten, wenn ein Behälter der Wahl, aber zweite Mutmaßung, die das beste Ergebnis erzielt, ohne Profilierung wird ein riskantes Geschäft ist.

Ich verstehe nicht, warum ich den Operator == überschreiben muss, bevor ich es verwenden kann. Ich bin auch verwirrt darüber, warum ich einen Hash brauche und wie man ihn implementiert. In diesem Beispiel wird keines dieser beiden Dinge getan.

Sie müssen die operator== und std::hash, wie sie von unordered_multimap und unordered_multiset intern verwendet sind. In dem Beispiel, mit dem Sie verbunden sind, ist der Schlüssel vom Typ int, daher sind operator== und std::hash<int> bereits definiert. Wenn Sie Note als Schlüssel verwenden, müssen Sie diese selbst definieren.

Ich würde empfehlen, mit einem multiset starten, wenn Sie die Elemente nicht häufig ändern müssen. Wenn Sie tun möchten in der Lage sein, Note s ohne Löschen und Einfügen zu ändern, würde ich empfehlen, measureNumber als Mitglied von Note zu entfernen und eine multimap<int, Note> verwenden.

Wenn Sie glauben, dass eine unordered_ Version Ihres Containers Ihren Anforderungen besser entspricht, haben Sie immer noch die set vs map Wahl. Wenn Sie unordered_multimap<int, Note> (measureNumber von Note entfernt) auswählen, ist der Schlüssel wie in Ihrem verknüpften Beispiel int. Sie müssen also nichts Besonderes definieren, damit dies funktioniert. Wenn Sie measureNumber als ein Mitglied von Note behalten und unordered_multiset<Note> verwenden, dann ist Note der Schlüssel und Sie müssen weitere Arbeit, z.

#include <functional> 
#include <unordered_set> 

class Note; // Forward declaration to allow specialisation of std::hash<> 

namespace std { 
template<> 
class hash<Note> { 
public: 
    size_t operator()(const Note &) const; // declaration of operator() to 
              // allow befriending by Note 
}; 
} 

class Note { 
private: 
    int measureNumber; 
public: 
    // functions befriended to allow access to measureNumber 
    friend bool operator== (const Note &, const Note &); 
    friend std::size_t std::hash<Note>::operator()(const Note &) const; 
}; 

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

std::size_t std::hash<Note>::operator()(const Note &note) const { 
    return std::hash<int>()(note.measureNumber); 
} 

Damit können Sie std::unordered_multiset<Note> erstellen und verwenden. Allerdings bin ich mir nicht sicher, dass wirklich ist, was Sie brauchen; Sie könnten sogar finden, dass eine sortierte std::vector<Note> für Sie am besten ist. Weitere Forschung und Überlegungen, wie Sie Ihren Container zusammen mit Profiling verwenden, sollte die beste Antwort geben.