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

履歴 編集

function
<unordered_map>

std::unordered_multimap::find(C++11)

iterator       find(const key_type& x);                    // (1) C++11
const_iterator find(const key_type& x) const;              // (2) C++11

iterator       find(const key_type& x, size_t hash);       // (3) C++20
const_iterator find(const key_type& x, size_t hash) const; // (4) C++20

template <class K> iterator       find(const K& k);        // (5) C++20
template <class K> const_iterator find(const K& k) const;  // (6) C++20

template <class K>
iterator       find(const K& k, size_t hash);              // (7) C++20
template <class K>
const_iterator find(const K& k, size_t hash) const;        // (8) C++20

概要

コンテナ内で指定されたキーに合致する要素を検索し、見つかった場合はそれへのイテレータを返し、見つからなかった場合は end (コンテナの最後の要素の次)を指すイテレータを返す。
指定されたキーに合致する要素の範囲を取得するには equal_rangeを用いる。
また、指定されたキーに合致する要素が存在するかを調べる場合は count を用いる。

  • (1) : 非const*thisオブジェクトに対する検索
  • (2) : const*thisオブジェクトに対する検索
  • (3) : 非const*thisオブジェクトに対して、事前計算したハッシュ値をつけて検索
  • (4) : const*thisオブジェクトに対して、事前計算したハッシュ値をつけて検索
  • (5) : 非const*thisオブジェクトに対する透過的な検索
  • (6) : const*thisオブジェクトに対する透過的な検索
  • (7) : 非const*thisオブジェクトに対して、事前計算したハッシュ値をつけて透過的に検索
  • (8) : const*thisオブジェクトに対して、事前計算したハッシュ値をつけて透過的に検索

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

パラメータ

  • x : 検索するキー。key_typemap コンテナの中で Key の別名として定義される。ここで Key は 1 番目のテンプレートパラメータである。
  • k : 検索するキー。key_typeと透過的に比較可能な型K型のキーである。

事前条件

  • (3), (4) : 値hashと、hash_function()(x)の戻り値が等値であること
  • (7), (8) : 値hashと、hash_function()(k)の戻り値が等値であること

戻り値

指定した値が見つかった場合はその要素へのイテレータ、そうでない場合は end へのイテレータ。

例外

投げない。

計算量

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

備考

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

基本的な使い方

#include <iostream>
#include <unordered_map>

int main()
{
  std::unordered_multimap<int, char> um;

  um.insert(std::make_pair(1, 'a'));

  std::cout << (um.find(1) != um.end()) << std::endl;
  std::cout << (um.find(2) != um.end()) << std::endl;

  return 0;
}

出力

1
0

事前計算しておいたハッシュ値を使用する (C++20)

#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++11

処理系

関連項目

名前 説明
count 指定したキーにマッチする要素の数を返す
equal_range 指定したキーにマッチする要素の範囲を返す

参照