- flat_set[meta header]
- std[meta namespace]
- class template[meta id-type]
- cpp23[meta cpp]
namespace std {
template <class Key,
class Compare = less<Key>,
class KeyContainer = vector<Key>>
class flat_multiset;
}
- less[link ../functional/less.md]
- vector[link /reference/vector/vector.md]
std::flat_multisetは、重複する要素を許可する連想コンテナの一種であり、要素自身がキーとなる、集合を表すクラスである。
std::flat_multisetは、ノードベースで実装されるstd::multiset、ハッシュテーブルで実装されるstd::unordered_multisetとは異なり、ソート済み配列と二分探索の組み合わせで実装される。これはほかの実装と比較して、メモリ使用量と列挙速度において優位であり、一方で挿入速度と検索速度はほかの実装に劣る。
また、このクラスは分類としてはstd::queueやstd::skackと同様のコンテナアダプタに分類され、キーの配列をラップして扱う実装となっている。
このコンテナクラスは、ランダムアクセスイテレータをサポートする。
このクラスは要件として、コンテナクラスと、逆順コンテナクラスであることは満たすが、連想コンテナの要件としては以下を満たさない：
- node handleに関する要件
- イテレータ無効化に関する要件
- 単一要素の挿入と削除に線形時間かかる (挿入位置のイテレータを指定したとしても)
また、このコンテナはメモリアロケータを指定できない設計にもなっている。
KeyContainerに指定するコンテナ型は、
- シーケンスコンテナの要件を満たし、
- ランダムアクセスイテレータをもつこと
KeyがKeyContainer::value_typeと同じ型であること
| 名前 |
説明 |
対応バージョン |
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 |
| 名前 |
説明 |
対応バージョン |
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 |
| 名前 |
説明 |
対応バージョン |
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 |
#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;
}
}
- fs.find[link flat_multiset/find.md]
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;
}
- std::greater[link ../functional/greater.md]
