最終更新日時: 2026年02月17日 23時22分33秒 (JST)
Akira Takahashi が更新

履歴 編集

function
<unordered_map>

# std::unordered_map::コンストラクタ(C++11)

    unordered_map();           // (1) C++14
    constexpr unordered_map(); // (1) C++26

    explicit
      unordered_map(size_type n,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type()); // (2) C++14
    constexpr explicit
      unordered_map(size_type n,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type()); // (2) C++26

    explicit
      unordered_map(size_type n = 実装依存の既定値,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type()); // (1) + (2) C++11

    template <class InputIterator>
    unordered_map(InputIterator first, InputIterator last,
                  size_type n = 実装依存の既定値,
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& a = allocator_type());   // (3) C++11
    template <class InputIterator>
    constexpr
      unordered_map(InputIterator first, InputIterator last,
                    size_type n = 実装依存の既定値,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type()); // (3) C++26

    unordered_map(const unordered_map& v);           // (4) C++11
    constexpr unordered_map(const unordered_map& v); // (4) C++26

    unordered_map(unordered_map&& rv);           // (5) C++11
    constexpr unordered_map(unordered_map&& rv); // (5) C++26

    explicit unordered_map(const allocator_type& a);           // (6) C++11
    constexpr explicit unordered_map(const allocator_type& a); // (6) C++26

    unordered_map(const unordered_map& v,
                  const allocator_type& a);                    // (7) C++11
    unordered_map(const unordered_map& v,
                  const type_identity_t<allocator_type>& a);   // (7) C++23
    constexpr
      unordered_map(const unordered_map& v,
                    const type_identity_t<allocator_type>& a); // (7) C++26

    unordered_map(unordered_map&& rv,
                  const allocator_type& a);                    // (8) C++11
    unordered_map(unordered_map&& rv,
                  const type_identity_t<allocator_type>& a);   // (8) C++23
    constexpr
      unordered_map(unordered_map&& rv,
                    const type_identity_t<allocator_type>& a); // (8) C++26

    unordered_map(initializer_list<value_type> il,
                  size_type n = 実装依存の既定値,
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& a = allocator_type());   // (9) C++11
    constexpr
      unordered_map(initializer_list<value_type> il,
                    size_type n = 実装依存の既定値,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type()); // (9) C++26

    unordered_map(size_type n, const allocator_type& a);           // (10) C++14
    constexpr unordered_map(size_type n, const allocator_type& a); // (10) C++26

    unordered_map(size_type n,
                  const hasher& hf,
                  const allocator_type& a);   // (11) C++14
    constexpr
      unordered_map(size_type n,
                    const hasher& hf,
                    const allocator_type& a); // (11) C++26

    template <class InputIterator>
    unordered_map(InputIterator f,
                  InputIterator l,
                  size_type n,
                  const allocator_type& a);   // (12) C++14
    template <class InputIterator>
    constexpr
      unordered_map(InputIterator f,
                    InputIterator l,
                    size_type n,
                    const allocator_type& a); // (12) C++26

    template <class InputIterator>
    unordered_map(InputIterator f,
                  InputIterator l,
                  size_type n,
                  const hasher& hf,
                  const allocator_type& a);   // (13) C++14
    template <class InputIterator>
    constexpr
      unordered_map(InputIterator f,
                    InputIterator l,
                    size_type n,
                    const hasher& hf,
                    const allocator_type& a); // (13) C++26

    unordered_map(initializer_list<value_type> il,
                  size_type n,
                  const allocator_type& a);   // (14) C++14
    constexpr
      unordered_map(initializer_list<value_type> il,
                    size_type n,
                    const allocator_type& a); // (14) C++26

    unordered_map(initializer_list<value_type> il,
                  size_type n,
                  const hasher& hf,
                  const allocator_type& a);   // (15) C++14
    constexpr
      unordered_map(initializer_list<value_type> il,
                    size_type n,
                    const hasher& hf,
                    const allocator_type& a); // (15) C++26

    template <container-compatible-range<value_type> R>
    unordered_map(std::from_range_t, R&& rg,
                  size_type n = 実装依存の既定値,
                  const hasher& hf = hasher(),
                  const key_equal& eql = key_equal(),
                  const allocator_type& a = allocator_type());   // (16) C++23
    template <container-compatible-range<value_type> R>
    constexpr
      unordered_map(std::from_range_t, R&& rg,
                    size_type n = 実装依存の既定値,
                    const hasher& hf = hasher(),
                    const key_equal& eql = key_equal(),
                    const allocator_type& a = allocator_type()); // (16) C++26

    template <container-compatible-range<value_type> R>
    unordered_map(std::from_range_t, R&& rg,
                  size_type n,
                  const allocator_type& a);   // (17) C++23
    template <container-compatible-range<value_type> R>
    constexpr
      unordered_map(std::from_range_t, R&& rg,
                    size_type n,
                    const allocator_type& a); // (17) C++26

    template <container-compatible-range<value_type> R>
    unordered_map(std::from_range_t, R&& rg,
                  size_type n,
                  const hasher& hf,
                  const allocator_type& a);   // (18) C++23
    template <container-compatible-range<value_type> R>
    constexpr
      unordered_map(std::from_range_t, R&& rg,
                    size_type n,
                    const hasher& hf,
                    const allocator_type& a); // (18) C++26

