c++ - 在 C++ 中将常规 `set` 转换为 boost 的 `unordered_set`

Question

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

#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 时还有一些。我错过了什么？

Answer 1

您缺少 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) 构造函数复制到临时 vector 中。 (这是最简单的代码)
• 使用boost::unordered_set<int> ，复制到临时 vector 中，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 移动语义可以在此处获得巨大的性能胜利，但在这种情况下，您应该使用相同的容器来构造和存储内部集。