STL Veri Yapısı - unordered_map Tanımlama

Tanımlama
Sınıfın template parametreleri şöyle

template <class Key,
          class T,
          class Hash = hash<Key>,  // implement if missing
          class Pred = equal_to<Key>,  // implement if missing
          class Alloc = allocator<pair<const Key,T>>
          >
class unordered_map;

key alanımız için default hash ve equality metodları varsa tanımlama çok kolay

Örnek - key std::string
Şöyle yaparız.

std::unordered_map<std::string, std::unique_ptr<Foo>> myMap;

Örnek - key uint8_t
Şöyle yaparız

std::unordered_map<uint8_t, MyValue> myMmap;

Bu durumda aslında şöyle bir şey tanımlamış oluruz.

std::unordered_map<uint8_t,MyValue,
                   std::hash<uint8_t>,std::equal_to<uint8_t>> myMmap;

Kendi Hash Ve Equality Metodumuz
1. Functor
Kendi hash ve equality metodlarımızı kullanmak istersek şöyle tanımlarız. Önce hash ve equality metodlarımızı yazarız.

struct hash_equ {
  // Hasher
  size_t operator()(myType const &val) const;

  // Equality comparer
  bool operator()(myType const &a, myType const &b) const;
};

Daha sonra  veri yapısını tanımlarız.

std::unordered_map<myType const &, int, hash_equ, hash_equ> myMmap;

Eğer arzu edersek hash ve equality sınıflarımız ayrı ayrı olabilir. Önce hash sınıfımızı yazarız.

class MyHash {
public:
  std::size_t operator()(const MyClass &p) const {
    return ...;
  }
};

Daha sonra equality sınıfımızı yazarız.

class MyEquals {
public:
  bool operator()(const MyClass& lhs, const MyClass& rhs) const {
    return ...;
  }
};

Son olarak veriyapımızı yazarız.

std::unordered_map<MyClass ,int, MyHash, MyEquals> map;

2. std İsim Alanı
std isim alanına bir şey eklemeyi hiç sevmiyroum ve bu yöntemi tercih etmiyorum.

Örnek
Elimizde == operatör'ü olan yapılarımız olsun.

struct v4RouteKey_t { 
  std::array<uint8_t, 4> ipv4; uint32_t val; 

  bool operator==(v4RouteKey_t const& other) const {
    return std::tie(ipv4, val) == std::tie(other.ipv4, other.val);
  };
};
struct v6RouteKey_t { 
  std::array<uint8_t, 16> ipv6; uint32_t val; 
  bool operator==(v6RouteKey_t const& other) const {
    return std::tie(ipv6, val) == std::tie(other.ipv6, other.val);
  };
};

Bu yapılar için std isim alanına hash tanımlarız.

namespace std {

  template <> struct hash<v4RouteKey_t> {
    size_t operator()(v4RouteKey_t const& key) { 
      return std::accumulate(key.ipv4.begin(), key.ipv4.end(), size_t(key.val),
        [](size_t seed, uint8_t b) { return (seed*139) ^ b; });
    }
  };
  template <> struct hash<v6RouteKey_t> {
    size_t operator()(v6RouteKey_t const& key) { 
      return std::accumulate(key.ipv6.begin(), key.ipv6.end(), size_t(key.val),
        [](size_t seed, uint8_t b) { return (seed*139) ^ b; });
    }
  };
}

Daha sonra bu yapılar için key tipi variant olan bir map tanımlayabiliriz. Şöyle yaparız.

struct RouteValue_t {};

typedef std::variant<v4RouteKey_t, v6RouteKey_t> RouteKey;
typedef std::unordered_map<RouteKey, RouteValue_t> RouteMap;

RouteMap map;

Örnek
Elimizde Foo sınıfı olsun

class Foo {
public: 
  int id;
};

std isim alanında ismi hash ve equal_to olan iki tane functor tanımlarız. Şöyle yaparız.

namespace std
{
  template<> 
  struct hash<Foo> {
    std::size_t operator()(Foo const& f) const {
      return std::hash<int>()(f.id);
    }
  };

  template<>
  struct equal_to<Foo> {
    bool operator()(const Foo &lhs, const Foo &rhs) const {
      return lhs.id == rhs.id;
    }
  };
}

Şöyle yaparız

unordered_map<Foo, int> dict;

Foo f;
f.id = 123;

dict[f] = 1;

Sadece Kendi Hash Metodumuz

Eğer key nesnemizin equality metodu varsa, sadece kendi hash metodumuzu tanımlamamız yeterli. Kendi hash metodumuz unordered_map'i tanımlarken üçüncü parametre olarak veriliyor.

std::unordered_map<int_pair, int, MyHashFunc> m;

Tüm STL algoritmalarında olduğu gibi, function pointer, functor ve class method yöntemlerinden birisini kullanabiliriz. Hash işlemi için std::hash() kullanılabilir. std::hash() anladığım kadarıyla bir seed'i combine ederek birleştiremiyor. Dolayısıyla boost::hash_combine()'ı kullanmak daha iyi olabilir.

1. Functor

Functor size_t tipinde bir değer döner. 

Örnek 1

Şöyle yaparız

struct name_hash  
{ 
  size_t operator() (std::string* name)
  {
     std::hash<std::string> h;
     return h(*name);
  }
};

Örnek 2

Kendi sınıflarımızın hashCode diye metodu olduğunu varsayalım. Functor template olabilir. Functor const parametre alır ve const imzaya sahiptir. Şöyle yaparız.

struct MyHash
{
  template <class T>
  std::size_t operator()(T const & t) const 
  {
    return t.hashCode();
  }
};

Örnek 3

Şöyle yaparız.

template <typename T>
struct vectorHasher{
  std::size_t operator()(const std::vector<T> &v) const  {
    ...
  }
};

unordered_map'i tanımlamak için şöyle yaparız.

typedef std::unordered_map< std::vector<std::size_t>, int,
  vectorHasher< std::size_t > > map_type;

2. std İsim Alanı

std isim alanına bir şey eklemeyi hiç sevmiyroum ve bu yöntemi tercih etmiyorum. Elimizde bir sınıf olsun.

struct Foo {
  const int start;
  ...

  bool operator==(const int &other) const
  {
    return (start == other.start);
  }
};

Bu sınıf için std isim alanında ismi hash olan bir functor tanımlarız. Şöyle yaparız.

namespace std {
  template<>
  struct hash<Foo> {
    size_t operator()(const Foo& fıı) const {
      return hash<int>()(foo.start);
    }
  };
}

Bir unordered_map tanımlarız.Şöyle yaparız.

unordered_map<Foo, vector<int>> map;

Foo f(1);

map.insert(make_pair(f, vector<int>()));