unordered_multimap 사용 및 연산자 덮어 쓰기

Question

내 노트 개체에 unordered_multimap을 사용해야하며 키는 내 개체의 measureNumber 구성원입니다. 나는 그것을 구현하려고 노력하고있어 as shown here하지만 나는 붙어있다.

먼저 사용하기 전에 operator==을 덮어 써야한다는 것을 이해하지 못합니다. 왜 해시가 필요한지, 어떻게 구현해야하는지 혼란 스럽습니다. In this example here, 두 가지 중 하나도 수행되지 않습니다.

가 그래서 첫 번째 예에 따라, 이것은 내가 무엇을 가지고 :

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이되고 오른쪽이 유일한 인수가됩니다. 일반적으로 이러한 기능은 비회원이어야합니다. 그래서 당신은이 클래스는 std::multiset로 사용될 수

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

것이다. 기본 룩업을 수행하기 위해 measureNumber을 제외한 초기화되지 않은 값을 가진 더미 객체를 생성 할 수 있습니다. 이것은 간단한 객체 유형에서만 작동합니다.

Answer 2

나는 나의 주 개체 및 내 개체의 measureNumber 회원이됩니다 키에 대한 unordered_multimap을 사용해야합니다.

OK - 나는 당신이 multiset, unordered_multiset, multimap, 또는 unordered_multimap 후하든 확실하지 않다. 귀하의 제목이 unordered_multimap을 나타내지 만 귀하가 제공 한 링크가 unordered_multiset으로 연결됩니다. 컨테이너를 선택할 때 고려해야 할 여러 가지 고려 사항이 있지만 프로파일 링없이 최고의 성능을 발휘할 것이라는 두 번째 추측은 위험한 비즈니스입니다.

나는 연산자를 사용하기 전에 ==를 덮어 써야하는 이유를 모르겠다. 해시가 필요한 이유와 구현 방법에 대해 혼란스러워합니다. 이 예제에서는 두 가지 중 하나도 수행되지 않습니다. 그들은 unordered_multimap 및 unordered_multiset 내부적으로 사용하고 같은

당신은 operator== 및 std::hash해야합니다. 연결된 예에서 키의 유형은 int이므로 operator== 및 std::hash<int>이 이미 정의되어 있습니다. Note을 키로 사용하려면이 키를 직접 정의해야합니다. 자주 요소를 변경할 필요가없는 경우

은 내가 multiset로 시작하는 것을 권 해드립니다. 을 수행하는 경우을 지우고 삽입하지 않고 Note을 변경하려면 Note의 회원으로 measureNumber을 삭제하고 multimap<int, Note>을 사용하는 것이 좋습니다.

컨테이너의 unordered_ 버전이 사용자의 요구에 더 잘 맞다고 느끼면 대 map을 선택해야합니다. unordered_multimap<int, Note> (Note에서 measureNumber을 제거한 경우)을 선택하면 링크 된 예에서와 같이 키는 int입니다. 따라서이 작업을 수행하기 위해 특별한 것을 정의 할 필요가 없습니다. measureNumber을 Note의 회원으로 유지하고 unordered_multiset<Note>을 사용하려는 경우 Note이 핵심이므로 추가 작업이 필요합니다.

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

이 작성하고 std::unordered_multiset<Note>를 사용할 수 있습니다. 그러나, 나는이 이이라는 것을 정말로 모릅니다. 당신은 심지어 정렬 된 std::vector<Note>이 당신에게 가장 적합하다는 것을 알 수 있습니다. 프로파일 링과 함께 컨테이너를 사용하는 방법에 대한 더 많은 연구와 생각은 최선의 대답을 제공해야합니다.