注意

以下の説明において:

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

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

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

```csharp 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)

要素数/領域確保

```csharp n :負でない整数 t :要素のインスタンス ```
vector deque,list set,multiset,map,multimap

size()

○

○

○

max_size()

○

○

○

empty()

○

○

○

resize(n,t)

○

○

capacity()

○

reserv(n)

○

参照

```csharp 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)

挿入

```csharp 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)

削除

```csharp 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)

検索

```csharp 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

○

リスト操作

```csharp 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()