C ++: shared_ptr как ключ unordered_set - PullRequest
Новая
       35

C ++: shared_ptr как ключ unordered_set

2 голосов
/ 19 июня 2011

Рассмотрим следующий код 

#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?Я почти уверен, что это как-то связано с хэш-функцией.Я безуспешно пытался посмотреть на документацию по надстройке и поиграть с хэш-функцией.

Идеи?

Ответы [ 3 ]

5 голосов
/ 19 июня 2011

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_ptr s действующими как указатели, в том числе для сравнений, за исключением автоматического уничтожения.

Вы можете определить свою собственную хеш-функцию и предикат сравнения и передать их в качестве параметров шаблона в 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. С ключами, изменяемыми после вставки, на самом деле слишком легко сделать это, что приводит к неопределенному поведению в хэше.

2 голосов
/ 25 августа 2012

Обратите внимание, что в Boost <= 1.46.0 по умолчанию <code>hash_value для boost::shared_ptr является его логическим значением, true или false.Для любого shared_ptr, который не NULL, hash_value оценивается как 1 (один), как (bool)shared_ptr == true.

Другими словами, вы понижаете хэш-набор до связанного списка если вы используете Boost <= 1.46.0. </p>

Это исправлено в Boost 1.47.0, см. https://svn.boost.org/trac/boost/ticket/5216.

Если вы используете std::shared_ptrПожалуйста, определите свою собственную хеш-функцию или используйте boost/functional/hash/extensions.hpp из Boost> = 1.51.0

0 голосов
/ 19 июня 2011

Как вы узнали, два объекта, вставленные в s2, различны.

...