Namespaces
Variants

C++ named requirements: AssociativeContainer

From cppreference.net
C++
C++ named requirements

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

連想コンテナは、各キーに対して最大1つの要素しか含まない場合、 unique keys をサポートします。それ以外の場合、 equivalent keys をサポートします。

目次

要件

**翻訳の説明:** - HTMLタグ、属性、クラス名はすべてそのまま保持 - ` `タグ内の`X::value_type`はC++の型名なので翻訳せず保持 - 「A value of type」を「型の値」と正確に翻訳 - 元のフォーマットと構造を完全に維持
凡例
X 連想コンテナクラス
T X の要素型
A Xのアロケータ型： X::allocator_type が存在する場合、それ以外の場合は std:: allocator < X :: value_type >
a X 型の値
a2 Y 型の値で、 node handles が X と互換性のあるもの
b X 型または const X 型の値
u 宣言されている変数の名前
a_uniq X 型の値（ X がユニークキーをサポートする場合）
a_eq X 型の値（ X が等価キーをサポートする場合）
a_tran X 型または X::key_compare::is_transparent が存在する場合の const X 型の値
i , j LegacyInputIterator を参照するイテレータ で、 X::value_type に暗黙的に変換可能な要素を指す
[ i , j ) 有効な範囲
rg
(C++23以降) 		container-compatible-range <value_type> をモデル化する型 R の値
p a への有効な定数イテレータ
q 有効な逆参照可能な定数イテレータ a を指す
r a への有効な逆参照可能なイテレータ
q1 , q2 a 内の有効なconstイテレータの範囲
il std:: initializer_list < X :: value_type > 型のオブジェクト
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 (until C++11) AllocatorAwareContainer (since C++11) を満たす。
  • Key と Key の要素に対して 狭義の弱順序 を誘導する順序関係 Compare をパラメータ化する。
    • さらに、 std::map と std::multimap は任意の マップされた型 T を Key に関連付ける。
    • 型 Compare のオブジェクトは、型 X のコンテナの 比較オブジェクト と呼ばれる。
  • すべての連想コンテナに対して以下の式は有効であり、指定された効果を持たなければならない：

型

名前 型 要件
key_type Key
mapped_type T （ std::map および std::multimap のみ）
value_type Erasable from X
key_compare Compare CopyConstructible
value_compare BinaryPredicate
node_type node-handle class template の特殊化であり、公開されたネスト型が X の対応する型と同じ型であるもの。

メンバー関数と演算子

