C++ Unordered_Map Fail When Used with a Vector as Key

C++ unordered_map fail when used with a vector as key

§23.2.5, paragraph 3, says:

Each unordered associative container is parameterized by Key, by a function object type Hash that meets the Hash requirements (17.6.3.4) and acts as a hash function for argument values of type Key, and by a binary predicate Pred that induces an equivalence relation on values of type Key.

Using vector<float> as Key and not providing explicit hash and equivalence predicate types means the default std::hash<vector<float>> and std::equal_to<vector<float>> will be used.

The std::equal_to for the equivalence relation is fine, because there is an operator == for vectors, and that's what std::equal_to uses.

There is however, no std::hash<vector<float>> specialization, and that's probably what the linker error you didn't show us says. You need to provide your own hasher for this to work.

An easy way of writing such an hasher is to use boost::hash_range:

template <typename Container> // we can make this generic for any container [1]
struct container_hash {
    std::size_t operator()(Container const& c) const {
        return boost::hash_range(c.begin(), c.end());
    }
};

Then you can use:

std::unordered_map<floatVector, int, container_hash<floaVector>> map;

Of course, if you need different equality semantics in the map you need to define the hash and equivalence relation appropriately.

_{1. However, avoid this for hashing unordered containers, as different orders will produce different hashes, and the order in unordered container is not guaranteed.}

Use vectors as key in unordered_map

There are two errors in this example. First, your hasher's operator() parameter should be const.

std::size_t operator()(const std::vector<T> &in) const
//      Add const here ^^^^^

Second is you are defining your hashing type as vectorHasher<std::vector<std::size_t> > which would imply that T = std::vector<std::size_t>, meaning that you are trying to instantiate a hasher with std::size_t operator()(const std::vector<std::vector<std::size_t>> &in) const which is too many vectors. Remove the std::vector from your map type declaration like this :

typedef std::unordered_map< std::vector<std::size_t>, int, vectorHasher< std::size_t > > map_type;
//                        Remove std::vector from this template argument ^^^^^^^^^^^

Compilation error related to map and unordered_map: attempting to reference a deleted function

Following on from @JohnZwinck's (excellent) answer, I would say that using std::unordered_map with a vector as a key is usually a bad idea, because of the likely high cost of implementing any kind of effective hashing function.

The link John gave expands on this, but, essentially, the hash function has to inspect every element in the vector every time anything needs to be hashed. If the vector is large, well, ouch!

