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

履歴 編集

class template
<flat_set>

# std::flat_multiset(C++23)

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

## 概要

`std::flat_multiset`は、重複する要素を許可する連想コンテナの一種であり、要素自身がキーとなる、集合を表すクラスである。

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

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

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

また、このクラスは分類としては`std::queue`や`std::stack`と同様のコンテナアダプタに分類され、キーの配列をラップして扱う実装となっている。

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

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

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

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

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

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

- `KeyContainer`に指定するコンテナ型は、
  - シーケンスコンテナの要件を満たし、
  - ランダムアクセスイテレータをもつこと

## 適格要件

- `Key`が`KeyContainer::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

## メンバ型

名前 | 説明 | 対応バージョン
--- | --- | ---
`key_type` | キーの型。テンプレートパラメータ `Key` | C++23
`value_type` | 要素の型。テンプレートパラメータ `Key` | C++23
`key_compare` | キーの大小関係を判定する二項述語の型。テンプレートパラメータ `Compare` | C++23
`value_compare` | 要素の大小関係を判定する二項述語の型。テンプレートパラメータ `Compare` | C++23
`reference` | 要素への参照型。`value_type&` | C++23
`const_reference` | 要素への`const`参照型。`const value_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
`container_type` | キーを格納するコンテナ型 `KeyContainer` | C++23

## 非メンバ関数

### 要素削除

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

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

### 比較演算子

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

### 入れ替え

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

## 推論補助

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

## その他

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

## 例

### 基本的な使い方

    #include <flat_set>
    #include <iostream>
    #include <string>

    int main()
    {
      // stringをキーとして扱う連想配列
      std::flat_multiset<std::string> fs = {"Carol", "Alice", "Bob", "Carol"};

      // 検索 : キーを指定し、イテレータを得る
      auto it = fs.find("Alice");
      std::cout << *it << std::endl
                << std::endl;

      // 全体を出力する
      for (const auto& str : fs) {
        std::cout << str << std::endl;
      }
    }

#### 出力

    Alice

    Alice
    Bob
    Carol
    Carol

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

    #include <deque>
    #include <flat_set>
    #include <iostream>

    int main()
    {
      std::deque<int> keys = {1, 4, 2, 8, 5, 7};

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

      // 全体を出力する
      for (int i : fs) {
        std::cout << i << " ";
      }
      std::cout << std::endl;
    }

#### 出力

    8 7 5 4 2 1

## バージョン

### 言語

- C++23

### 処理系

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

## 参照

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