How to use sf::Vector2f as a key-type in unordered associative containers

[NGM88]

I was just about to put this into the wiki but my account was flagged for some reason. I'll just put it here for now and edit this to just include link when GitHub support fixes the issue.

This is my first contribution so all feedback is appreciated.

Title: How to use sf::Vector2f as a key-type in unordered associative containers

#include <SFML/Graphics.hpp>
#include <iostream>
#include <string>
#include <unordered_map>

struct Key
{
        sf::Vector2f key;

        bool operator==(const Key &other) const
        {
                return (key.x == other.key.x && key.y == other.key.y);
        }
};

struct KeyHasher
{
        std::size_t operator()(const Key& k) const
        {
                return ((std::hash<float>()(k.key.x) ^ (std::hash<float>()(k.key.y) << 1)) >> 1);
        }
};

int main()
{
        std::unordered_map<Key, std::string, KeyHasher> Map =
        {
                { { sf::Vector2f(1, 1) }, "one" } ,
                { { sf::Vector2f(2, 2) }, "two" }
        };

        // Individual Call
        std::cout << Map[{ sf::Vector2f(2, 2) }];

        // Loop
        for (auto& k : Map)
        {
                std::cout << k.second << std::endl;
        }

        return 0;
}
 

[Laurent]

Using anything based on floating point numbers as the key type in an associative container is... unusual. I wonder why you needed that stuff.

[NGM88]

Mapping tiles for a grid based game. It turned out to be better performance than using integers to map and using equations like:

   int X = ((i % LEVEL_SIZE) * (TILE_SIZE)) + (TILE_SIZE / 2);
   int Y = ((i / LEVEL_SIZE) * (TILE_SIZE)) + (TILE_SIZE / 2);

to find and access keys.

[Hapax]

As keys, wouldn't the integers just be:

x = i % LEVEL_SIZE;
y = i / LEVEL_SIZE;

assuming i is the index of the tile in the map.

[NGM88]

As keys, wouldn't the integers just be:

x = i % LEVEL_SIZE;
y = i / LEVEL_SIZE;

assuming i is the index of the tile in the map.

Yeah I accidentally pasted the thing that returns tile center coordinates.

[Elias Daler]

1) I'd suggest to use sf::Vector2i as a key for maps. Sometimes it can be useful. For example, I have std::unordered_map<sf::Vector2i, TileChunk> which allows me to have sparse tile maps
2) I'd also suggest to use boost::hash_combine. It can be defined somewhere as a free function (no Boost dependency)

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

And now you can do:

template<typename T>
...
std::size_t operator()(const Vector2<T>& k) const
{
    std::size_t seed;
    hash_combine(seed, k.x);
    hash_combine(seed, k.y);
    return seed;
}

[Laurent]

    std::size_t seed;
    hash_combine(seed, k.x);

Aren't you using seed without initialiazing it first?

[Elias Daler]

    std::size_t seed;
    hash_combine(seed, k.x);

Aren't you using seed without initialiazing it first?

Oops, yes, it should be zero initialized:

std::size_t seed = 0;

(some might say that UB will get more random hashes...  )

[Laurent]

some might say that UB will get more random hashes...

Hashes mustn't be random, (multiple calls to hash(x) must yield the same value), they must be uniformly distributed as much as possible.

And don't forget that with UB, anything is allowed to happen, not just random numbers