30

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?

vincenzo
  • 413
  • 1
  • 4
  • 5

5 Answers5

15

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.

Satakshi Pandey
  • 234
  • 4
  • 9
6

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.

Useless
  • 64,155
  • 6
  • 88
  • 132
1

Unfortunately, there is no general specialization of std::hash for std::vector. There is only a specialization for std::vector<bool>, which is not very helpful:

int main()
{
    std::hash<std::vector<bool>> hash_bool;  // ok
    std::hash<std::vector<int>> hash_int;  // error
}

Demo.

The reason IMHO is that there is no standard way to combine hashes. Because you have to combine hashes for all elements in order to construct the hash for the whole vector. But why there is no standard way to combine hashes - this is the mystery.

You can use boost::hash or absl::Hash instead, e.g.:

unordered_set<vector<int>, boost::hash<vector<int>>>

Be aware that the hash codes computed by absl::Hash are not guaranteed to be stable across different runs of your program. Which might be either a benefit (if you aim for security), or a disadvantage (if you aim for reproducibility).

Mikhail
  • 20,685
  • 7
  • 70
  • 146
0

My answer is not related to std::vector issue directly, but in my case I've got the "Call to implicitly-deleted default constructor" error on std::string, just because I did not include the <string> header file.

I mean that that error can happen when unordered_map is used on forward declared type:

#include <unordered_map>
#include <string_view>
//#include <string>

int main()
{
    auto m = std::unordered_map<std::string, int>{};
}
Dmytro Ovdiienko
  • 816
  • 8
  • 9
-7

set use self balancing trees whereas unordered_set uses pure hashing.

shaurya
  • 11