在 std::hash_map 中使用 GUID 作为键的“正确”方法是什么

Question

我想说

std::hash_map<GUID, int> foo;

我相信要做到这一点，我必须创建一个

bool operator < (const GUID &guid1, const GUID &guid2);
std::size_t hash_value(GUID const &b);

比较 GUID 的正确方法是什么？(memcmp?) - 生成哈希的正确方法是什么？

如果有人能充实这两个功能就太好了，我已经阅读了数十篇文章，这些文章可以做所有事情，但给出了最后的线索:-)

Answer 1

从文档看来：

typedef struct _GUID {
  DWORD Data1;
  WORD  Data2;
  WORD  Data3;
  BYTE  Data4[8];
} GUID;

大概有几种可能

建立自己的

为了比较，我会逐项进行

bool operator < (const GUID &guid1, const GUID &guid2) {
    if(guid1.Data1!=guid2.Data1) {
        return guid1.Data1 < guid2.Data1;
    }
    if(guid1.Data2!=guid2.Data2) {
        return guid1.Data2 < guid2.Data2;
    }
    if(guid1.Data3!=guid2.Data3) {
        return guid1.Data3 < guid2.Data3;
    }
    for(int i=0;i<8;i++) {
        if(guid1.Data4[i]!=guid2.Data4[i]) {
            return guid1.Data4[i] < guid2.Data4[i];
        }
    }
    return false;
}

对于散列......我会使用UuidHash函数（请注意，GUID 是UUID 定义中指示的UUID形式）

回到字符串

使用StringFromCLSID从 GUID 中获取字符串...一旦有了字符串，就拥有了所有运算符。

……这可能更贵。

Answer 2

C++ 库中没有 std::hash_map 并且 stdext::hash_map 是一个过时的类（请参阅http://msdn.microsoft.com/en-us/en-en/library/0d462wfh.aspx）。

要在 std::unordered_map 中使用 GUID：

#include <climits>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <unordered_map>

// Adopted from http://msdn.microsoft.com/en-us/library/windows/desktop/aa373931%28v=vs.85%29.aspx
typedef struct _GUID
{
    std::uint32_t Data1;
    std::uint16_t Data2;
    std::uint16_t Data3;
    std::uint8_t  Data4[8];
} GUID;

// Ensure it has 128 bits
static_assert(sizeof(_GUID) == 128/CHAR_BIT, "GUID");

// The compare operator is required by std::unordered_map
inline bool operator == (const GUID& a, const GUID& b) {
    return std::memcmp(&a, &b, sizeof(GUID)) == 0;
}

// A wrapper to create a GUID
inline GUID make_guid() {
    // Should return the value of some library function. 
    return GUID();
}

// Specialize std::hash
namespace std {
    template<> struct hash<GUID>
    {
        size_t operator()(const GUID& guid) const noexcept {
            const std::uint64_t* p = reinterpret_cast<const std::uint64_t*>(&guid);
            std::hash<std::uint64_t> hash;
            return hash(p[0]) ^ hash(p[1]);
        }
    };
}

// Usage
int main(void) {
    typedef std::unordered_map<GUID, int> map_type;
    map_type m;
    m.insert(map_type::value_type(make_guid(), 0));
    m.insert(map_type::value_type(make_guid(), 1));
    m.insert(map_type::value_type(make_guid(), 2));
}

Answer 3

你的 GUID 是什么类型？考虑下面这段代码：

struct MyCompare : binary_function<SomeClass, SomeClass, bool>
{
    //constructor
    MyCompare(int (SomeClass::*p)() const, int (SomeClass::*p2)() const) : pointer(p), pointer2(p2) {}

    //comparison functor

    bool operator < (SomeClass const& left, SomeClass const& right)
    {
        if ((left.*pointer)() != (right.*pointer)())
        {
            return less<int>()((left.*pointer)(), (right.*pointer)());
        }
        else
        {
            return less<int>()((left.*pointer2)(), (right.*pointer2)());
        }
    }
    private:
    int (SomeClass::*pointer)() const;
    int (SomeClass::*pointer2)() const;
};

这是针对 2 个 int 类型字段的复合键。对第一个指针进行排序，然后对第二个指针进行稳定排序。第一次尝试代码可能无法运行，但您已经明白了。