最終更新日時(UTC): 2026年03月13日 02時25分45秒
Akira Takahashi が更新

履歴 編集

class template
<flat_map>

# std::flat_multimap(C++23)

    namespace std {
      template <class Key,
                class T,
                class Compare = less<Key>,
                class KeyContainer = vector<Key>,
                class MappedContainer = vector<T>>
      class flat_multimap;
    }

## 概要

`flat_multimap` は同一キーの要素を複数格納できる連想コンテナの一種であり、キーとそれに対応する値を格納する。

`std::flat_multimap`は、ノードベースで実装される`std::multimap`、ハッシュテーブルで実装される`std::unordered_multimap`とは異なり、ソート済み配列と二分探索の組み合わせで実装される。

ほかの連想コンテナとの比較としては、

- メモリ使用量と列挙速度において優位
- 挿入速度と削除速度はほかの実装に劣る
- 検索速度は、`std::multimap`より高速であることが期待できるが (計算量としては同じ対数時間だが、メモリアクセスが高速)、サイズが大きいときは`std::unordered_multimap`に劣る

また、このクラスは分類としては`std::queue`や`std::stack`と同様のコンテナアダプタに分類され、キーの配列と値の配列の2つを内部で持ち、それを`std::ranges::zip_view`で綴じあわせて扱う実装となっている。

このコンテナクラスは、ランダムアクセスイテレータをサポートする。

### ほかの連想コンテナとの要件の違い

このクラスは要件として、コンテナクラスと、逆順コンテナクラスであることは満たすが、連想コンテナの要件としては以下を満たさない：

- node handleに関する要件
- イテレータ無効化に関する要件
- 単一要素の挿入と削除に線形時間かかる (挿入位置のイテレータを指定したとしても)

また、このコンテナはメモリアロケータを指定できない設計にもなっている。

`value_type`は、`std::multimap`では`std::pair<const Key, T>`だが、このクラスは`std::pair<Key, T>`である (`const`がつかない)。

以下の不変条件をもち、メンバ関数のいずれかが例外によって終了した場合には不変条件の状態に復元される (ただし、その復元操作によってコンテナが空になる可能性がある)。ムーブコンストラクタとムーブ代入演算子の場合、両方の引数の不変条件が復元される：

- キーの配列と値の配列が、同じ要素数をもつ
- キーの配列が、指定された比較関数オブジェクトを尊重してソートを行う
- 値の配列内のオフセット`off`の値は、キー配列内のオフセット`off`のキーに関連付けられた値である

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

- `KeyContainer`と`MappedContainer`に指定するコンテナ型は、
  - シーケンスコンテナの要件を満たし、
  - ランダムアクセスイテレータをもち、
  - 例外を送出しないメンバ関数`size()`と`max_size()`をもつこと

## 適格要件

- `Key`が`KeyContainer::value_type`と同じ型であること
- `T`が`MappedContainer::value_type`と同じ型であること

## メンバ関数

### 構築・破棄

名前 | 説明 | 対応バージョン
--- | --- | ---
`(constructor)` | コンストラクタ | C++23
`(destructor)` | デストラクタ | C++23
`operator=` | 代入演算子 | C++23

### イテレータ

名前 | 説明 | 対応バージョン
--- | --- | ---
`begin` | 先頭を指すイテレータを取得する | C++23
`cbegin` | 先頭を指す読み取り専用イテレータを取得する | C++23
`end` | 末尾の次を指すイテレータを取得する | C++23
`cend` | 末尾の次を指す読み取り専用イテレータを取得する | C++23
`rbegin` | 末尾を指す逆イテレータを取得する | C++23
`crbegin` | 末尾を指す読み取り専用逆イテレータを取得する | C++23
`rend` | 先頭の前を指す逆イテレータを取得する | C++23
`crend` | 先頭の前を指す読み取り専用逆イテレータを取得する | C++23

### 領域

名前 | 説明 | 対応バージョン
--- | --- | ---
`empty` | コンテナが空であるかどうかを調べる | C++23
`size` | 要素数を取得する | C++23
`max_size` | 格納可能な最大の要素数を取得する | C++23

### コンテナの変更

名前 | 説明 | 対応バージョン
--- | --- | ---
`clear` | 全ての要素を削除する | C++23
`insert` | 要素を挿入する | C++23
`insert_range` | Rangeを挿入する | C++23
`emplace` | 要素を直接構築する | C++23
`emplace_hint` | ヒントを使って要素を直接構築する | C++23
`erase` | 要素を削除する | C++23
`swap` | コンテンツを交換する | C++23
`extract` | キーのコンテナ、値のコンテナを取得する | C++23
`replace` | キーのコンテナ、値のコンテナを置き換える | C++23

### 要素アクセス

名前 | 説明 | 対応バージョン
--- | --- | ---
`count` | 指定したキーにマッチする要素の数を取得する | C++23
`find` | 指定したキーで要素を探す | C++23
`contains` | 指定したキーの要素が含まれているかを判定する | C++23
`equal_range` | 指定したキーにマッチする要素範囲を取得する | C++23
`lower_bound` | 与えられた値より小さくない最初の要素へのイテレータを取得する | C++23
`upper_bound` | 特定の値よりも大きい最初の要素へのイテレータを取得する | C++23

### オブザーバー

名前 | 説明 | 対応バージョン
--- | --- | ---
`key_comp` | キー比較用の関数オブジェクトを取得する | C++23
`value_comp` | 要素比較用の関数オブジェクトを取得する | C++23
`keys` | キーのコンテナを取得する | C++23
`values` | 値のコンテナを取得する | C++23

