How to use std::vector as the type of key for an std::unordered_map in C++?

Question

I'm trying to build an unordered map to contain points in n-dimensional space. I understand that std::vector meets all the requirements for being a key in std::map, and yet this code does not compile. I get a long list of error messages, but this seems the most problematic:

error: no match for call to ‘(const std::hash<std::vector<int> >) (const std::vector<int>&)'.

Does anyone have any idea as to why g++ doesn't seem to think that std::vector<int> is hashable?

#include <vector>
#include <unordered_map>
#include <boost/functional/hash.hpp>

using namespace std;

typedef vector<int> point;

int main()
{
    unordered_map<point, int>jugSpace;
    vector<int> origin(3, 0);

    jugSpace.insert( pair<point,int>(origin, 0) );
}

Possible duplicate of C++ unordered_map using a custom class type as the key — Saurav Sahu
– Saurav Sahu, Commented Dec 12, 2016 at 14:56
This doesn't directly relate to the question, but using vector<int> as a point seems unnecessarily expensive. Sensible uses of points all traffic in points with the same number of dimensions, so the variable size of a vector, and the resultant overhead, is generally not needed. I'd go with a struct with appropriate data members, or possible a template that takes the number of dimensions as a template argument and uses std::array internally. Of course, with either of these approaches you still have to make the point type hashable. — Pete Becker
– Pete Becker, Commented Dec 12, 2016 at 15:07
@SauravSahu I thought, being that vector<int> is a fairly common class, there would already be some support for hashing it in either the STL or Boost, an issue I don't think was covered in that question. Is it the case that there is not? — Monty Evans
– Monty Evans, Commented Dec 12, 2016 at 15:08

SergeyA · Accepted Answer · 2016-12-12 15:42:55Z

6

Unordered map requires availability of hash function for the key. Such function does not exist for std::vector in standard implementation.

You could use std::map, though - it requires comparison operator, which exists for vector.

If you really must use vector as a key to hash map (which seems dubious), you should implement hashing function yourself.

edited Dec 12, 2016 at 15:42

answered Dec 12, 2016 at 14:54

SergeyA

62.9k5 gold badges85 silver badges143 bronze badges

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

2 Comments

Jarod42 Over a year ago

en.cppreference.com/w/cpp/container/vector/operator_cmp, So you may use it in std::map.

Ricola Over a year ago

> You could use std::map, though - it requires comparison operator, which exists for vector You should point out that doing this might not lead to the same performance

Deedee Megadoodoo · Accepted Answer · 2016-12-12 15:35:04Z

5

You need to specialize template class std::hash<> for your point like:

namespace std {
  template<>
  class hash<point> {
  public:
    size_t operator()(const point &p) const {
      // put here your hash calculation code
    }  
  };
}

Or create custom hasher class and specify its type as template member for std::unordered_map:

class my_hash {
public:
  size_t operator()(const point &p) const {
    // your hash calculation code
  }
};

// somewhere in your code, where you declare your unordered_map variable
std::unordered_map<point, int, my_hash> myUnorderedMap;

If you want to use boost::hash_value as hash function then just return its result in your hasher implementation, ex:

class my_hash {
public:
  size_t operator()(const point &p) const {
    return boost::hash_value(p);
  }
};

edited Dec 12, 2016 at 15:35

answered Dec 12, 2016 at 15:02

Deedee Megadoodoo

8738 silver badges22 bronze badges

5 Comments

Monty Evans Over a year ago

I can't be the first person to have needed a hash function for a vector though? I don't really understand the documentation, but it looks like boost defines that hash already in boost.org/doc/libs/1_62_0/doc/html/hash/reference.html.

Deedee Megadoodoo Over a year ago

@MontyEvans, I think you can return value of boost::hash_value(p); from any of hash functions

Monty Evans Over a year ago

Ah, okay, so just including the header file from boost won't do it for me, I need to write a hash function and then return the value as given by boost?

Deedee Megadoodoo Over a year ago

@MontyEvans, that's right. I've just updated my post for you.

Monty Evans Over a year ago

Thanks a million! I've downloaded boost and it's all working now.

Collectives™ on Stack Overflow

How to use std::vector as the type of key for an std::unordered_map in C++?

2 Answers 2

2 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related