unordered map without hashing

Question

I'd like to use a structure just like std::map but without ordering, I don't need ordering and my key is pretty huge, so it's "less than" comparision takes time. So, I saw unordered_map but it has a hash template argument, so, how to use unordered_map without hashing? I'll really need to build my own container?

This question applies to std::set too.

EDIT Some answers have suggested to create my own hash, but I can't do this, I should have specified it here. The key contains floating point data, so hashing it would be a real bad idea. I need to compare (std::equal_to) directly.

What do you want this container to be able to do? `std::hash_map` etc. provide fast lookup, based on hashing. If you don't want hashing, then you don't get fast lookup or you have to provide some other mechanism. — Pete Becker, Dec 08 '13 at 19:36
It sounds you want to map you keys to some value. How do you envision that mapping to be done? `std::map<...>` uses the less than relation to locate objects. The ordering just falls out of its internal structure. The unordered containers use a hash to locate the objects rather than an ordering. If you don't want either, you'll need to describe how you imagine the keys are to be found... — Dietmar Kühl, Dec 08 '13 at 19:40
`std::unordered_map` is likely more than suitable for your requirements. Consider focusing on how to successfully use your own types as a container key. — Captain Obvlious, Dec 08 '13 at 20:07
@Captain Obvlious Actually I have "found" how to make my type as a key. In the case of the std::map, the operator< is overloaded in way that it makes the 'ordering' based on checks from the first to the last field. Like, if first field from a and b are not equal, returns which one is the lesser. If first field from a and b are equal, continue to the second field doing the same. If it reaches the last field and they are equal, return false. — Denilson Amorim, Dec 08 '13 at 20:11

score 1 · Answer 1 · answered Dec 08 '13 at 19:41

1

Create your own hash, it's easily done by composing the overloads of std::hash on the fields of your key.

The cppreference example (same as previous link) is quite good (even if you do not need the template stuff):

struct S
{
    std::string first_name;
    std::string last_name;
}; 

template <class T>
class MyHash;

template<>
class MyHash<S>
{
public:
    std::size_t operator()(S const& s) const 
    {
        std::size_t h1 = std::hash<std::string>()(s.first_name);
        std::size_t h2 = std::hash<std::string>()(s.last_name);
        return h1 ^ (h2 << 1);
    }
};

After that you can use it in the std::unorderd_map:

std::unordered_map<S, Value, MyHash<S>> the_map;

By the way std::unordered_set also need a hash.

answered Dec 08 '13 at 19:41

Johan

3,728
16
25

@LINK2012 Hashing is done on `float` and `double`... That's even provided by the `std::hash` function.... The goal of the hash is just to fine the bucket, no more no less. – Johan Dec 08 '13 at 19:56
But std::hash for floating points just hash its bits (at least in GNU implementation), and for example 5.12 have "many" ways to be represented in IEEE representation – Denilson Amorim Dec 08 '13 at 20:04
@LINK2012 [Are you sure ?](http://stackoverflow.com/questions/17251767/all-real-numbers-that-have-more-than-1-representation-in-ieee-754-of-single-prec) – Johan Dec 08 '13 at 20:11
I probably didn't express my point precisely, I mean [something like this](http://stackoverflow.com/questions/17333/most-effective-way-for-float-and-double-comparison) – Denilson Amorim Dec 08 '13 at 20:13
@LINK2012 They you're not looking for an exact match of the element. You'll have the problem on the comparison operator. If you handle it on the comparison operator, just do not hash the float. – Johan Dec 08 '13 at 20:15

score 0 · Answer 2 · answered Dec 08 '13 at 19:41

You need to spetialize hash object for your key before declaring your unordered_map.

    namespace std
    {
    template <>
    class hash<Key>
    {
    public:
      size_t operator()(const Key &) const
      {
        // ... your hash function for Key object ...

      }
    };
    }

    std::unordered_map<Key, Value> myMap;

Example, if I want you use as a key pair:

    namespace std
    {
    class hash<pair<string, int>>
    {
    public:
      size_t operator()(const pair<string, int> &s) const
      {
        size_t h1 = hash<string>()(s.first);
        size_t h2 = hash<int>()(s.second);
        return h1 ^ (h2 << 1);
      }
    };
    }

    unordered_map<pair<string, int>, string> myMap;

unordered map without hashing

2 Answers2