Call to implicitly-deleted default constructor of 'unordered_set< vector<int> >'

Question

It seems like when I try to define an unordered_set of vector, I get an error saying: "Call to implicitly-deleted default constructor of unordered_set< vector<int> > ." This doesn't happen when I define a regular (ordered) set: set< vector<int> >. It seems like I need to define hash<vector<int>> in order to get rid of the error.

Does anyone know why I get this error only when I use unordered_set? Shouldn't both data structures use hashing, so why would an unordered_set need a custom-defined hash function? In fact, shouldn't a regular (ordered) set need some custom-defined comparator as well in order to order the vector<int> data structures?

Answer 1

It's because unordered_set is using std::hash template to compute hash for its entries and there is no std::hash for pairs. You have to define custom hash to use unordered_set.

    struct vector_hash
{
    template <class T1, class T2>
    std::size_t operator () (std::pair<T1, T2> const &v) const
    {
        return std::hash<T1>()(v.size());    
    }
};

and then declare your unordered_set as -

std::unordered_set< vector<int>, vector_hash> set;

This hash function is not good. It's just an example.

Answer 2

Shouldn't both data structures use hashing

No. This is documented, you can always look it up yourself:

• std::set

  std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as red-black trees

  Note that Compare defaults to std::less<Key>, and std::vector overloads operator<.

• std::unordered_set, for comparison

  Unordered set is an associative container that contains a set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity.

  Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value

  and the Hash type parameter defaults to std::hash<Key>. This has a list of specializations for standard library types, and std::vector is not included on that list.