boost - C++: unordered_set のキーとしての shared_ptr

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 のサイズが 1 ではなく 2 なのかということです。ハッシュ関数と関係があるに違いないと確信しています。ブーストドキュメントを見て、ハッシュ関数をいじってみましたが、うまくいきませんでした。

アイデア？

score 8 · Accepted Answer

make_shared新しいを割り当て、それintを a で囲みshared_ptrます。これは、2 つshared_ptr<int>の s が異なる memoryを指していることを意味し、ポインター値をキーとするハッシュテーブルを作成しているため、それらは別個のキーです。

同じ理由で、これは 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;

ただし、これはおそらくいくつかの理由で悪い考えです。

x != ybuts4[x]とs4[y]が同じという紛らわしい状況があります。
誰かがハッシュキーが指す値を変更した場合、あなたのハッシュは壊れます! あれは：
```
boost::shared_ptr<int> tmp(new int(42));
s4[tmp] = 42;
*tmp = 24; // UNDEFINED BEHAVIOR
```

通常、ハッシュ関数では、キーを不変にする必要があります。後で何が起こっても、常に同じものを比較します。ポインターを使用している場合は、通常、ポインターの ID を一致させる必要がありextra_info_hash[&some_object] = ...ます。some_objectこれは通常、のメンバーが何であれ、常に同じハッシュ値にマップされます。挿入後に変更可能なキーを使用すると、実際に変更するのが非常に簡単になり、ハッシュで未定義の動作が発生します。

score 2 · Accepted Answer

Boost <= 1.46.0 では、hash_valueaのデフォルトboost::shared_ptrはそのブール値、trueつまりであることに注意してくださいfalse。shared_ptrでないものについては、として 1NULLに評価されます。hash_value(bool)shared_ptr == true

つまり、Boost <= 1.46.0 を使用している場合は、ハッシュセットをリンクリストにダウングレードします。

これは Boost 1.47.0 で修正されています。 https://svn.boost.org/trac/boost/ticket/5216を参照してください。

を使用している場合はstd::shared_ptr、独自のハッシュ関数を定義するかboost/functional/hash/extensions.hpp、Boost >= 1.51.0 から使用してください。

score 0 · Accepted Answer

0

ご覧のとおり、挿入された 2 つのオブジェクトs2は別個のものです。

于 2011-06-19T19:57:11.263 に答える

boost - C++: unordered_set のキーとしての shared_ptr

3 に答える 3

Related

Reference