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::queueやstd::skackと同様のコンテナアダプタに分類され、キーの配列と値の配列の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と同じ型であること

メンバ関数

構築・破棄

イテレータ

領域

コンテナの変更

要素アクセス

オブザーバー

メンバ型

非メンバ関数

要素削除

非メンバ（Hidden friends）関数

比較演算子

入れ替え

推論補助

その他

例

基本的な使い方

#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の仕様