HTMLタグ、属性、 タグ内のテキスト、C++固有の用語は翻訳せず、元のフォーマットを保持しました。 **注記**: このC++コードは翻訳対象外のため、元のまま保持されています。HTMLタグ、属性、および` `内のC++コードは一切翻訳していません。 **注記**: 提供されたHTMLコード内のテキストはすべてC++コードであり、` `タグで囲まれているため、翻訳対象外となります。HTMLタグ、属性、およびC++コードはすべて原文のまま保持されています。
式 結果 事前条件 効果 戻り値 計算量
X ( c ) 空のコンテナを構築します。比較オブジェクトとして c のコピーを使用します 定数時間
X u = X ( ) ;
X u ; 		key_compare は DefaultConstructible 要件を満たす 空のコンテナを構築する。 Compare ( ) を比較オブジェクトとして使用する 定数時間
X ( i, j, c ) value_type は EmplaceConstructible 要件を満たし、 X に * i から構築可能であること 空のコンテナを構築し、範囲 [ i , j ) から要素を挿入する； c を比較オブジェクトとして使用する N·log ( N ) の計算量（一般ケース）、ここで N は std:: distance ( i, j ) の値； [ i , j ) が value_comp ( ) に関してソートされている場合は線形計算量
X ( i, j ) key_compare は DefaultConstructible 要件を満たす。 value_type は EmplaceConstructible であり、 X に * i から構築可能 空のコンテナを構築し、範囲 [ i , j ) から要素を挿入する。比較オブジェクトとして Compare ( ) を使用する
X ( from_range, rg, c )
(C++23以降) 		value_type が EmplaceConstructible であり、 X に * ranges:: begin ( rg ) から構築可能であること 空のコンテナを構築し、 rg から各要素を挿入する。 c を比較オブジェクトとして使用する N·log ( N ) の計算量（一般ケース）。ここで N は ranges:: distance ( rg ) の値である。 rg が value_comp ( ) に関してソートされている場合は線形計算量
X ( from_range, rg )
(C++23以降) 		key_compare は DefaultConstructible 要件を満たす。 value_type は EmplaceConstructible であり、 X に * ranges:: begin ( rg ) から構築可能 空のコンテナを構築し、 rg の各要素を挿入する。比較オブジェクトとして Compare ( ) を使用する
X ( il, c ) X ( il. begin ( ) , il. end ( ) , c )
X ( il ) X ( il. begin ( ) , il. end ( ) )
a = il X & value_type が CopyInsertable であり、 X に挿入可能かつ 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 の構築に使用された比較オブジェクト 定数
b. value_comp ( ) X::value_compare 比較オブジェクトから構築された value_compare のオブジェクト 定数
a_uniq. emplace ( args ) std:: pair <
iterator,
bool > 		value_type が EmplaceConstructible 要件を満たし、 X に args から構築可能であること value_type オブジェクト t を std:: forward < Args > ( args ) ... で構築し、コンテナ内に t のキーと等価なキーを持つ要素が存在しない場合にのみ挿入する 返されるpairの bool コンポーネントは、挿入が行われた場合にのみ true となり、pairのイテレータコンポーネントは t のキーと等価なキーを持つ要素を指す 対数時間
a_eq. emplace ( args ) iterator value_type が EmplaceConstructible であること（ X に対して args から構築可能） std:: forward < Args > ( args ) ... で構築された value_type オブジェクト t を挿入する。 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 は MoveInsertable でなければならない。それ以外の場合、 value_type は CopyInsertable でなければならない。 t のキーと等価なキーを持つ要素がコンテナ内に存在しない場合にのみ t を挿入する 返されるpairの bool コンポーネントは、挿入が行われた場合にのみ true となり、pairの iterator コンポーネントは t のキーと等価なキーを持つ要素を指す 対数時間
a_eq. insert ( t ) iterator t が非const右辺値の場合、 value_type は MoveInsertable でなければならない。それ以外の場合、 value_type は CopyInsertable でなければならない t を挿入し、新しく挿入された要素を指すイテレータを返す。 t と等価な要素を含む範囲が a_eq に存在する場合、 t はその範囲の末尾に挿入される 対数時間
a. insert ( p, t ) iterator t が非const右辺値の場合、 value_type は MoveInsertable でなければならない。それ以外の場合、 value_type は CopyInsertable でなければならない。 一意キーを持つコンテナでは、 t のキーと等価なキーを持つ要素が存在しない場合にのみ t を挿入する。等価キーを持つコンテナでは常に t を挿入する。 t は p の直前の位置にできるだけ近い位置に挿入される。 t のキーと等価なキーを持つ要素を指すイテレータ 一般的には対数時間だが、 t が p の直前に挿入される場合は償却定数時間
a. insert ( i, j ) void value_type は EmplaceConstructible であり、 X に * i から構築可能であること。 i および j は a のイテレータではないこと 範囲 [ i , j ) の各要素を挿入する。ユニークキーを持つコンテナでは、その要素のキーと等価なキーを持つ要素がコンテナ内に存在しない場合にのみ挿入する。等価キーを持つコンテナでは常にその要素を挿入する N·log ( a. size ( ) + N ) 。ここで N は std:: distance ( i, j ) の値
a. insert_range ( rg )
(C++23以降) 		void value_type が EmplaceConstructible であり、 X に * ranges:: begin ( rg ) から構築可能であること。 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 が所有する要素を挿入し、新しく挿入された要素を指すイテレータを返す。 nh. key ( ) と等価なキーを持つ要素の範囲が a_eq に存在する場合、その範囲の末尾に要素が挿入される。保証事項: nh は空になる 対数時間
a. insert ( p, nh ) iterator nh が空であるか、

a. get_allocator ( )
==
nh. get_allocator ( ) が true であること

nh が空の場合、何も効果がなく a. end ( ) を返す。それ以外の場合、一意キーを持つコンテナでは nh. key ( ) と等価なキーを持つ要素が存在しない場合にのみ、 nh が所有する要素を挿入する。等価キーを持つコンテナでは常に nh が所有する要素を挿入する。要素は p の直前の位置にできるだけ近く挿入される。挿入が成功した場合は 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 に挿入しようと試みます。一意なキーを持つコンテナでは、 a に a2 からの要素のキーと等価なキーを持つ要素が存在する場合、その要素は 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 ; const_iterator 定数オブジェクト用 b キー k と等価な要素を指すイテレータ、またはそのような要素が見つからない場合は b. end ( ) を返す 対数時間
a_tran. find ( ke ) iterator ; const_iterator 定数 a_tran 用 キー 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 ; const_iterator 定数オブジェクト用 b キー k 以上となる最初の要素を指すイテレータ。そのような要素が見つからない場合は b. end ( ) を返す 対数時間
a_tran. lower_bound ( kl ) iterator ; const_iterator は定数 a_tran に対して キー r を持つ最初の要素を指すイテレータ。ただし ! c ( r, kl ) を満たすもの。そのような要素が見つからない場合は a_tran. end ( ) を返す 対数時間
b. upper_bound ( k ) iterator ; const_iterator 定数用 b k より大きいキーを持つ最初の要素を指すイテレータ、またはそのような要素が見つからない場合は b. end ( ) 対数時間
a_tran. upper_bound ( ku ) iterator ; const_iterator 定数 a_tran 用 キー r を持つ最初の要素を指すイテレータ。ただし c ( ku, r ) の条件を満たすもの。そのような要素が見つからない場合は a_tran. end ( ) を返す 対数時間
b. equal_range ( k ) std:: pair <
iterator,
iterator > ;

std:: pair <
const_iterator,
const_iterator > 定数 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 > constな 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 要件を満たします：

一意のキーのコレクション、キーでソート
(クラステンプレート)
キーのコレクション、キーでソート
(クラステンプレート)
キーと値のペアのコレクション、キーでソート、キーは一意
(クラステンプレート)
キーと値のペアのコレクション、キーでソート
(クラステンプレート)

不具合報告

以下の動作変更の欠陥報告書は、以前に公開されたC++規格に対して遡及的に適用されました。

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