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

Question

Background: I am comming from the Java world and I am fairly new to C++ or Qt.

In order to play with unordered_map, I have written the following simple program:

#include <QtCore/QCoreApplication>
#include <QtCore>
#include <iostream>
#include <stdio.h>
#include <string>
#include <unordered_map>

using std::string;
using std::cout;
using std::endl;
typedef std::vector<float> floatVector;

int main(int argc, char *argv[]) {
    QCoreApplication a(argc, argv);
    
    floatVector c(10);
    floatVector b(10);
    
    for (int i = 0; i < 10; i++) {
        c[i] = i + 1;
        b[i] = i * 2;
    }
    
    std::unordered_map<floatVector, int> map;
    
    map[b] = 135;
    map[c] = 40;
    map[c] = 32;
  
    std::cout << "b -> " << map[b] << std::endl;
    std::cout << "c -> " << map[c] << std::endl;
    std::cout << "Contains? -> " << map.size() << std::endl;
    
    return a.exec();
}

Unfortunately, I am running into the folowing error which isn't inspiring. There is not even a line number.

:-1: error: collect2: ld returned 1 exit status

Any idea of the origin of the problem?

@SethCarnegie That was what I though the problem was comming too. However, it seems to me that a class as basic as vector should have a default hash function. If it isn't the case, could you explain me how to provide one or point me to some material. Thank you! — Pierre-Antoine
– Pierre-Antoine, Commented May 1, 2012 at 22:11
Valid and interesting question, but I don't see a use case where it will be clever to use a list as a key in a map. — UmNyobe
– UmNyobe, Commented May 1, 2012 at 22:15
@UmNyobe The int is the result of a heavy computation from which the vector is the input. The result once computed need to be access many times and quickly. — Pierre-Antoine
– Pierre-Antoine, Commented May 1, 2012 at 22:23

ildjarn · Accepted Answer · 2012-05-01 23:51:33Z

36

§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.}

edited May 1, 2012 at 23:51

ildjarn

63.2k9 gold badges135 silver badges219 bronze badges

answered May 1, 2012 at 22:13

R. Martinho Fernandes

236k73 gold badges443 silver badges518 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Pierre-Antoine Over a year ago

Thank you very much this indeed solved my problem. Note for people that would have the same problem: to use boost::hash_range you need to #include <boost/functional/hash.hpp>

ildjarn Over a year ago

@user1162647 : That's literally the first thing on that doc page. ;-]

ForeverLearning Over a year ago

@R. Martinho Fernandes : If you're still watching, the docs in that page say: "hash_range is sensitive to the order of the elements so it wouldn't be appropriate to use this with an unordered container." Does that suggest the above usage is wrong?

R. Martinho Fernandes Over a year ago

@Dilip I think what that means is that calling hash_range (unordered_container) is a bad idea because it can produce different results each time.

Chirag Arora Over a year ago

@hash3r That's because map uses red and black trees at the backend and is not concerned with the kind of data stored. Whereas, unordered_map essentially needs a hash function. And it can only be calculated once the kind of data stored in the vector is ascertained.

|

Chirag Arora · Accepted Answer · 2020-06-18 16:20:29Z

24

I found R. Martinho Fernandes's answer unsuitable for competitive programming since most of the times you have to deal with a provided IDE and cannot use an external library such as boost. You can use the following method if you'd like to make the best of STL.

As already stated above, you just need to write a hash function. And it should specialize for the kind of data stored in your vector. The following hash function assumes int type data:

struct VectorHasher {
    int operator()(const vector<int> &V) const {
        int hash = V.size();
        for(auto &i : V) {
            hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);
        }
        return hash;
    }
};

Note that you can use any kind of operation to generate a hash. You just need to be creative so that collisions are minimized. For example, hash^=V[i], hash|=V[i], hash+=V[i]*V[i] or even hash+=(V[i]<<i)*(V[i]<<i)*(V[i]<<i) are all valid until of course, your hash doesn't overflows.

Finally to use this hash function with your unordered_map, initialize it as follows:

unordered_map<vector<int>,string,VectorHasher> hashMap;

edited Jun 18, 2020 at 16:20

answered Nov 13, 2018 at 15:11

Chirag Arora

9561 gold badge9 silver badges23 bronze badges

4 Comments

wcochran Over a year ago

Shouldn’t the second template parameter be int instead of bool?

Chirag Arora Over a year ago

@wcochran It works with any permitted data structure/type(map, vector, set, queue, stack, int, float, ...etc). Depends on your use case.

Caleth Over a year ago

If you are not bothering with a sensible hash, why not go all the way with template <typename T> struct AnyHasher { int operator()(const T &) { return 0; } } ?

Chirag Arora Over a year ago

@Caleth do you think it is sensible enough now?

Collectives™ on Stack Overflow

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

2 Answers 2

6 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related