Skip to content

Latest commit

 

History

History
195 lines (162 loc) · 8.36 KB

hash.md

File metadata and controls

195 lines (162 loc) · 8.36 KB
Raw

hash

  • functional[meta header]
  • std[meta namespace]
  • class template[meta id-type]
  • cpp11[meta cpp]
namespace std {
  template <class T> struct hash;

  // ハッシュ関数の特殊化
  template <> struct hash<bool>;
  template <> struct hash<char>;
  template <> struct hash<signed char>;
  template <> struct hash<unsigned char>;
  template <> struct hash<char8_t>;    // C++20
  template <> struct hash<char16_t>;
  template <> struct hash<char32_t>;
  template <> struct hash<wchar_t>;
  template <> struct hash<short>;
  template <> struct hash<unsigned short>;
  template <> struct hash<int>;
  template <> struct hash<unsigned int>;
  template <> struct hash<long>;
  template <> struct hash<long long>;
  template <> struct hash<unsigned long>;
  template <> struct hash<unsigned long long>;
  template <> struct hash<float>;
  template <> struct hash<double>;
  template <> struct hash<long double>;
  template <> struct hash<nullptr_t>;  // C++17
  template<class T> struct hash<T*>;
}

概要

クラステンプレートhashは、非順序連想コンテナ（unordered_map/unordered_multimap/unordered_set/unordered_multiset）のキーとなる型のためのハッシュ値を計算する関数オブジェクトである。

このクラスはそのものにデフォルトの定義は存在せず、ユーザーが任意の型で特殊化する際の要件を定義する。hashクラステンプレートを特殊化する場合、以下に記述するメンバ関数を持たせる必要がある。

<functional>ヘッダでは、以下の特殊化を提供する。これ以外の特殊化は、対象型を定義する各種ヘッダファイルにて提供される：

型 対応バージョン
bool C++11
char C++11
signed char C++11
unsigned char C++11
char8_t C++20
char16_t C++11
char32_t C++11
wchar_t C++11
short C++11
unsigned short C++11
int C++11
unsigned int C++11
long C++11
long long C++11
unsigned long C++11
unsigned long long C++11
float C++11
double C++11
long double C++11
全ての型へのポインタ C++11
全ての列挙型 C++14
nullptr_t C++17

メンバ関数

名前 説明
hash()
hash(const hash&)
hash(hash&&)		 デフォルトコンストラクタ、コピーコンストラクタ、ムーブコンストラクタを持つ
~hash() デストラクタを持つ
hash& operator=(const hash&)
hash& operator=(hash&&)		 コピー代入演算子とムーブ代入演算子を持つ
size_t operator()(T key) const 関数呼び出し演算子によって、キーに対応するハッシュ値を返す

メンバ型

名前 説明 対応バージョン
is_transparent 省略可。ハッシュ計算の関数オブジェクトがこの型を持っている場合、非順序連想コンテナの透過的な検索関数が有効になる。
この型は、例としてhash<string>がhash<const char*>やhash<string_view>と等価なハッシュ値を生成できるような場合に定義される。		 C++20

例

基本的な使い方

#include <iostream>
#include <functional>

int main()
{
  int x;

  // char型の値'C'に対するハッシュ値を求める
  std::cout << std::hash<char>()('C') << std::endl;

  // int型の値100に対するハッシュ値を求める
  std::cout << std::hash<int>()(100) << std::endl;

  // double型の値3.14に対するハッシュ値を求める
  std::cout << std::hash<double>()(3.14) << std::endl;

  // int*型のアドレス値(&x)に対するハッシュ値を求める
  std::cout << std::hash<int*>()(&x) << std::endl;
}
  • std::hash[color ff0000]

出力例

67
100
1427109137
3219530756

透過的にハッシュ値を計算できる場合 (C++20)

is_transparentが定義される場合、以下のようなコードにおいて、find()メンバ関数に文字列リテラルを指定しても、一時的なstringオブジェクトが作成されず、パフォーマンス向上が期待できる。

#include <iostream>
#include <unordered_map>
#include <string>
#include <string_view>

struct string_hash {
  using is_transparent = void;
  // string/string_view/const char*共用ハッシュ計算
  size_t operator()(std::string_view sv) const {
    return std::hash<std::string_view>{}(sv);
  }
};

int main()
{
  std::unordered_map<std::string, int, string_hash, std::equal_to<>> um = {
    {"Alice", 3},
    {"Bob", 1},
    {"Carol", 4}
  };

  // string_hashおよびstd::equal_to<>はいずれもメンバ型にis_transparentを持つため、
  // find()などの検索関数に引数を渡す場合に、std::string一時オブジェクトが作られない
  auto it = um.find("Alice");
  if (it != um.end()) {
    std::cout << "found : " << it->second << std::endl;
  }
}
  • um.find[link /reference/unordered_map/unordered_map/find.md]
  • um.end()[link /reference/unordered_map/unordered_map/end.md]

出力

found : 3

バージョン

言語

  • C++11

処理系

関連項目

ヘッダ 特殊化対象
<coroutine> std::coroutine_handle
<bitset> std::bitset
<filesystem> std::filesystem::path
<optional> std::optional
<memory> std::shared_ptr, std::unique_ptr
<stacktrace> std::basic_backtrace, std::stacktrace_entry
<string> std::stringなど
<string_view> std::string_viewなど
<system_error> std::error_code, std::error_condition
<thread> std::thread:id
<typeindex> std::type_index
<variant> std::variant, std::monostate
<vector> std::vector<bool>

参照