2

私は主に通常のを使用している小さなプログラムを持っていますが、setパフォーマンスが低下しているのでunordered_set、ブーストから使用することにしました。私は楽観的に、単純な検索と置換からset、unordered_set次のような追加のヘッダーを使用してトリックを実行できると考えていました。

#include <boost/unordered_set.hpp>
using boost::unordered_set;

しかし、今はコンパイルエラーがたくさんあります。for私はそれを調べて、単純なネストされたループでさえ機能しないことに気づきました。次に例を示します。

unordered_set<unordered_set<int> > s;

unordered_set<int> temp;
temp.insert(5);
temp.insert(6);
temp.insert(7);

s.insert(temp);
s.insert(temp);

unordered_set<unordered_set<int> >::iterator it1;
unordered_set<int>::iterator it2;
for (it1 = s.begin(); it1 != s.end(); it1++) {
    for (it2 = it1->begin(); it2 != it1->end(); it2++) {
        cout << *it2 << endl;
    }
}

これは、使用すると正常にコンパイルされますsetが、次のようになります。

In file included from /usr/include/boost/functional/hash/hash.hpp:535:0,
                 from /usr/include/boost/functional/hash.hpp:6,
                 from /usr/include/boost/unordered/unordered_set.hpp:17,
                 from /usr/include/boost/unordered_set.hpp:16,
                 from foo.cpp:4:
/usr/include/boost/functional/hash/extensions.hpp: In member function ‘std::size_t boost::hash<T>::operator()(const T&) const [with T = boost::unordered_set<int>, std::size_t = long uns
igned int]’:
/usr/include/boost/unordered/detail/unique.hpp:363:1:   instantiated from ‘boost::unordered_detail::hash_unique_table<T>::emplace_return boost::unordered_detail::hash_unique_table<T>::e
mplace_impl(const key_type&, const Arg0&) [with Arg0 = boost::unordered_set<int>, T = boost::unordered_detail::set<boost::hash<boost::unordered_set<int> >, std::equal_to<boost::unordere
d_set<int> >, std::allocator<boost::unordered_set<int> > >, boost::unordered_detail::hash_unique_table<T>::emplace_return = std::pair<boost::unordered_detail::hash_iterator_base<std::al
locator<boost::unordered_set<int> >, boost::unordered_detail::ungrouped>, bool>, typename T::iterator_base = boost::unordered_detail::hash_iterator_base<std::allocator<boost::unordered_
set<int> >, boost::unordered_detail::ungrouped>, boost::unordered_detail::hash_unique_table<T>::key_type = boost::unordered_set<int>]’
/usr/include/boost/unordered/detail/unique.hpp:398:36:   instantiated from ‘boost::unordered_detail::hash_unique_table<T>::emplace_return boost::unordered_detail::hash_unique_table<T>::
emplace(const Arg0&) [with Arg0 = boost::unordered_set<int>, T = boost::unordered_detail::set<boost::hash<boost::unordered_set<int> >, std::equal_to<boost::unordered_set<int> >, std::al
locator<boost::unordered_set<int> > >, boost::unordered_detail::hash_unique_table<T>::emplace_return = std::pair<boost::unordered_detail::hash_iterator_base<std::allocator<boost::unorde
red_set<int> >, boost::unordered_detail::ungrouped>, bool>, typename T::iterator_base = boost::unordered_detail::hash_iterator_base<std::allocator<boost::unordered_set<int> >, boost::un
ordered_detail::ungrouped>]’
/usr/include/boost/unordered/unordered_set.hpp:339:40:   instantiated from ‘std::pair<boost::unordered_detail::hash_const_iterator<typename boost::unordered_detail::rebind_wrap<A, T>::t
ype, boost::unordered_detail::ungrouped>, bool> boost::unordered_set<T, H, P, A>::insert(const value_type&) [with T = boost::unordered_set<int>, H = boost::hash<boost::unordered_set<int
> >, P = std::equal_to<boost::unordered_set<int> >, A = std::allocator<boost::unordered_set<int> >, typename boost::unordered_detail::rebind_wrap<A, T>::type = std::allocator<boost::uno
rdered_set<int> >, boost::unordered_set<T, H, P, A>::value_type = boost::unordered_set<int>]’
foo.cpp:17:18:   instantiated from here
/usr/include/boost/functional/hash/extensions.hpp:176:34: error: no matching function for call to ‘hash_value(const boost::unordered_set<int>&)’
/usr/include/boost/functional/hash/extensions.hpp:176:34: note: candidates are:
/usr/include/boost/functional/hash/hash.hpp:144:24: note: std::size_t boost::hash_value(bool)

