Skip to content

Latest commit

 

History

History
117 lines (89 loc) · 4.65 KB

bucket.md

File metadata and controls

117 lines (89 loc) · 4.65 KB

bucket

  • unordered_set[meta header]
  • std[meta namespace]
  • unordered_multiset[meta class]
  • function[meta id-type]
  • cpp11[meta cpp]
size_type bucket(const key_type& k) const;           // (1) C++11
constexpr size_type bucket(const key_type& k) const; // (1) C++26

template <class K>
constexpr size_type bucket(const K& k) const; // (2) C++26

概要

指定したキーと等価な要素が格納されている場合、そのバケットのインデックス(添え字)を取得する。

  • (1) : key_type型のキーを受け取って、バケットのインデックスを取得する
  • (2) : key_typeと比較可能なキーを受け取って、バケットのインデックスを取得する

テンプレートパラメータ制約

  • (2) : Hash::is_transparentおよびPred::is_transparentが妥当な式であること

事前条件

当該コンテナは bucket_count() > 0 であること

戻り値

パラメータ k と等価なキーの要素が格納されているバケットのインデックス(添え字)

事後条件

戻り値は [0, bucket_count()) の範囲である。

計算量

定数。

備考

  • 指定したキーと等価な要素が格納されていない場合、そのキーを挿入した際に rehash が発生しなければ格納されるバケットのインデックス(添え字)が返る。
  • (2) :
    • is_transparentは、HashとPredの両方がメンバ型として持つ必要がある。Predにはis_transparentを定義するstd::equal_to<>が使えるが、Hashには標準ライブラリに該当するものがないため、利用者が定義する必要がある。詳細はstd::hashクラスのページを参照。
    • これらのオーバーロードは、unordered_multiset<string>のようなコンテナに対し、検索操作で文字列リテラルを渡した際に、キー型の一時オブジェクトが生成されるコストを減らすためにある。

例

#include <iostream>
#include <string>
#include <unordered_set>

int main()
{
  std::unordered_multiset<std::string> ums{ "A", "B", "C", "D", "E", "A", "B", "C", "D", "E", };

  decltype(ums)::size_type c = ums.bucket_count();
  std::cout << "bucket_count() = " << c << std::endl;

  // 全てのキーに対するバケットのインデックスとそのバケットの要素数を取得
  for (decltype(ums)::key_type k : ums) {
    decltype(ums)::size_type b = ums.bucket(k);
    decltype(ums)::size_type s = ums.bucket_size(b);
    std::cout << "key = " << k << ", bucket = " << b << ", bucket_size = " << s << std::endl;
  }

  // 存在しないキーに対するバケットのインデックスとそのバケットの要素数を取得
  decltype(ums)::key_type k = "H";
  decltype(ums)::size_type b = ums.bucket(k);
  decltype(ums)::size_type s = ums.bucket_size(b);
  std::cout << "key = " << k << ", bucket = " << b << ", bucket_size = " << s << std::endl;
}
  • bucket[color ff0000]
  • ums.bucket_count()[link bucket_count.md]
  • ums.bucket_size[link bucket_size.md]

出力例

bucket_count() = 11
key = E, bucket = 6, bucket_size = 2
key = E, bucket = 6, bucket_size = 2
key = A, bucket = 5, bucket_size = 6
key = A, bucket = 5, bucket_size = 6
key = C, bucket = 5, bucket_size = 6
key = C, bucket = 5, bucket_size = 6
key = D, bucket = 5, bucket_size = 6
key = D, bucket = 5, bucket_size = 6
key = B, bucket = 7, bucket_size = 2
key = B, bucket = 7, bucket_size = 2
key = H, bucket = 3, bucket_size = 0

バージョン

言語

  • C++11

処理系

関連項目

名前 説明
max_bucket_count 最大バケット数の取得

参照