std::flat_set(C++23)

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

概要

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

std::flat_setは、ノードベースで実装されるstd::set、ハッシュテーブルで実装されるstd::unordered_setとは異なり、ソート済み配列と二分探索の組み合わせで実装される。これはほかの実装と比較して、メモリ使用量と列挙速度において優位であり、一方で挿入速度と検索速度はほかの実装に劣る。

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

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

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

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

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

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

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

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

適格要件

• KeyがKeyContainer::value_typeと同じ型であること

メンバ関数

構築・破棄

イテレータ

領域

コンテナの変更

要素アクセス

オブザーバー

メンバ型

非メンバ関数

要素削除

非メンバ（Hidden friends）関数

比較演算子

入れ替え

推論補助

その他

例

基本的な使い方

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

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

  // 検索 : キーを指定し、イテレータを得る
  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

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

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

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

  // intをキーとして扱う連想配列
  // キーの順序はgreater、キーのコンテナはdequeで保持
  std::flat_set<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の仕様