## メンバ型

名前 | 説明 | 対応バージョン
--- | --- | ---
`key_type` | キーの型。テンプレートパラメータ `Key` | C++23
`mapped_type` | 値の型。テンプレートパラメータ `T` | C++23
`value_type` | 要素の型。`std::pair<key_type, mapped_type>` | C++23
`key_compare` | キー値の大小関係を判定する二項述語の型。テンプレートパラメータ `Compare` | C++23
`value_compare` | 要素値のキー部分で大小関係を判定する二項述語の型。入れ子クラス | C++23
`reference` | 要素への参照型。`std::pair<const key_type&, mapped_type&>` | C++23
`const_reference` | 要素への`const`参照型。`std::pair<const key_type&, const mapped_type&>` | C++23
`size_type` | 要素数を表す符号なし整数型 `size_t` | C++23
`difference_type` | 同一のコンテナを指す `iterator` の差を表す符号付き整数型 `ptrdiff_t` | C++23
`iterator` | ランダムアクセスイテレータ | C++23
`const_iterator` | 読み取り専用ランダムアクセスイテレータ | C++23
`reverse_iterator` | 逆順ランダムアクセスイテレータ。`std::reverse_iterator<iterator>` | C++23
`const_reverse_iterator` | 読み取り専用逆順ランダムアクセスイテレータ。`std::reverse_iterator<const_iterator>` | C++23
`key_container_type` | キーを格納するコンテナ型 `KeyContainer` | C++23
`mapped_container_type` | 値を格納するコンテナ型 `MappedContainer` | C++23
`containers` | キーのコンテナと値のコンテナを保持する型 | C++23
`key_equiv` | 要素をとってキーの等価比較を行う説明専用の関数オブジェクト | C++23

## 非メンバ関数

### 要素削除

名前 | 説明 | 対応バージョン
--- | --- | ---
`erase_if` | 指定した条件に合致する要素とその分の領域を、コンテナから削除する | C++23

## 非メンバ（Hidden friends）関数

### 比較演算子

名前 | 説明 | 対応バージョン
--- | --- | ---
`operator==` | 左辺と右辺が等しいかの判定を行う | C++23
`bool operator!=(const flat_multimap& x, const flat_multimap& y);` | 左辺と右辺が等しくないかの判定を行う (`==`により使用可能) | C++23
`operator<=>` | 三方比較を行う | C++23
`bool operator<(const flat_multimap& x, const flat_multimap& y);` | 左辺が右辺より小さいかの判定を行う (`<=>`により使用可能) | C++23
`bool operator<=(const flat_multimap& x, const flat_multimap& y);` | 左辺が右辺より小さいか等しいかの判定を行う (`<=>`により使用可能) | C++23
`bool operator>(const flat_multimap& x, const flat_multimap& y);` | 左辺が右辺より大きいかの判定を行う (`<=>`により使用可能) | C++23
`bool operator>=(const flat_multimap& x, const flat_multimap& y);` | 左辺が右辺より大きいか等しいかの判定を行う (`<=>`により使用可能) | C++23

### 入れ替え

名前 | 説明 | 対応バージョン
--- | --- | ---
`swap` | 2つの`flat_multimap`オブジェクトを入れ替える | C++23

## 推論補助

名前 | 説明 | 対応バージョン
--- | --- | ---
`(deduction_guide)` | クラステンプレートの推論補助 | C++23

## その他

名前 | 説明 | 対応バージョン
--- | --- | ---
`uses_allocator` | `flat_multimap`による特殊化 | C++23

## 例

### 基本的な使い方

    #include <flat_map>
    #include <iostream>

    int main()
    {
      // intをキー、charを値、として扱う連想配列
      // flat_mapとは異なり、キーが重複してもよい
      std::flat_multimap<int, char> fm = {
        {10, 'A'}, {11, 'B'}, {12, 'C'},
        {10, 'a'}, {11, 'b'}, {12, 'c'},
      };

      // 全体を出力する
      for (const auto& [key, value] : fm) {
        std::cout << key << " : " << value << std::endl;
      }
    }

#### 出力

    10 : A
    10 : a
    11 : B
    11 : b
    12 : C
    12 : c

### キーと要素以外のテンプレートを指定

    #include <deque>
    #include <flat_map>
    #include <iostream>

    int main()
    {
      std::deque<int> keys = {10, 10, 11, 11, 12, 12};
      std::deque<char> values = {'A', 'a', 'B', 'b', 'C', 'c'};

      // intをキー、charを値として扱う連想配列
      // キーの順序はgreater、キーと値のコンテナはdequeで保持
      std::flat_multimap<int,
                         char,
                         std::greater<int>,
                         std::deque<int>,
                         std::deque<char>> fm(keys, values);

      // 全体を出力する
      for (const auto& [key, value] : fm) {
        std::cout << key << " : " << value << std::endl;
      }
    }

#### 出力

    12 : C
    12 : c
    11 : B
    11 : b
    10 : A
    10 : a

## バージョン

### 言語

- C++23

### 処理系

- Clang: ??
- GCC: ??
- Visual C++: ??

## 参照

- P0429R3 A Standard `flat_map`
  - C++23で`flat_map`が導入された経緯・動機・設計について記載されている
- P0429R9 A Standard `flat_map`
  - C++23で導入された`flat_map`の仕様
- P3567R2 flat_meow Fixes
  - C++26で`swap`の条件付き`noexcept`、`insert_range`のソート済みオーバーロード追加などの修正が行われた