google::dense_hash_mapを使う

google::dense_hash_map?

使い方

  • ヘッダオンリーなのでソースをダウンロードして#includeするだけ
  • 使う前にset_empty_key(key)を実行しなければいけない ←これ重要
    • ここで設定したキーは、ハッシュマップに格納できなくなる
    • これがstd::unrodered_mapと比べたときの欠点
  • また、要素を削除する前にset_deleted_key(key)を実行する必要あり
    • 要素を削除しない(挿入するだけ)場合は不要
    • set_empty_key(key)とは別のキーを設定しなければならない
  • その他は基本的にstd::unordered_mapと同じ

サンプルコード

#include <iostream>
#include <string>

#include "google/dense_hash_map"

int main() {
  google::dense_hash_map<std::string, std::string> smap;
  smap.set_empty_key("Mori");
  smap.insert({"Kimura", "Takuya"});
  smap.insert({"Kusanagi", "Tsuyoshi"});
  smap.insert({"Katori", "Shingo"});
  std::cout << smap["Kusanagi"] << std::endl;
  return 0;
}

注意点

  • バケット数の調整はreserve()ではなくresize()
  • clear()バケット数もリセットしてしまう
    • STLclear()と同じ挙動をするのはclear_no_resize()
    • clear_no_resize()するときはset_deleted_key(key)が必要

パフォーマンス