目次

注意

以下の説明において:

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

更新履歴

test

[雑記]

ブログ