2

我有一个小程序，主要使用常规set的，但现在我的性能很差，我决定unordered_set从 boost 中使用。我乐观地认为，简单的搜索和替换 from settounordered_set可以使用 ofc 附加标题，例如：

#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::vectoror 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::sortandstd::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 的 boost 文档中看到了这一点

“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 回答