## 概要

`unordered_map` オブジェクトを構築する

## 要件

- ハッシュ関数オブジェクト `hasher` が引数として与えられなかった場合、`hasher` は DefaultConstructible であること。

- キー比較用関数オブジェクト `key_equal` が引数として与えられなかった場合、`key_equal` は DefaultConstructible であること。

- アロケータオブジェクト `allocator_type` が引数として与えられなかった場合、`allocator_type` は DefaultConstructible であること。

- (3) の形式の場合、`value_type` は `*first` からこの `unordered_map` に EmplaceConstructible であること。

- (4), (7)、および (9) の形式の場合、`value_type` はこの `unordered_map` に CopyInsertable であること。

- (5) の形式の場合、`allocator_type` のムーブ構築は例外終了しないこと。

- (8) の形式の場合、`value_type` はこの `unordered_map` に MoveInsertable であること。（但し、備考参照）

## 効果

- (1) : バケット数の最低が実装依存の、要素を持たない空の `unordered_map` を構築する。
- (2) : バケット数最低 `n`、ハッシュ関数オブジェクト `hf`、キー比較用関数オブジェクト `eql`、アロケータオブジェクト `a` で、要素を持たない空の `unordered_map` を構築する。

- (1) + (2) バケット数最低 `n`、ハッシュ関数オブジェクト `hf`、キー比較用関数オブジェクト `eql`、アロケータオブジェクト `a` で、要素を持たない空の `unordered_map` を構築する。 引数 `n` のデフォルト値は実装依存である。

- (3) : バケット数最低 `n`、ハッシュ関数オブジェクト `hf`、キー比較用関数オブジェクト `eql`、アロケータオブジェクト `a` で `unordered_map` が構築された後、イテレータ範囲`[first, last)` の要素が挿入される。

- (4) : コピーコンストラクタ。`v` の全ての要素をコピーした、`unordered_map` を構築する。 ハッシュ関数オブジェクトとキー比較関数オブジェクト、および、`max_load_factor()` の値も `v` からコピーされる。 アロケータオブジェクトは、`std::allocator_traits<allocator_type>::select_on_container_copy_construction(get_allocator())` の戻り値が使用される。

- (5) : ムーブコンストラクタ。`rv` の全ての要素をムーブした、`unordered_map` を構築する。 ハッシュ関数オブジェクトとキー比較関数オブジェクト、および、アロケータオブジェクトも `v` からムーブされる。 `max_load_factor()` の値は `rv` からコピーされる。 なお、要素のムーブは個々に行われるのではなく、`unordered_map` 内部の構造ごと一括でムーブされる。

