C++ 名前付き要件: AssociativeContainer

 

C++

コンパイラサポート

フリースタンディングとホスト

言語

標準ライブラリ

標準ライブラリヘッダー

名前付き要件

機能テストマクロ (C++20)

言語サポートライブラリ

コンセプトライブラリ (C++20)

診断ライブラリ

メモリ管理ライブラリ

メタプログラミングライブラリ (C++11)

汎用ユーティリティライブラリ

コンテナライブラリ

イテレータライブラリ

Rangesライブラリ (C++20)

アルゴリズムライブラリ

文字列ライブラリ

テキスト処理ライブラリ

数値ライブラリ

日付と時刻ライブラリ

入出力ライブラリ

ファイルシステムライブラリ (C++17)

並行サポートライブラリ (C++11)

実行制御ライブラリ (C++26)

Technical specifications (技術仕様)

シンボルインデックス

外部ライブラリ

 

C++ 名前付き要件

基本 DefaultConstructible MoveConstructible (C++11) CopyConstructible CopyAssignable MoveAssignable (C++11) Destructible 型のプロパティ ScalarType PODType TriviallyCopyable (C++11) TrivialType (C++11) StandardLayoutType (C++11)   ImplicitLifetimeType ライブラリワイド BooleanTestable EqualityComparable LessThanComparable Swappable ValueSwappable (C++11) NullablePointer (C++11) Hash (C++11) アロケータ FunctionObject Callable Predicate BinaryPredicate Compare

コンテナ コンテナ ReversibleContainer AllocatorAwareContainer SequenceContainer ContiguousContainer (C++17) AssociativeContainer UnorderedAssociativeContainer (C++11)   コンテナ要素 DefaultInsertable (C++11) CopyInsertable (C++11) MoveInsertable (C++11) EmplaceConstructible (C++11) Erasable (C++11) イテレータ LegacyIterator LegacyInputIterator LegacyOutputIterator LegacyForwardIterator LegacyBidirectionalIterator LegacyRandomAccessIterator LegacyContiguousIterator (C++17) ConstexprIterator (C++20) ストリームI/O FormattedInputFunction UnformattedInputFunction FormattedOutputFunction UnformattedOutputFunction フォーマッタ BasicFormatter (C++20) フォーマッタ (C++20)

乱数 SeedSequence (C++11) RandomNumberEngine (C++11) RandomNumberDistribution (C++11) UniformRandomBitGenerator (C++11) RandomNumberEngineAdaptor (C++11) 並行性 BasicLockable (C++11) Lockable (C++11) TimedLockable (C++11) SharedLockable (C++14) SharedTimedLockable (C++14) Mutex (C++11) TimedMutex (C++11) SharedMutex (C++17) SharedTimedMutex (C++14) Ranges RangeAdaptorObject (C++20) RangeAdaptorClosureObject (C++20) 多次元ビュー LayoutMapping (C++23) LayoutMappingPolicy (C++23) AccessorPolicy (C++23) その他 CharTraits RegexTraits (C++11)   BitmaskType LiteralType (C++11) NumericType UnaryTypeTrait (C++11) BinaryTypeTrait (C++11) TransformationTrait (C++11) Clock (C++11) TrivialClock (C++11)

 

AssociativeContainer とは、キーに基づいてオブジェクトの高速な検索を提供する、順序付けられた Container です。

連想コンテナが 一意のキー をサポートするのは、各キーに対して最大1つの要素しか含めない場合です。それ以外の場合は、同値キー をサポートします。

要件

