convert regular `set` to boost's `unordered_set` in c++

Question

I have a small program that is mostly using regular set's but now that I'm getting a poor performance I decided to use unordered_set from boost. I was optimistically thinking that a simple search and replace from set to unordered_set would do the trick with ofc the additional headers such as:

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

but now I have lots of compile errors. I have looked into it and realized that even a simple nested for loop does not work. Here's an example:

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;
    }
}

which compiles fine when using set but gives me:

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)

and some more when using unordered_set. What am I missing?

Answer 1

You are missing a hash function for unordered_sets. The bad news is, that you cannot easily construct one. For example, the order in which you insert into your inner sets might cause a different ordering within the container, hence yielding a different hash if you use the naive way to construct it (as I did in the previous version of this answer :) )

Either way, you need to pick a different container for your inner sets, and these sets need to be sorted. I propose that you use std::vector or std::set. Then you need a hash functor: you can use boost::hash_range to easily construct one:

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

It is probably the best choice to use std::vector<int> as your inner container, making the whole thing a boost::unordered_set<std::vector<int>, HashContainer<std::vector<int> > >. Note that you do not necessarily need to use the same container for building and storing your inner sets. If you want to use that you can either:

• Use std::vector<int> directly to build the inner sets. For that, push all the values, then use std::sort and std::unique to establish set property, then insert into the outer set. (Probably, preferred for performance)
• Use std::set<int> and copy into a temporary vector, using the (Iterator, Iterator) constructor, in your insert call. (This is the simplest code)
• Use boost::unordered_set<int>, copy into a temporary vector, std::sort that (no need for unique) and insert.

You can also use std::set<int> as the inner container, making the whole set an boost::unordered_set<std::set<int>, HashContainer<std::set<int> > >. In this case, you can use any container to construct the inner sets. If you use std::set<int> you can move/copy into the outer container. I you use another container, you can use the std::set<int>::set(Iterator b, Iterator e) constructor.

Note that having C++11 move semantics available can be a huge performance win here, but in that case you should use the same container for constructing and storing the inner set.

Answer 2

I don't have enough REPs to comment on the accepted answer. But I saw this in the boost docs about hash_range

"hash_range is sensitive to the order of the elements so it wouldn't be appropriate to use this with an unordered container."

Answer 3

Using unordered containers is all about hashing and every type that you use as a key should have an assigned hash function(and of course operator==) in order to be used as a key in unordered container. So when you use unordered_set<int> as key for another unordered_set you must provide a hash function for it. see <boost/functional/hash.hpp> for more information on providing a hash function for a type