最終更新日時(UTC):
が更新

履歴 編集

function
<unordered_map>

std::unordered_multimap::contains(C++20)

bool contains(const key_type& x) const;              // (1)
bool contains(const key_type& x, size_t hash) const; // (2)

template <class K>
bool contains(const K& k) const;                     // (3)
template <class K>
bool contains(const K& k, size_t hash) const;        // (4)

概要

指定されたキーに一致する要素がコンテナに含まれているかを判定する。

  • (1) : キーxを検索し、合致する要素が含まれるかを判定する
  • (2) : キーxを、事前計算したハッシュ値をつけて検索し、合致する要素が含まれるかを判定する
  • (3) : キーkを透過的に検索し、合致する要素が含まれるかを判定する
  • (4) : キーkを、事前計算したハッシュ値をつけて透過的に検索し、合致する要素が含まれるかを判定する

(3)と(4)の透過的な検索は、Hash::transparent_key_equalが定義される場合に有効になる機能であり、例としてunordered_multimap<string, int> m;に対してm.contains("key");のようにstring型のキーを持つ連想コンテナの検索インタフェースに文字列リテラルを渡した際、stringの一時オブジェクトが作られないようにできる。詳細はstd::hashクラスのページを参照。

事前条件

戻り値

xkを共通の変数aであるとして、以下と等価:

return find(a) != end();

計算量

  • 平均: 定数時間
  • 最悪: size について線形時間

備考

  • (3), (4) : このオーバーロードは、Hash::transparent_key_equal型が定義される場合にのみ、オーバーロード解決に参加する
  • (2), (4) : これらのオーバーロードは、キーに対するハッシュ値を事前に計算しておくことで、何度も同じキーで検索する場合に高速になる

基本的な使い方

#include <iostream>
#include <unordered_map>

int main()
{
  std::unordered_multimap<char, int> um = {
    {'a', 3},
    {'b', 1},
    {'c', 4}
  };

  // キー'b'の要素が含まれているか
  if (um.contains('b')) {
    std::cout << "contain" << std::endl;
  }
  else {
    std::cout << "doesn't contain" << std::endl;
  }
}

出力

contain

事前計算しておいたハッシュ値を使用する

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

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

  // ハッシュ値を事前計算
  const char* key = "Alice";
  std::size_t hash = um.hash_function()(key);

  // 事前計算しておいたハッシュ値を、検索インタフェースにキーといっしょに渡すことで、
  // 内部でのハッシュ値計算を省略できる
  if (um.contains(key, hash)) {
    auto it = um.find(key, hash);
    std::cout << it->first << ':' << it->second << std::endl;
  }
}

出力

Alice:3

バージョン

言語

  • C++20

処理系

参照