- (6) : ハッシュ関数オブジェクト `hasher()`、キー比較用関数オブジェクト `key_equal()`、アロケータオブジェクト `a` で、要素を持たない空の `unordered_map` を構築する。 構築された `unordered_map` のバケット数、および、`max_load_factor()` は実装依存である。

- (7) : `v` の全ての要素をコピーした、`unordered_map` を構築する。 ハッシュ関数オブジェクトとキー比較関数オブジェクト、および、`max_load_factor()` の値も `v` からコピーされるが、アロケータオブジェクトは引数 `a` が使用される。

- (8) : `rv` のすべての要素をムーブした、`unordered_map` を構築する。 ハッシュ関数オブジェクトとキー比較関数オブジェクトの値も `rv` からムーブされるが、アロケータオブジェクトは引数 `a` が使用される。 `max_load_factor()` の値は `rv` からコピーされる。 なお、`a == rv.get_allocator()` の場合、要素のムーブは個々に行われるのではなく、`unordered_map` 内部の構造ごと一括でムーブされるが、そうでない場合は要素ごとにムーブされる。

- (9) : (3) の形式を `unordered_map(il.begin(), il.end(), n, hf, eql, a)` として呼び出した場合と等価である。

- (10) : (2) の形式を `unordered_map(n, hasher(), key_equal(), a)` として呼び出した場合と等価である。

- (11) : (2) の形式を `unordered_map(n, hf, key_equal(), a)` として呼び出した場合と等価である。

- (12) : (3) の形式を `unordered_map(f, l, n, hasher(), key_equal(), a)` として呼び出した場合と等価である。

- (13) : (3) の形式を `unordered_map(f, l, n, hf, key_equal(), a)` として呼び出した場合と等価である。

- (14) : (5) の形式を `unordered_map(il, n, hasher(), key_equal(), a)` として呼び出した場合と等価である。

- (15) : (5) の形式を `unordered_map(il, n, hf, key_equal(), a)` として呼び出した場合と等価である。

- (16) : バケット数最低 `n`、ハッシュ関数オブジェクト `hf`、キー比較用関数オブジェクト `eql`、アロケータオブジェクト `a` で `unordered_map` が構築された後、Range `rg` の要素が挿入される。

- (17) : (16) の形式を `unordered_map(from_range, std::forward<R>(rg), n, hasher(), key_equal(), a)` として呼び出した場合と等価である。

- (18) : (16) の形式を `unordered_map(from_range, std::forward<R>(rg), n, hf, key_equal(), a)` として呼び出した場合と等価である。

## 事後条件

以下では構築されたオブジェクトを `u` とする。

- (1) : `u.empty() == true`。 `u.max_load_factor() == 1.0`。

- (2) : `u.empty() == true`。 `u.get_allocator() == a`。 `u.max_load_factor() == 1.0`。 `u.bucket_count() >= n`。

- (3) : `u.get_allocator() == a`。 `u.max_load_factor() == 1.0`。 `u.bucket_count() >= n`。

- (4) : `u.max_load_factor() == v.max_load_factor()`。 `u == v`。

- (5) : `u.get_allocator() ==`構築前の `rv.get_allocator()`。 `u.max_load_factor() ==`構築前の `rv.max_load_factor()`。 `u ==`構築前の `rv`。

- (6) : `u.empty() == true`。 `u.get_allocator() == a`。

- (7) : `u.max_load_factor() == v.max_load_factor()`。 `u == v`。 `u.get_allocator() == a`。

- (8) : `u.max_load_factor() ==`構築前の `rv.max_load_factor()`。 `u ==`構築前の `rv`。 `u.get_allocator() == a`。

- (9) : `u.get_allocator() == a`。 `u.max_load_factor() == 1.0`。 `u.bucket_count() >= n`。

