unordered_map 中用户定义类型的运算符重载()

问题描述 投票：0回答：2

我正在看这篇文章C++ unordered_map 使用自定义类类型作为键

  1. 我知道我们需要为自定义类型键重新定义 
    equality
    和 
    hash code
    。
  2. 我知道运算符重载一般是如何工作的。

但是，

operator()
和
hash code
有什么关系呢？
unordered_map
是否在内部使用 
()
运算符在某处评估键？

c++ stl hashmap operator-overloading unordered-map
2个回答
4
投票

std::unordered_map
使用
std::hash
对象来计算哈希值。

它将像函数一样使用哈希对象，调用

operator()
进行计算。

举个简单的例子，对于 

int
键，它会是这样的：

int key = 123;  // Or whatever value...

std::hash<int> hash_object;
auto hash_value = hash_object(key);  // Calls hash_object.operator()(key)
1
投票
根据

cpp-reference

，
std::unordered_map 的完整定义如下所示：

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

如您所见，它具有 has 函数、相等检查器和分配器的模板参数。我们不会在这个答案中查看分配器。

如您所见，它需要具有密钥类型的功能和

equal_to
密钥类型的功能。

因此，为了使用它，我们可以将两个 

struct
专门用作默认值，因此 std::hash 和 std::equal_to。

为了做到这一点，我们需要打开 std 命名空间，这基本上不太好。

但是，我们可以这样做：

#include <iostream>
#include <unordered_map>
#include <functional>

struct Test {
    char a{};
    char b{};
    char c{};
};

namespace std {
    template <>
    struct hash<Test> {
        size_t operator()(const Test& t) const {
            return (((size_t)t.a) << 16) + (((size_t)t.b) << 8) + ((size_t)t.c);
        }
    };
    template <> 
    struct equal_to<Test> {
        bool operator()(const Test& lhs, const Test& rhs) const {
            return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
        } 
    };
}

int main() {
    std::unordered_map<Test, int> test{};
    
    Test t1{ 'a', 'b', 'c' };
    Test t2{ 'd', 'e', 'f' };
    
    test[t1] = 1;
    test[t2] = 2;

    for (const auto& [key, value] : test)
        std::cout << key.a << ' ' << key.b << ' ' << key.c << "  --> " << value << '\n';
}

通过上述 Functor 专业化，我们可以使用该类，而无需任何进一步的模板参数。

但是我们当然也可以定义专用的函子。但接下来我们需要将函子的名称作为模板参数提交

这可能看起来像：

#include <iostream>
#include <unordered_map>
#include <functional>

struct Test {
    char a{};
    char b{};
    char c{};
};

struct hashTest {
    size_t operator()(const Test& t) const {
        return (((size_t)t.a) << 16) + (((size_t)t.b) << 8) + ((size_t)t.c);
    }
};
struct equal_toTest {
    bool operator()(const Test& lhs, const Test& rhs) const {
            return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
    }
};

int main() {
    std::unordered_map<Test, int, hashTest, equal_toTest> test{};

    Test t1{ 'a', 'b', 'c' };
    Test t2{ 'd', 'e', 'f' };

    test[t1] = 1;
    test[t2] = 2;

    for (const auto& [key, value] : test)
        std::cout << key.a << ' ' << key.b << ' ' << key.c << "  --> " << value << '\n';
}

由于额外的模板参数，这不再那么好，但无论如何。

接下来，我们还可以使用 Lambda。

但是，您不能直接将闭包类型作为模板参数传递，并且需要从另一个闭包对象构造容器成员。 （闭包类型没有默认构造函数！）。对于块作用域

std::unorderd_map
，这在某种程度上是可以的。但总的来说，它有点笨拙。

请亲自看看：

#include <iostream>
#include <unordered_map>
#include <functional>

struct Test {
    char a{};
    char b{};
    char c{};
};


struct equal_toTest {
    bool operator()(const Test& lhs, const Test& rhs) const {
        return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c;
    }
};

int main() {
    auto equalTest = [](const Test& lhs, const Test& rhs) -> bool { return lhs.a == rhs.a and lhs.b == rhs.b and lhs.c == rhs.c; };
    auto hasher = [](const Test& t)->size_t {return (((size_t)t.a) << 16) + (((size_t)t.b) << 8) + ((size_t)t.c); };
    std::unordered_map < Test, int, decltype(hasher), decltype(equalTest)> test{};

    Test t1{ 'a', 'b', 'c' };
    Test t2{ 'd', 'e', 'f' };

    test[t1] = 1;
    test[t2] = 2;

    for (const auto& [key, value] : test)
        std::cout << key.a << ' ' << key.b << ' ' << key.c << "  --> " << value << '\n';
}

好吧，很难理解，而且可能没那么有用。

接下来，如果我们阅读

std::equal
here，它将调用：

bool 运算符()( const T& lhs, const T& rhs ) const;

我们也可以直接在我们的“测试”中实现

struct
。那么我们就可以省略一个模板参数了。

#include <iostream>
#include <unordered_map>
#include <functional>

struct Test {
    char a{};
    char b{};
    char c{};
    bool operator==(const Test& t) const { return a == t.a and b == t.b and c == t.c; }
};

struct hashTest {
    size_t operator()(const Test& t) const {
        return (((size_t)t.a) << 16) + (((size_t)t.b) << 8) + ((size_t)t.c);
    }
};

int main() {
    std::unordered_map<Test, int, hashTest> test{};

    Test t1{ 'a', 'b', 'c' };
    Test t2{ 'd', 'e', 'f' };

    test[t1] = 1;
    test[t2] = 2;

    for (const auto& [key, value] : test)
        std::cout << key.a << ' ' << key.b << ' ' << key.c << "  --> " << value << '\n';
}

当然，这也适用于我们类型“Test”的类外部布尔比较运算符

#include <iostream>
#include <unordered_map>
#include <functional>

struct Test {
    char a{};
    char b{};
    char c{};
};
bool operator==(const Test& l, const Test& r)  { return l.a == r.a and l.b == r.b and l.c == r.c; }

struct hashTest {
    size_t operator()(const Test& t) const {
        return (((size_t)t.a) << 16) + (((size_t)t.b) << 8) + ((size_t)t.c);
    }
};

int main() {
    std::unordered_map<Test, int, hashTest> test{};

    Test t1{ 'a', 'b', 'c' };
    Test t2{ 'd', 'e', 'f' };

    test[t1] = 1;
    test[t2] = 2;

    for (const auto& [key, value] : test)
        std::cout << key.a << ' ' << key.b << ' ' << key.c << "  --> " << value << '\n';
}

不幸的是，哈希函数不可能做到这一点。您可以将计算哈希值的函数添加到“Test”类中，但您需要将其命名为模板参数。

#include <iostream>
#include <unordered_map>
#include <functional>

struct Test {
    char a{};
    char b{};
    char c{};
    bool operator==(const Test& t) const { return a == t.a and b == t.b and c == t.c; }
    size_t operator()(const Test& t) const { return (((size_t)t.a) << 16) + (((size_t)t.b) << 8) + ((size_t)t.c); }
};

struct hashTest {
    
};

int main() {
    std::unordered_map<Test, int, Test> test{};

    Test t1{ 'a', 'b', 'c' };
    Test t2{ 'd', 'e', 'f' };

    test[t1] = 1;
    test[t2] = 2;

    for (const auto& [key, value] : test)
        std::cout << key.a << ' ' << key.b << ' ' << key.c << "  --> " << value << '\n';
}

混合上述方法还有更多潜在的解决方案。

但是你现在应该有了更好的理解。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.