最終更新日時:
が更新

履歴 編集

function
<unordered_set>

std::unordered_set::max_load_factor(C++11)

float max_load_factor() const noexcept; // (1)
void max_load_factor(float z);          // (2)

概要

  • (1) : 負荷率(バケットあたりの要素数の平均)の最大値を取得する。
  • (2) : 負荷率(バケットあたりの要素数の平均)の最大値を設定する。

要件

z は正の数であること。

効果

  • (1) : なし。
  • (2) : 引数 z を「ヒント」として、負荷率(バケットあたりの要素数の平均)の最大値を変更する「かもしれない」。

戻り値

  • (1) : 負荷率(バケットあたりの要素数の平均)の最大値
  • (2) : なし

例外

投げない。

計算量

定数。

備考

  • max_load_factor はその名前の通り、load_factor の最大値(上限)を定義する。
    従って、insertemplaceemplace_hint で要素が追加された際、および、operator= による initializer_list からの代入で要素数が増加した際には、load_factormax_load_factor() 以下になるように、必要に応じてバケット数が調整される。
    なお、min_load_factor のようなものはないので、erase で要素が削除された際にも、バケット数の調整は行われない。
    (標準では、erase が呼び出された際に、削除された要素を指すイテレータ、および、参照以外は無効にならないと規定されているため、調整できないと思われる)

  • (2) の形式では、効果にもある通り引数 z は「ヒント」であり、設定も変更される「かもしれない」となっているため、確定的な事は何も無いが、少なくとも load_factor() <= z が満たされていれば z に従って設定されると考えてよいと思われる。
    一方、load_factor() > z の場合、単純に無視するか load_factor() に設定するのが適切と思われるが、z をそのまま設定する実装もある。
    なお、計算量が定数であることからわかるように、いずれの場合でもリハッシュ(バケット数の調整)は行われない(はずだが、load_factor() > z の場合に load_factor() <= z を満たすようにリハッシュされる実装も多い)。

#include <iostream>
#include <unordered_set>

template<class C>
void print(const C& c)
{
  std::cout << "size is " << c.size() <<
    ", bucket_count is " << c.bucket_count() <<
    ", load_factor is " << c.load_factor() <<
    ", bucket_count * max_load_factor is " << static_cast<float>(c.bucket_count()) * c.max_load_factor() << '\n' << std::endl;
}

int main()
{
  std::unordered_set<int> us(12);

  std::cout << "max_load_factor is " << us.max_load_factor() << "\n\n"; // (1) の形式。max_load_factor のデフォルトは 1.0f。
  print(us);

  us.max_load_factor(2.0f); // (2) の形式。max_load_factor を 2.0f に設定。

  float z = us.max_load_factor(); // (1) の形式。上記で設定した値。
  std::cout << "max_load_factor is " << z << "\n\n";
  print(us);

  decltype(us)::size_type b = us.bucket_count();
  float limit = static_cast<float>(b) * z;

  // max_load_factor を超えるちょっと前まで要素を追加。
  decltype(us)::size_type i = 1;
  for (; i < limit; ++i) {
    us.emplace(i);
  }

  // max_load_factor を超えて bucket_count が変わるまで、状態を出力しつつ要素を追加。
  for (; us.bucket_count() == b; ++i) {
    print(us);
    us.emplace(i);
  }

  // bucket_count が変わった直後の状態を出力。
  print(us);

  us.max_load_factor(us.load_factor() / 2.0f); // (2) の形式。max_load_factor を現在の値の 1/2 を引数にして呼び出し。

  z = us.max_load_factor(); // (1) の形式。上記で設定した値。
  std::cout << "max_load_factor is " << z << "\n\n";

  // 最終的な状態を出力。
  print(us);
}

出力

libstdc++ の出力例(4.7.2 時点)

  • load_factor() > z の場合に、max_load_factor()z を設定して load_factor() < max_load_factor() となるようにリハッシュされている。

  • size() = 0 の場合にバケット数が減っている。

  • emplace() では、load_factor()max_load_factor() に達する前にバケット数が増加している。

max_load_factor is 1

size is 0, bucket_count is 29, load_factor is 0, bucket_count * max_load_factor is 29

max_load_factor is 2

size is 0, bucket_count is 2, load_factor is 0, bucket_count * max_load_factor is 4

size is 3, bucket_count is 2, load_factor is 1.5, bucket_count * max_load_factor is 4

size is 4, bucket_count is 7, load_factor is 0.571429, bucket_count * max_load_factor is 14

max_load_factor is 0.285714

size is 4, bucket_count is 29, load_factor is 0.137931, bucket_count * max_load_factor is 8.28572

libc++ の出力例(2012/12/19 現在)

  • load_factor() > z の場合に、max_load_factor()load_factor() の値を設定してリハッシュはされていない。

  • size() = 0 の場合にもバケット数は減っていない。

  • emplace() では、load_factor()max_load_factor() を超えた際にバケット数が増加している。

max_load_factor is 1

size is 0, bucket_count is 13, load_factor is 0, bucket_count * max_load_factor is 13

max_load_factor is 2

size is 0, bucket_count is 13, load_factor is 0, bucket_count * max_load_factor is 26

size is 25, bucket_count is 13, load_factor is 1.92308, bucket_count * max_load_factor is 26

size is 26, bucket_count is 13, load_factor is 2, bucket_count * max_load_factor is 26

size is 27, bucket_count is 29, load_factor is 0.931035, bucket_count * max_load_factor is 58

max_load_factor is 0.931035

size is 27, bucket_count is 29, load_factor is 0.931035, bucket_count * max_load_factor is 27

バージョン

言語

  • C++11

処理系

参照

operator= 代入演算子
emplace コンテナ内への要素の直接構築
emplace_hint 挿入位置のヒントを使用したコンテナ内への要素の直接構築
insert 要素の追加
size 要素数の取得
bucket_count バケット数の取得
load_factor 現在の負荷率(バケットあたりの要素数の平均)を取得
rehash 最小バケット数指定によるバケット数の調整
reserve 最小要素数指定によるバケット数の調整