So std::map is likely to be a better choice here, because std::less (-> operator<) is likely to be cheap - as soon as we hit an element of the vector whose value differs between the two operands, we are done. Worst case, it is no more expensive (although it's true that std::unordered_map is more efficient than std::map when a cheap and effective hashing function does exist, especially, for example, if the key is something like an int).

Putting a vector of pairs in an unordered_map vs a map

To elaborate a little on this:
For std::map:

std::map is a sorted associative container that contains key-value pairs with unique keys.Keys are sorted by using the comparison function Compare. [...] Maps are usually implemented as red-black trees.

Said "function Compare" is a template parameter with default value std::less<Key>. So a map needs to compare values using < to sort them into the red-black-tree. std::vector supports (such a comparison)[https://en.cppreference.com/w/cpp/container/vector/operator_cmp].

std::unordered_map on the other hash requires a hash-function to put keys into hash buckets. The used hash function is a template parameter with a default value of std::hash<Key>.

std::hash has only an overload for vector<bool>, not for any generic vector. Unless you provide a custom hash function, the unordered_map has no way of computing a hash for the keys, that's what the errors message tells you too.

How to use a vector variants as key in unordered_map?

I enjoy a good terrible idea...

I have no idea how or why you would use something like this for something other than a "I wonder if I can get this to compile and run" example.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <variant>

using VariantType = std::variant<int, std::string, unsigned int>;
using VecVariantType = std::vector<VariantType>;

struct Hasher
{
    size_t operator()(const VecVariantType &v) const
    {
        size_t hash = 0;
        for (auto &val : v)
        {
            hash ^= std::hash<VariantType>()(val);
        }
        return hash;
    }
};

std::ostream& operator<<(std::ostream& out, std::pair<const VecVariantType, int> &p)
{
    out << "key: { ";
    bool needs_comma = false;
    for (auto &var : p.first)
    {
        if (needs_comma)
        {
            out << ", ";
        }
        if (std::holds_alternative<int>(var))
        {
            out << "int: " << std::get<int>(var);
            needs_comma = true;
        }
        if (std::holds_alternative<std::string>(var))
        {
            out << "string: " << std::get<std::string>(var);
            needs_comma = true;
        }
        if (std::holds_alternative<unsigned int>(var))
        {
            out << "uint: " << std::get<unsigned int>(var);
            needs_comma = true;
        }
    }
    out << " }, value: " << p.second;
    return out;
}

void lookup(const VecVariantType &var, std::unordered_map<VecVariantType, int, Hasher> &m)
{
    std::cout << "Lookup ";
    auto it = m.find(var);
    if (it != m.end())
    {
        std::cout << "success - " << *it << "\n";
    }
    else
    {
        std::cout << "failure\n";
    }
}

int main()
{
    std::unordered_map<VecVariantType, int, Hasher> m;
    auto one = VecVariantType { 1, "one", 1u };
    auto two = VecVariantType { 2, "two", 2u };
    auto three = VecVariantType { 3, "three", 3u };
    auto nnn = VecVariantType { 1, "one", 1u, 2, "two", 2u, 3, "three", 3u };
    m.emplace(one, 1);
    m.emplace(two, 2);
    m.emplace(three, 3);
    m.emplace(nnn, 999);

    std::cout << "Enumerating:\n";
    for (auto& item : m)
    {
        std::cout << "    " << item << "\n";
    }

    lookup(one, m);
    lookup(two, m);
    lookup(three, m);
    lookup(nnn, m);
}

https://repl.it/repls/AmazingCrushingOpen64

Why C++ STL hash table (unordered_map) doesn't accept vectors as keys

You'll notice Boost doesn't actually have an extension to accept a vector<T> as a key specifically - instead it has an extension that lets you use any Iterable - and it generates the hash only as a function of the Iterable's contents...

This may or may not be desirable, depending on:

If you want to use object-identity rather than object-value as the basis for hashing... or not.
If you're comfortable with hashing being a non-constant-time operation... or not.
- Just because boost::hash_range appears to be O(n) doesn't mean the underlying iterable won't take 5 minutes to return all hashable values for each call...
If the order of elements does - or doesn't matter.
- (I believe) using boost::hash_range or boost::hash_combine with one of two distinct but equivalent unordered_set objects will result in different hash-codes despite their value-equivalence.
If two conceptually different objects that can iterate over the same values (e.g. a vector<uint8_t> representing a data buffer, or queue<SomeEnum> where SomeEnum : uint8_t representing a queue of values) should have the same hahs-code... or not.

I suspect the team behind the STL doesn't like the fact that there's so many contextual "if"s described above which would mean it wouldn't be sensible to provide default behaviour and so they require you to always be more explicit with your hash-generation for arbitrary objects (besides, if you want Boost's behaviour, then just use Boost in the first place - it's not like Boost is competing with the STL).

Also see this QA: C++ unordered_map using a custom class type as the key

STL Unordered Map- inserting into a vector

The second in the pair is a vector<int>, so you construct a vector with 1 element initialized with 5 instead of push_back.

 categorySearch.insert(make_pair("hello", std::vector<int>(1,5)));

Live example: http://ideone.com/JlMUuN

If the item already exists, use the return value that unordered_map::insert gives you, which is a std::pair consisting of the iterator and a bool denoting the success of the insertion:

#include <vector>
#include <unordered_map>
#include <string>
#include <iostream>

using namespace std;
int main()
{
    typedef unordered_map<string, vector<int>> CMap;
    CMap category_map;
    category_map.insert(make_pair("hello", std::vector<int>(1, 5)));
    auto pr = category_map.insert(make_pair("hello", std::vector<int>(1, 5)));
    if (!pr.second)
        pr.first->second.push_back(10);
    cout << pr.first->second.size(); 
}

Live Example: http://ideone.com/svEqcD

You will see that the map entry for "hello" has now 2 items in the vector, since the second call to insert failed due to item previously existing.

See here: http://en.cppreference.com/w/cpp/container/unordered_map/insert

C++ Unordered_Map Fail When Used with a Vector as Key