Playing with unordered_multimap

Question

So, guys, I am playing with std::unordered multimap just for fun. I'd like to store (in this example) unsigned shorts, with a custom hash and equal.

What's the funny part? Having two items being equal if they're both even or odd.

So, as far as I understand, I can't use std::unordered_map, even though actual values differ: the custom predicate says otherwise. (correct me if I'm wrong, obviously!)

So to recap: I store different integers and therefore different hashes, but their values under the predicate might be the same.

#include <iostream>
#include <unordered_map>

class tt
{
public:

    tt(const unsigned short v = 0) : i(v) { };

    unsigned short i;
};

class tt_hash
{
public:
    size_t operator()(const tt &v) const
    {
        auto f = std::hash<unsigned short>();
        return f(v.i);
    };
};

class tt_equal
{
public:
    bool operator()(const tt &u, const tt &v) const
    {
        return (u.i % 2) == (v.i % 2);
    };
};

typedef std::unordered_multimap<tt, bool, tt_hash, tt_equal> mymap;

// Print all values that match a criteria
void f(const mymap &m, unsigned short c)
{
    auto range = m.equal_range(c);

    auto target = range.first;

    if (target == m.end())
    {
        std::cout << "not found : " << (int) c << std::endl;
    }
    else
    {
        for (auto i = target; i != range.second; i++)
            std::cout << "there is  : " << (int) i->first.i << " : " << i->second << std::endl;
    }

}

int main(int argc, const char * argv[])
{    
    mymap m;

    m.emplace(std::make_pair(tt(3), false));
    m.emplace(std::make_pair(tt(10), true));
    m.emplace(std::make_pair(tt(4), true));
    m.emplace(std::make_pair(tt(23), false));

    std::cout << "size " << m.size() << std::endl;
    std::cout << "buck " << m.bucket_count() << std::endl;

    int c = 0;

    for (auto i = m.begin(); i != m.end(); i++)
        std::cout << "# " << c++ << " : " << (int) i->first.i << " : " << i->second << std::endl;

    f(m, 3);

    return 0;
}

So, when I execute the code above I find the correct values, 3, 10, 4, 23 (not in this order of course).

Unexpectedly, when printing all the values matching 3 calling f(), I get two answers, 3 and 23; but when I ask for 1000, I expected to have all the even numbers printed, but I was wrong:

size 4
buck 5
# 0 : 4 : 1
# 1 : 10 : 1
# 2 : 3 : 0
# 3 : 23 : 0
there is  : 10 : 1

Am I missing something here? (the answer is obviously yes)

Answer 1

What you are doing is undefined behavior: equal elements should have equal hash values. According to the standard (emphasis mine)

23.2.5 Unordered associative containers [unord.req]

5 Two values k1 and k2 of type Key are considered equivalent if the container’s key equality predicate returns true when passed those values. If k1 and k2 are equivalent, the container’s hash function shall return the same value for both.

Since you define equivalence in terms of modulo 2, you also need to use the hash function on the modulo 2 of the integer being passed. It also means that you need std::unordered_multimap as soon as you have more than 2 elements.