## 計算量

- (1) : 定数
- (2) : 定数
- (3) : 平均的には O(n)、ここで、n は `std::distance(first, last)`。 最悪のケースでは O(n2)
- (4) : 平均的には O(n)、ここで、n は `v.size()`。 最悪のケースでは O(n2)
- (5) : 定数
- (6) : 定数
- (7) : O(`v.size()`)
- (8) : `a == rv.get_allocator()` の場合、定数。 そうでない場合、O(`rv.size()`)。
- (9) : (3)の形式を `unordered_map(il.begin(), il.end(), n, hf, eql, a)` として呼び出した場合と等価。
- (10) : (2)の形式を `unordered_map(n, hasher(), key_equal(), a)` として呼び出した場合と等価。
- (11) : (2) の形式を `unordered_map(n, hf, key_equal(), a)` として呼び出した場合と等価。
- (12) : (3) の形式を `unordered_map(f, l, n, hasher(), key_equal(), a)` として呼び出した場合と等価。
- (13) : (3) の形式を `unordered_map(f, l, n, hf, key_equal(), a)` として呼び出した場合と等価。
- (14) : (5) の形式を `unordered_map(il, n, hasher(), key_equal(), a)` として呼び出した場合と等価。
- (15) : (5) の形式を `unordered_map(il, n, hf, key_equal(), a)` として呼び出した場合と等価。
- (16), (17), (18) : 平均的には O(n)、ここで、n は `ranges::distance(rg)`。最悪のケースでは O(n2)

## 備考

- (8) の形式の場合、MoveInsertable が要件となっているが、`rv.get_allocator() == a` の場合にはムーブコンストラクタと同様の挙動となるため、MoveInsertable ではなくても良いと思われる。

- C++14 では、デフォルトコンストラクタを (1) + (2) の形式から (1) の形式に分離して残りを (2) の形式（`n` のデフォルト引数を削除）にした。 これは、デフォルトコンストラクタに `explicit` が付いていると、

      std::unordered_map<int, char> m = {};

  のようなコード（C++11 から導入された、コピーリスト初期化によるデフォルトコンストラクタ呼び出し）がエラーになってしまうためである。

- C++23 では、(7) と (8) のアロケータパラメータの型が `const allocator_type&` から `const type_identity_t<allocator_type>&` に変更された。 これは、クラステンプレートのテンプレート引数推論 (CTAD) の際に、コピー/ムーブ元の `unordered_map` から推論される `Allocator` と、アロケータ引数から推論される型が異なる場合に推論が失敗する問題を修正するためである。`type_identity_t` で包むことで、アロケータ引数が非推論コンテキストとなり、アロケータの型はコピー/ムーブ元のみから推論されるようになる。

## バージョン

### 言語

- C++11

### 処理系

- Clang: 3.0 ✅, 3.1 ✅
- GCC: 4.4.7 ✅, 4.5.3 ✅, 4.6.3 ✅, 4.7.0 ✅
- ICC: ?
- Visual C++: ?

#### 備考

libstdc++ には 4.8.2 現在、(6), (7), (8)の形式はない。

## 関連項目

名前 | 説明
--- | ---
`(destructor)` | デストラクタ
`operator=` | 代入演算子

## 参照

- N2679 Initializer Lists for Standard Containers(Revision 1)
  - (9)の経緯となる提案文書
- LWG 2193. Default constructors for standard library containers are explicit
  (1) + (2) を 2 つのオーバーロードに分割するきっかけとなったレポート
- LWG 2210. Missing allocator-extended constructor for allocator-aware containers
  (10), (11), (12), (13), (14), (15) を追加するきっかけとなったレポート
  なお、Discussion の例はアロケータの型が誤っているので注意
- P1518R2 Stop Overconstraining Allocators in Container Deduction Guides
  - C++23でのアロケータ引数を`type_identity_t`で包む変更
- P3372R3 constexpr containers and adaptors