void reserve(size_type n);           // (1) C++11
constexpr void reserve(size_type n); // (1) C++26

概要

コンテナが、リハッシュされずに少なくとも引数 n で指定された要素数格納できるようにバケット数を調整（リハッシュ）する。

効果

引数を ceil(n / max_load_factor()) にした rehash() と等価である。
( Visual C++ 2012の実装では n / max_load_factor() + 0.5f で呼んでいる)

戻り値

なし

例外

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

計算量

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

備考

• C++14 までの規格の記載では、要素挿入時のリハッシュ条件に誤りがあったため、効果に記載の処理内容では n - 1 要素しか格納することができない場合があった。
  C++17 でリハッシュ条件が修正され、確実に n 要素格納できるようになったが、処理系によっては現在でも n - 1 要素しか格納できない可能性があるため、注意が必要である。
  下記のバージョンの記載も参照のこと。
• リハッシュされる条件については、insert()、emplace()、emplace_hint() も参照。
• リハッシュが行われた場合、
  • 全てのイテレータが無効になる。
  • 要素間の順番が変わる。
  • 要素の格納されているバケットが変更になる。
  • 要素へのポインタや参照は無効にならない。
• 現在のバケット数が既に ceil(n / max_load_factor()) 以上の場合の動作は、標準では特に規定されていない。

例

#include <iostream>
#include <unordered_map>

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

  um.max_load_factor(2.0F);

  um.emplace(0, 0);
  um.emplace(1, 1);
  um.emplace(2, 2);
  um.emplace(3, 3);

  std::cout << "current max_load_factor: " << um.max_load_factor() << '\n';
  std::cout << "current size: " << um.size() << '\n';
  std::cout << "current bucket_count: " << um.bucket_count() << '\n';
  std::cout << "current load_factor: " << um.load_factor() << '\n';
  std::cout << '\n';

  um.reserve(22);
  std::cout << "um.reserve(22)\n\n";

  std::cout << "new max_load_factor: " << um.max_load_factor() << '\n';
  std::cout << "new size: " << um.size() << '\n';
  std::cout << "new bucket_count: " << um.bucket_count() << '\n';
  std::cout << "new load_factor: " << um.load_factor() << '\n';
}

出力例

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

um.reserve(22)

new max_load_factor: 2
new size: 4
new bucket_count: 11
new load_factor: 0.363636

考察

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

バージョン

言語

• C++11

処理系

• Clang: 3.2 ✅
• GCC: 4.5.4 ✅
• Visual C++: 2012 ✅

備考

• Clang 3.3 以降は C++17 モードでなくても C++17 の条件でのリハッシュとなっている。
• GCC は 8.2.0 時点でまだ C++17 の条件でのリハッシュとなっていない。また、バージョンによってリハッシュ条件が微妙に異なるため注意。

関連項目

参照

• LWG Issue 1189. Awkward interface for changing the number of buckets in an unordered associative container
  • C++11で、要素数を指定してバケット数を確保するreserve()が追加された。rehash()はバケット数を指定するため、要素数から計算する必要があった
• P3372R3 constexpr containers and adaptors
• LWG Issue 2156. Unordered containers' reserve(n) reserves for n-1 elements