を使用する場合はさらにいくつかunordered_set。私は何が欠けていますか？

4

3 に答える 3

3

unordered_setsのハッシュ関数がありません。悪いニュースは、簡単に作成できないことです。たとえば、内部セットに挿入する順序によって、コンテナー内で異なる順序が発生する可能性があるため、単純な方法で構築すると、異なるハッシュが生成されます（この回答の前のバージョンで行ったように:)）

いずれにせよ、内部セット用に別のコンテナーを選択する必要があり、これらのセットをソートする必要があります。std::vectorまたはを使用することをお勧めしますstd::set。次に、ハッシュファンクターが必要です。ハッシュファンクターboost::hash_rangeを簡単に作成するために使用できます。

template <class T>
struct HashContainer
{
   std::size_t operator()(T const& Rhs) const
   {
     return boost::hash_range(Rhs.begin(), Rhs.end());
   }
};

おそらく、std::vector<int>内部コンテナとして使用するのが最良の選択であり、すべてをboost::unordered_set<std::vector<int>, HashContainer<std::vector<int> > >。内部セットの構築と保存に必ずしも同じコンテナを使用する必要はないことに注意してください。それを使用したい場合は、次のいずれかを行うことができます。

  • std::vector<int>内部セットを構築するために直接使用します。そのためには、すべての値をプッシュし、とを使用std::sortしstd::uniqueてセットプロパティを確立してから、外部セットに挿入します。（おそらく、パフォーマンスのために好まれます）
  • std::set<int>挿入呼び出しで（Iterator、Iterator）コンストラクターを使用して、一時ベクトルを使用してコピーします。（これは最も単純なコードです）
  • を使用boost::unordered_set<int>して、一時的なベクトルにコピーし、std::sort（一意である必要はありません）挿入します。

std::set<int>内側のコンテナとしても使用でき、セット全体をboost::unordered_set<std::set<int>, HashContainer<std::set<int> > >。この場合、任意のコンテナを使用して内部セットを作成できます。使用するstd::set<int>場合は、外部コンテナに移動/コピーできます。別のコンテナーを使用する場合は、std::set<int>::set(Iterator b, Iterator e)コンストラクターを使用できます。

ここでは、C ++ 11の移動セマンティクスを使用できるようにすることで、パフォーマンスを大幅に向上させることができますが、その場合は、内部セットの構築と保存に同じコンテナーを使用する必要があります。

于 2012-10-22T16:49:03.380 に答える
2

受け入れられた回答にコメントするのに十分なREPがありません。しかし、私はこれをhash_rangeに関するブーストドキュメントで見ました

「hash_rangeは要素の順序に敏感であるため、順序付けされていないコンテナでこれを使用することは適切ではありません。」

于 2012-10-22T18:12:49.463 に答える
1

コンテナの使用unorderedはすべてハッシュに関するものであり、キーとして使用するすべてのタイプにはoperator==、コンテナでキーとして使用するためにハッシュ関数（およびもちろん）が割り当てられている必要がありunorderedます。したがって、unordered_set<int>別のキーとして使用するunordered_set場合は、そのハッシュ関数を提供する必要があります。<boost/functional/hash.hpp>タイプにハッシュ関数を提供する方法の詳細については、を参照してください。

于 2012-10-22T16:48:01.063 に答える