凡例
X	連想コンテナクラス
T	X の要素型
A	X のアロケータ型: 存在する場合は X::allocator_type、それ以外の場合は std::allocator<X::value_type>
a	X の値
a2	X と互換性のある ノードハンドル を持つ Y 型の値
b	X または const X の値
u	宣言される変数の名前
a_uniq	X が一意キーをサポートする場合の X の値
a_eq	X が同値キーをサポートする場合の X の値
a_tran	X::key_compare::is_transparent が存在する場合の X または const X の値
i, j	X::value_type に暗黙的に変換可能な LegacyInputIterator
[i, j)	有効な範囲
rg (C++23から)	container-compatible-range<value_type> をモデル化する R 型の値
p	a への有効な定数イテレータ
q	a への有効な逆参照可能な定数イテレータ
r	a への有効な逆参照可能なイテレータ
q1, q2	a 内の有効な定数イテレータの範囲
il	X::value_type の std::initializer_list のオブジェクト
t	X::value_type の値
k	X::key_type の値
c	X::key_compare または const X::key_compare の値
kl	a が c(x, kl) に関して分割されており、x は e のキー値であり、e は a 内にあるような値
ku	a が !c(ku, x) に関して分割されており、x は e のキー値であり、e は a 内にあるような値
ke	a が c(x, ke) と !c(ke, x) に関して分割されており、c(x, ke) が !c(ke, x) を含意し、x は e のキー値であり、e は a 内にあるような値
kx (C++23から)	以下を満たす値: a は c(x, kx) と !c(kx, x) に関して分割されており、c(x, kx) が !c(kx, x) を含意し、x は e のキー値であり、e は a 内にある。 kx は X::iterator または X::const_iterator のどちらにも変換できない。
m	A に変換可能な型のアロケータ
nh	X::node_type の非 const 右辺値

型 X は、以下の場合に AssociativeContainer を満たします。

• 型 X は Container(C++11まで)AllocatorAwareContainer(C++11以降) を満たす。
• Key と、Key の要素上に strict weak ordering を誘導する順序関係 Compare をパラメータとする。
  • さらに、std::map および std::multimap は、Key に任意の マッピング型 T を関連付けます。
  • Compare のオブジェクトは、型 X のコンテナの 比較オブジェクト と呼ばれます。
• すべての連想コンテナについて、以下の式は有効であり、指定された効果を持つ必要があります。

型

名前	型	要件
key_type	Key
mapped_type	T (std::map および std::multimap のみ)
value_type	Key (std::set および std::multiset のみ) std::pair<const Key, T> (std::map および std::multimap のみ)	X から Erasable
key_compare	Compare	CopyConstructible
value_compare	key_compare と同じ (std::set および std::multiset の場合) ペアの順序関係で、第一成分（すなわち Key）によって誘導されるもの (std::map および std::multimap の場合)	BinaryPredicate
node_type	node-handle クラステンプレート の特殊化。その公開されているネストされた型が、X の対応する型と同じ型である。

メンバ関数と演算子

