unordered_set将元素存储为指针 [英] unordered_set storing elements as pointers
问题描述
缩小范围:我目前使用 Boost。无序。我看到两种可能的解决方案:
-
定义我自己的 Equality Predicates and Hash Functions 并利用模板(可能
is_pointer
)来区分指针和实例;
-
简单地通过提供<$>来扩展
boost :: hash
c $ c> hash_value(Type * const& x)用于散列;并使用(Type * const& x,Type * const& y)
参数添加==
运算符重载为自由函数至于平等检查。
我不确定这两种变化是否可行,因为我没有测试他们。我想找出你处理这个问题。欢迎实现:)
编辑1:
这是怎么回事?
模板< class T>
struct Equals:std :: binary_function< T,T,bool> {
bool operator()(T const& left,T const& right)const {
return left == right;
}
};
模板< 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>散列;
返回散列(base.string_);
friend std :: size_t hash_value(Base * const& base){
return hash_value(* base);
}
然后:
Derived d1(x);
派生的d2(x);
unordered_set< Base *>组;
set.insert(& d1);
assert(set.find(& d2)== end());
调试器说 friend std :: size_t hash_value(Base * const& base )
永远不会被调用(GCC 4.7)。为什么会这样?
编辑3:
我发现 template< class T>第215行(Boost 1.49)中的std :: size_t hash_value(T * const& v)
在 boost / functional / hash.hpp
中是Boost's指针的专业化,它只是简单地掩盖了 EDIT 2 中的 hash_value
的自定义实现。
因此,这里看起来唯一的办法就是创建一个自定义的散列函数。
,你可以在新的标准中专门选择 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; }
};
按照类似的模式进行搜索。
To narrow it down: I'm currently using Boost.Unordered. I see two possible solutions:
Define my own Equality Predicates and Hash Functions and to utilize templates (maybe
is_pointer
) to distinct between pointers and instances;Simply to extend
boost::hash
by providinghash_value(Type* const& x)
as for hashing; and add==
operator overload as free function with(Type* const& x, Type* const& y)
parameters as for equality checking.
I'm not sure whether both variations are actually possible, since I didn't test them. I would like to find out you handle this problem. Implementations are welcome :)
EDIT 1: What about this?
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;
}
};
EDIT 2:
I've just defined:
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);
}
And then:
Derived d1("x");
Derived d2("x");
unordered_set<Base*> set;
set.insert(&d1);
assert(set.find(&d2) == end());
Debugger says that friend std::size_t hash_value(Base* const& base)
is never called (GCC 4.7). Why is that?
EDIT 3:
I found out that template <class T> std::size_t hash_value(T* const& v)
in boost/functional/hash.hpp
on line #215 (Boost 1.49) is Boost's specialization for pointers and it simply masks your custom implementation of hash_value
such as mine in EDIT 2.
Therefore, it seems like the only way here is to create a custom Hash Functor.
For the hash function, you have a choice between specializing boost::hash
(or std::hash
in the newer standard) or defining a new functor class. These alternatives work equally well.
For the equality operator, you need to define a new functor, because you cannot redefine the equality operator over pointers. It's a built-in operator (defined in functional terms as bool operator==( T const *x, T const *y )
) and cannot be replaced.
Both of these can be defined generically by using a templated operator()
in a non-templated class.
struct indirect_equal {
template< typename X, typename Y >
bool operator() ( X const &lhs, Y const &rhs )
{ return * lhs == * rhs; }
};
Follow a similar pattern for the hasher.
这篇关于unordered_set将元素存储为指针的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!