注意

以下の説明において:

n   :負でない整数
t   :要素のインスタンス
i,j :input iterator
p,q :要素のイテレータ
X   :コンテナのクラス名
x   :コンテナのインスタンス
N   :コンテナのサイズ

コンテナ内で定義された型

	vector,deque	list	set,multiset	map,multimap
key_type			○	○
mapped_type				○
key_compare			○	○
reference	○	○	○	○
const_reference	○	○	○	○
iterator	○	○	○	○
const_iterator	○	○	○	○
reverse_iterator	○	○	○	○
const_reverse_iterator	○	○	○	○
size_type	○	○	○	○
defference_type	○	○	○	○
value_type	○	○	○	○
value_compare			○	○
allocator_type	○	○	○	○
pointer	○	○	○	○
const_pointer	○	○	○	○
イテレータ-の種類	RandomAccess	Bidirectional	Bidirectional	Bidirectional

・可能な操作とそのオーダー

コンストラクタ/デストラクタ/コピー/交換

n    :負でない整数
t    :要素のインスタンス
i,j  :input iterator
X    :コンテナのクラス名
x    :コンテナのインスタンス
comp :比較オブジェクト
alloc:アロケーター

	vector,deque,list	set,multiset,map,multimap
X(alloc)	○
X(comp,alloc)		○
X(i,j,alloc)	○
X(i,j,comp,alloc)		○
X(x)	○	○
~X()	○	○
operator=(x)	○	○
assign(i,j)	○	○
assign(n,t)	○	○
swap(x)	○	○
get_allocator()	○	○

イテレータ

すべてのコンテナに共通

begin()

end()

rbegin()

rend()

辞書式比較

すべてのコンテナに共通

x:コンテナのインスタンス

operator==(x)

operator!=(x)

operator<(x)

operator>(x)

operator<=(x)

operator>=(x)

要素数/領域確保

n   :負でない整数
t   :要素のインスタンス

	vector	deque,list	set,multiset,map,multimap
size()	○	○	○
max_size()	○	○	○
empty()	○	○	○
resize(n,t)	○	○
capacity()	○
reserv(n)	○

参照

n   :負でない整数
N   :コンテナのサイズ
key :連想コンテナのキー

	vector	deque	list	set	multiset	map	multimap
front()	O(1)	O(1)	O(1)
back()	O(1)	O(1)	O(1)
at(n)	O(1)	O(1)
x[n]	O(1)	O(1)
x[key]						O(logN)

挿入

n   :負でない整数
t   :要素のインスタンス
i,j :input iterator
p,q :要素のイテレータ
N   :コンテナのサイズ

	vector	deque	list	set	multiset	map	multimap
insert(p,t)	O(N)	O(N)	O(1)	O(logN)	O(logN)	O(logN)	O(logN)
insert(p,n,t)	O(N)	O(N)	O(1)
insert(p,i,j)	O(N)	O(N)	O(1)	O(logN)	O(logN)	O(logN)	O(logN)
insert(t)				O(logN)	O(logN)	O(logN)	O(logN)
push_front()		O(1)	O(1)
push_back()	O(1)	O(1)	O(1)

削除

p,q :要素のイテレータ
N   :コンテナのサイズ
key :連想コンテナのキー

	vector	deque	list	set	multiset	map	multimap
erase(p)	O(N)	O(N)	O(1)	O(logN)	O(logN)	O(logN)	O(logN)
erase(p,q)	O(N)	O(N)	O(1)	O(logN)	O(logN)	O(logN)	O(logN)
erase(key)				O(logN)	O(logN)	O(logN)	O(logN)
clear()	O(N)	O(N)	O(N)	O(N)	O(N)	O(N)	O(N)
pop_front()		O(1)	O(1)
pop_back()	O(1)	O(1)	O(1)

検索

N   :コンテナのサイズ
key :連想コンテナのキー

	set,multiset,map,multimap
find(key)	O(logN)
count(key)	O(logN)
lower_bound(key)	O(logN)
upper_bound(key)	O(logN)
equallrange(key)	O(logN)
key_compare()	○
value_compare	○

リスト操作

t   :要素のインスタンス
i,j :input iterator
p,q :要素のイテレータ
x   :コンテナのインスタンス
pred:述語(真理値を返す関数オブジェクト)
comp:比較オブジェクト

splice(p,x)

splice(p,x,i)

splice(p,x,i,j)

remove(t)

remove(pred)

unique()

unique(pred)

marge(x)

marge(x,comp)

sort()

sort(comp)

reverse()