Expression	結果	事前条件	効果	戻り値	計算量
X(c)			空のコンテナを構築します。c のコピーを比較オブジェクトとして使用します。		Constant
X u = X(); X u;		key_compare は DefaultConstructible 要件を満たす。	空のコンテナを構築します。Compare() を比較オブジェクトとして使用します。		Constant
X(i, j, c)		value_type は、*i から X へ EmplaceConstructible である。	空のコンテナを構築し、範囲 [i, j) の要素を挿入します。c を比較オブジェクトとして使用します。		一般的に N·log(N)、ここで N は std::distance(i, j) の値。範囲 [i, j) が value_comp() に関してソートされている場合は線形。
X(i, j)		key_compare は DefaultConstructible 要件を満たす。value_type は、*i から X へ EmplaceConstructible である。	空のコンテナを構築し、範囲 [i, j) の要素を挿入します。Compare() を比較オブジェクトとして使用します。
X(from_range, rg, c) (C++23から)		value_type は、*ranges::begin(rg) から X へ EmplaceConstructible である。	空のコンテナを構築し、rg の各要素を挿入します。c を比較オブジェクトとして使用します。		一般的に N·log(N)、ここで N は ranges::distance(rg) の値。範囲 rg が value_comp() に関してソートされている場合は線形。
X(from_range, rg) (C++23から)		key_compare は DefaultConstructible 要件を満たす。value_type は、*ranges::begin(rg) から X へ EmplaceConstructible である。	空のコンテナを構築し、rg の各要素を挿入します。Compare() を比較オブジェクトとして使用します。
X(il, c)			X(il.begin(), il.end(), c)
X(il)			X(il.begin(), il.end())
a = il	X&	value_type は X へ CopyInsertable であり、CopyAssignable である。	範囲 [il.begin(), il.end()) を a に代入します。a の既存のすべての要素は、代入されるか破棄されます。		一般的に N·log(N)、ここで N は il.size() + a.size() の値。範囲 [il.begin(), il.end()) が value_comp() に関してソートされている場合は線形。
b.key_comp()	X::key_compare			b が構築された比較オブジェクト	Constant
b.value_comp()	X::value_compare			比較オブジェクトから構築された value_compare のオブジェクト	Constant
a_uniq.emplace(args)	std::pair<   iterator,   bool>	value_type は、args から X へ EmplaceConstructible である。	value_type オブジェクト t を、std::forward<Args>(args)... で構築して挿入します。ただし、コンテナ内に t のキーと同値のキーを持つ要素が存在しない場合に限ります。	返されるペアの bool 成分は、挿入が行われた場合に true となり、ペアのイテレータ成分は t のキーと同値のキーを持つ要素を指します。	対数時間
a_eq.emplace(args)	iterator	value_type は、args から X へ EmplaceConstructible である。	value_type オブジェクト t を、std::forward<Args>(args)... で構築して挿入します。a_eq 内に t と同値の要素を持つ範囲が存在する場合、t はその範囲の末尾に挿入されます。	新しく挿入された要素を指すイテレータ	対数時間
a.emplace_hint(p, args)	iterator		以下と等価です。 a.emplace(std::forward<Args>(args)...) と同様ですが、要素は p の直前の位置にできるだけ近い位置に挿入されます。	新しく挿入された要素と同値のキーを持つ要素を指すイテレータ	一般的に対数時間ですが、要素が p の直前に挿入される場合は償却定数時間。
a_uniq.insert(t)	std::pair<   iterator,   bool>	t が非 const 右辺値の場合、value_type は X へ MoveInsertable であり、それ以外の場合、value_type は X へ CopyInsertable です。	t と同値のキーを持つ要素がコンテナ内に存在しない場合に限り、t を挿入します。	返されるペアの bool 成分は、挿入が行われた場合に true となり、iterator 成分は t のキーと同値のキーを持つ要素を指します。	対数時間
a_eq.insert(t)	iterator	t が非 const 右辺値の場合、value_type は X へ MoveInsertable であり、それ以外の場合、value_type は X へ CopyInsertable です。	t を挿入し、新しく挿入された要素を指すイテレータを返します。a_eq 内に t と同値の要素を持つ範囲が存在する場合、t はその範囲の末尾に挿入されます。		対数時間
a.insert(p, t)	iterator	t が非 const 右辺値の場合、value_type は X へ MoveInsertable であり、それ以外の場合、value_type は X へ CopyInsertable です。	一意キーを持つコンテナでは、t のキーと同値のキーを持つ要素が存在しない場合に限り t を挿入します。同値キーを持つコンテナでは常に t を挿入します。t は p の直前の位置にできるだけ近い位置に挿入されます。	t のキーと同値のキーを持つ要素を指すイテレータ	一般的に対数時間ですが、t が p の直前に挿入される場合は償却定数時間。
a.insert(i, j)	void	value_type は、*i から X へ EmplaceConstructible である。i も j も a へのイテレータではない。	範囲 [i, j) の各要素を、一意キーを持つコンテナではその要素のキーと同値のキーを持つ要素が存在しない場合に限り、同値キーを持つコンテナでは常に挿入します。		N·log(a.size() + N)、ここで N は std::distance(i, j) の値。
a.insert_range(rg) (C++23から)	void	value_type は、*ranges::begin(rg) から X へ EmplaceConstructible である。rg と a は重複しない。	rg の各要素を、一意キーを持つコンテナではその要素のキーと同値のキーを持つ要素が存在しない場合に限り、同値キーを持つコンテナでは常に挿入します。		N·log(a.size() + N)、ここで N は ranges::distance(rg) の値。
a.insert(il)			a.insert(il.begin(), il.end())
a_uniq.insert(nh)	insert_return_type	nh が空であるか、または a_uniq.get_allocator() == nh.get_allocator() が true である。	nh が空の場合、効果はありません。それ以外の場合、nh が所有する要素を、コンテナ内に nh.key() と同値のキーを持つ要素が存在しない場合に限り挿入します。	nh が空の場合、inserted は false、position は end()、node は空です。それ以外の場合、挿入が行われた場合は inserted は true、position は挿入された要素を指し、node は空です。挿入が失敗した場合は、inserted は false、node は nh の以前の値となり、position は nh.key() と同値のキーを持つ要素を指します。	対数時間
a_eq.insert(nh)	iterator	nh が空であるか、または a_eq.get_allocator() == nh.get_allocator() が true である。	nh が空の場合、効果はなく a_eq.end() を返します。それ以外の場合、nh が所有する要素を挿入し、新しく挿入された要素を指すイテレータを返します。a_eq 内に nh.key() と同値のキーを持つ要素の範囲が存在する場合、要素はその範囲の末尾に挿入されます。保証: nh は空になります。		対数時間
a.insert(p, nh)	iterator	nh が空であるか、または a.get_allocator() == nh.get_allocator() が true である。	nh が空の場合、効果はなく a.end() を返します。それ以外の場合、nh が所有する要素を、一意キーを持つコンテナでは nh.key() と同値のキーを持つ要素が存在しない場合に限り挿入します。同値キーを持つコンテナでは常に nh が所有する要素を挿入します。要素は p の直前の位置にできるだけ近い位置に挿入されます。保証: 挿入が成功した場合 nh は空になります。挿入が失敗した場合 nh は変更されません。	nh.key() と同値のキーを持つ要素を指すイテレータ	一般的に対数時間ですが、要素が p の直前に挿入される場合は償却定数時間。
a.extract(k)	node_type		コンテナ内で k と同値のキーを持つ最初の要素を削除します。	要素を所有する node_type (見つかった場合)、それ以外の場合は空の node_type。	log(a.size())
a_tran.extract(kx) (C++23から)	node_type		コンテナ内で r というキーを持つ最初の要素を削除します。ここで、!c(r, kx) && !c(kx, r) が true となる。	要素を所有する node_type (見つかった場合)、それ以外の場合は空の node_type。	log(a_tran.size())
a.extract(q)	node_type		q が指す要素を削除します。	その要素を所有する node_type。	償却定数時間
a.merge(a2)	void	a.get_allocator() == a2.get_allocator()	a2 内の各要素を抽出し、a の比較オブジェクトを使用して a に挿入しようとします。一意キーを持つコンテナでは、a2 の要素のキーと等しいキーを持つ要素が a に存在する場合、その要素は a2 から抽出されません。保証: 転送された a2 の要素へのポインタおよび参照は、それらを a のメンバとして参照し続けます。転送された要素を参照するイテレータは、それらの要素を参照し続けますが、それらは a2 ではなく a のイテレータとして動作します。例外: 比較オブジェクトが例外をスローしない限り、例外は発生しません。		N·log(a.size() + N)、ここで N は a2.size() の値。
a.erase(k)	size_type		コンテナ内で k と同値のキーを持つすべての要素を削除します。	削除された要素の数	log(a.size()) + a.count(k)
a_tran.erase(kx) (C++23から)	size_type		コンテナ内で r というキーを持つすべての要素を削除します。ここで、!c(r, kx) && !c(kx, r) が true となる。	削除された要素の数	log(a_tran.size()) + a_tran.count(kx)
a.erase(q)	iterator		q が指す要素を削除します。	削除される要素の直前に q が指していた要素の次の要素を指すイテレータ。そのような要素が存在しない場合は、a.end() を返します。	償却定数時間
a.erase(r)	iterator		r が指す要素を削除します。	削除される要素の直前に r が指していた要素の次の要素を指すイテレータ。そのような要素が存在しない場合は、a.end() を返します。	償却定数時間
a.erase(q1, q2)	iterator		範囲内のすべての要素を削除します。 [q1, q2)	要素が削除される前の q2 が指していた要素を指すイテレータ。そのような要素が存在しない場合は、a.end() が返されます。	log(a.size()) + N、ここで N は std::distance(q1, q2) の値。
a.clear()			a.erase(a.begin(), a.end())。保証: a.empty() は true になる。		a.size() に関して線形。
b.find(k)	iterator。b が const の場合は const_iterator。			k と同値のキーを持つ要素を指すイテレータ、またはそのような要素が見つからない場合は b.end()。	対数時間
a_tran.find(ke)	iterator。a_tran が const の場合は const_iterator。			以下を満たすキー r を持つ要素を指すイテレータ: !c(r, ke) && !c(ke, r) が true となる。または、そのような要素が見つからない場合は a_tran.end()。	対数時間
b.count(k)	size_type			k と同値のキーを持つ要素の数。	log(b.size()) + b.count(k)
a_tran.count(ke)	size_type			以下を満たすキー r を持つ要素の数: !c(r, ke) && !c(ke, r)	log(a_tran.size()) + a_tran.count(ke)
b.contains(k)	bool		return b.find(k) != b.end();
a_tran.contains(ke)	bool		return   a_tran.find(ke) !=   a_tran.end();
b.lower_bound(k)	iterator。b が const の場合は const_iterator。			k 以上で最小のキーを持つ要素を指すイテレータ、またはそのような要素が見つからない場合は b.end()。	対数時間
a_tran.lower_bound(kl)	iterator。a_tran が const の場合は const_iterator。			!c(r, kl) を満たす最初のキー r を持つ要素を指すイテレータ、またはそのような要素が見つからない場合は a_tran.end()。	対数時間
b.upper_bound(k)	iterator。b が const の場合は const_iterator。			k より大きいキーを持つ最初の要素を指すイテレータ、またはそのような要素が見つからない場合は b.end()。	対数時間
a_tran.upper_bound(ku)	iterator。a_tran が const の場合は const_iterator。			c(ku, r) を満たす最初のキー r を持つ要素を指すイテレータ、またはそのような要素が見つからない場合は a_tran.end()。	対数時間
b.equal_range(k)	std::pair<   iterator,   iterator>; std::pair<   const_iterator,   const_iterator> for constant b		以下と等価です。 return   std::make_pair(     b.lower_bound(k),     b.upper_bound(k));		対数時間
a_tran.equal_range(ke)	std::pair<   iterator,   iterator>; std::pair<   const_iterator,   const_iterator> for constant a_tran		以下と等価です。 return   std::make_pair(     a_tran.lower_bound(ke),     a_tran.upper_bound(ke));		対数時間

