c++ - unordered_set 将元素存储为指针

Question

缩小范围:我目前正在使用 Boost.Unordered .我看到两种可能的解决方案:

1. 定义我自己的Equality Predicates and Hash Functions并利用模板(可能是 is_pointer )来区分指针和实例；

2. 简单地扩展boost::hash通过提供 hash_value(Type* const& x)至于散列；并添加 ==运算符重载为自由函数 (Type* const& x, Type* const& y)用于相等检查的参数。

我不确定这两种变体是否真的可行，因为我没有测试它们。我想知道你处理这个问题。欢迎实现:)

编辑 1:这个呢？

template<class T>
struct Equals: std::binary_function<T, T, bool> {
    bool operator()(T const& left, T const& right) const {
        return left == right;
    }
};

template<class T>
struct Equals<T*> : std::binary_function<T*, T*, bool> {
    bool operator()(T* const& left, T* const& right) const {
        return *left == *right;
    }
};

编辑 2:

我刚刚定义:

friend std::size_t hash_value(Base const& base) {
    boost::hash<std::string> hash;

    return hash(base.string_);
}

friend std::size_t hash_value(Base* const& base) {
    return hash_value(*base);
}

然后:

Derived d1("x");
Derived d2("x");

unordered_set<Base*> set;

set.insert(&d1);

assert(set.find(&d2) == end());

调试器说 friend std::size_t hash_value(Base* const& base)永远不会被调用(GCC 4.7)。这是为什么？

编辑 3:我发现 template <class T> std::size_t hash_value(T* const& v)在 boost/functional/hash.hpp在第 215 行(Boost 1.49)是 Boost 对指针的专门化，它只是屏蔽了您对 hash_value 的自定义实现。比如我在 EDIT 2 中。因此，似乎这里唯一的方法是创建一个自定义哈希仿函数。

Answer 1

对于哈希函数，您可以选择专门化 boost::hash(或较新标准中的 std::hash)或定义一个新的仿函数类。这些替代方案同样有效。

对于相等运算符，您需要定义一个新的仿函数，因为您不能在指针上重新定义相等运算符。它是一个内置运算符(在功能术语中定义为 bool operator==( T const *x, T const *y ))并且不能被替换。

这两者都可以通过在非模板类中使用模板化的 operator() 进行一般定义。

struct indirect_equal {
    template< typename X, typename Y >
    bool operator() ( X const &lhs, Y const &rhs )
        { return * lhs == * rhs; }
};

哈希器遵循类似的模式。