最終更新日時:
が更新

履歴 編集

function
<unordered_map>

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

void reserve(size_type n);

概要

コンテナが、リハッシュされずに少なくとも引数 n で指定された要素数格納できるようにバケット数を調整(リハッシュ)する。
実際には 引数を n / max_load_factor() にし rehash() を呼ぶ。
( VC11の実装では n / max_load_factor() + 0.5f で呼んでいる)

戻り値

なし

例外

ハッシュ関数、および、キー比較用関数以外から例外が投げられた場合、コンテナは変更されない。

計算量

平均的なケースでは size() に比例するが、最悪のケースでは size() の 2 乗に比例する。

備考

  • 本関数は、概要の通り、リハッシュされずに引数 n で指定された要素数格納できるように意図されているはずであるが、現在の条件では n - 1 しか格納することができない場合がある(少なくとも、事後条件を満たすだけでは確実に n 要素を格納できる保証はない)。この件については、既に Issue が上がっている(2156. Unordered containers' reserve(n) reserves for n-1 elements)。リハッシュされる条件については、insert()emplace()emplace_hint() も参照。
  • リハッシュが行われた場合、
    • 全てのイテレータが無効になる。
    • 要素間の順番が変わる。
    • 要素の格納されているバケットが変更になる。
    • 要素へのポインタや参照は無効にならない
  • 現在のバケット数が既に ceil(n / max_load_factor()) 以上の場合の動作は、標準では特に規定されていない。

#include <iostream>
#include <unordered_map>

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

  m.emplace( 1, 1 );
  m.emplace( 1, 1 );
  m.emplace( 2, 2 );
  m.emplace( 3, 3 );

  m.max_load_factor( 2.0f );

  std::cout << "current max_load_factor: " << m.max_load_factor() << std::endl;
  std::cout << "current size: " << m.size() << std::endl;
  std::cout << "current bucket_count: " << m.bucket_count() << std::endl;
  std::cout << "current load_factor: " << m.load_factor() << std::endl;
  std::cout << std::endl;

  m.reserve(20);
  std::cout << "m.reserve(20)" << std::endl;
  std::cout << std::endl;

  std::cout << "new max_load_factor: " << m.max_load_factor() << std::endl;
  std::cout << "new size: " << m.size() << std::endl;
  std::cout << "new bucket_count: " << m.bucket_count() << std::endl;
  std::cout << "new load_factor: " << m.load_factor() << std::endl;
}

出力例

current max_load_factor: 2
current size: 4
current bucket_count: 8
current load_factor: 0.5

m.reserve(20)

new max_load_factor: 2
new size: 4
new bucket_count: 16
new load_factor: 0.25

考察

reserve(20) により
bucket_count() > n / max_load_factor() を満たしている

バージョン

言語

  • C++11

処理系

参照

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