イテレータ

連想コンテナのイテレータは、LegacyBidirectionalIterator の要件を満たします。

value_type と key_type が同じである連想コンテナでは、iterator と const_iterator は両方とも定数イテレータです。iterator と const_iterator が同じ型であるかどうかは未規定です。

連想コンテナのイテレータは、コンテナの構築に使用された比較によって定義される非降順のキーの順序でコンテナを走査します。つまり、以下を与えられた場合:

• a、連想コンテナ。
• i と j、a への逆参照可能なイテレータ。

i から j への距離が正の場合、a.value_comp()(*j, *i) == false。さらに、a が一意キーを持つ連想コンテナの場合、より強い条件 a.value_comp()(*i, *j) != false が成り立ちます。

標準ライブラリ

以下の標準ライブラリコンテナは AssociativeContainer 要件を満たします。

set	ユニークなキーのコレクション、キーによってソートされる (class template)
multiset	キーによってソートされたキーのコレクション (クラステンプレート)
map	キーでソートされたキーと値のペアのコレクション、キーは一意 (クラステンプレート)
multimap	キーによってソートされたキーと値のペアのコレクション (クラステンプレート)

欠陥レポート

以下の動作変更を伴う欠陥報告が、以前に公開されたC++標準に遡って適用されました。

DR	適用対象	公開された動作	正しい動作
LWG 354	C++98	lower_bound と upper_bound が 要素が見つからない場合に end イテレータを返さない	この場合、end イテレータを返す
LWG 589	C++98	i と j が参照する要素 は X::value_type 型であった	要素は暗黙的に X::value_type に変換可能であった