unordered_set将元素存储为指针

Question

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

1. 定义我自己的Equality Predicates和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(升压1.49)是加速对指针的专业化,它只是掩盖你的定制实现hash_value在诸如矿井EDIT 2.因此,似乎这里唯一的方法是创建一个自定义Hash Functor.

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

遵循类似的幽默模式.