Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: How to use sf::Vector2f as a key-type in unordered associative containers  (Read 17289 times)

0 Members and 1 Guest are viewing this topic.

NGM88

  • Full Member
  • ***
  • Posts: 162
    • View Profile
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

  • Administrator
  • Hero Member
  • *****
  • Posts: 32504
    • View Profile
    • SFML's website
    • Email
Using anything based on floating point numbers as the key type in an associative container is... unusual. I wonder why you needed that stuff.
Laurent Gomila - SFML developer

NGM88

  • Full Member
  • ***
  • Posts: 162
    • View Profile
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

  • Hero Member
  • *****
  • Posts: 3346
  • My number of posts is shown in hexadecimal.
    • View Profile
    • Links
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.
Selba Ward -SFML drawables
Cheese Map -Drawable Layered Tile Map
Kairos -Timing Library
Grambol
 *Hapaxia Links*

NGM88

  • Full Member
  • ***
  • Posts: 162
    • View Profile
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

  • Hero Member
  • *****
  • Posts: 599
    • View Profile
    • Blog
    • Email
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;
}
Tomb Painter, Re:creation dev (abandoned, doing other things) | edw.is | @EliasDaler

Laurent

  • Administrator
  • Hero Member
  • *****
  • Posts: 32504
    • View Profile
    • SFML's website
    • Email
Quote
    std::size_t seed;
    hash_combine(seed, k.x);
Aren't you using seed without initialiazing it first?
Laurent Gomila - SFML developer

Elias Daler

  • Hero Member
  • *****
  • Posts: 599
    • View Profile
    • Blog
    • Email
Quote
    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...  8))
Tomb Painter, Re:creation dev (abandoned, doing other things) | edw.is | @EliasDaler

Laurent

  • Administrator
  • Hero Member
  • *****
  • Posts: 32504
    • View Profile
    • SFML's website
    • Email
Quote
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 ;)
Laurent Gomila - SFML developer

 

anything