C++:shared_ptr as unordered_set的密钥

Question

请考虑以下代码

#include <boost/unordered_set.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/make_shared.hpp>

int main()
{
    boost::unordered_set<int> s;
    s.insert(5);
    s.insert(5);
    // s.size() == 1 

    boost::unordered_set<boost::shared_ptr<int> > s2;
    s2.insert(boost::make_shared<int>(5));
    s2.insert(boost::make_shared<int>(5));
    // s2.size() == 2
}

问题是:为什么s2的大小是2而不是1？我很确定它必须与哈希函数有关.我试着看看增强文档,并且没有运气就玩哈希函数.

想法？

Answer 1

make_shared分配一个新的int,并shared_ptr围绕它包装.这意味着你的两个shared_ptr<int>指向不同的内存,并且由于你创建了一个键控指针值的哈希表,它们是不同的键.

出于同样的原因,这将导致2的大小:

boost::unordered_set<int *> s3;
s3.insert(new int(5));
s3.insert(new int(5));
assert(s3.size() == 2);

在大多数情况下,你可以认为shared_ptrs就像指针一样,包括比较,除了自动销毁.

您可以定义自己的哈希函数和比较谓词,并将它们作为模板参数传递给unordered_map,但是:

struct your_equality_predicate
    : std::binary_function<boost::shared_ptr<int>, boost::shared_ptr<int>, bool>
{
    bool operator()(boost::shared_ptr<int> i1, boost::shared_ptr<int> i2) const {
        return *i1 == *i2;
    }
};

struct your_hash_function
    : std::unary_function<boost::shared_ptr<int>, std::size_t>
{
    std::size_t operator()(boost::shared_ptr<int> x) const {
        return *x; // BAD hash function, replace with somethign better!
    }
};

boost::unordered_set<int, your_hash_function, your_equality_predicate> s4;

但是,由于以下几个原因,这可能是一个坏主意:

1. 你有一个令人困惑的情况,x != y但是s4[x]并且s4[y]是相同的.

2. 如果有人更改了哈希键所指向的值,那么哈希将会中断!那是:

   boost::shared_ptr<int> tmp(new int(42));
   s4[tmp] = 42;
   *tmp = 24; // UNDEFINED BEHAVIOR
   

通常使用散列函数,您希望密钥是不可变的; 无论以后会发生什么,它总会比较相同的.如果你正在使用指针,你通常希望指针标识是匹配的,如extra_info_hash[&some_object] = ...; 这通常总是映射到相同的散列值,无论some_object成员是什么.插入后键可变,实际上很容易实现,导致散列中的未定义行为.