低速 ← 対数 線形 償却 定数 → 高速
(注) 償却 : 償却定数時間。
たまに長い時間を要することがあるが、多くの場合は定数時間で処理が終わるため、
平均してみると処理にかかる時間を定数だとみなせるもの。
ex. vector の 末尾への追加。
キャパシティを超える場合のみ線形時間かかるが、通常は定数時間で処理が終わる。
| コンテナ | ヘッダ | カテゴリ | 先頭 | 末尾 | 中間 | 参照 | 挿入 | 削除 | 備考 |
|---|---|---|---|---|---|---|---|---|---|
| vector | <vector> | シーケンス | 線形 | 償却 | 線形 | 定数 | 参照はdequeより高速。末尾での挿入/削除、ランダムアクセスがメインならこれ。 | ||
| priority_queue | <queue> | アダプタ (vector) | 線形 | 償却 | 線形 | 定数 | |||
| deque | <deque> | シーケンス | 定数 | 定数 | 線形 | 定数 | 先頭での挿入/削除が多いならこれ。 | ||
| queue | <queue> | アダプタ (deque) | 定数 | 定数 | 線形 | 定数 | |||
| stack | <stack> | アダプタ (deque) | 定数 | 定数 | 線形 | 定数 | |||
| list | <list> | シーケンス | 定数 | 定数 | 定数 | - | ランダムアクセスの必要が無く、中間での挿入/削除が多いならこれ。 要素毎に前後２要素を指すポインタが必要なため、メモリ的には不利。 |
||
| map | <map> | 連想 | (償却) | 対数 | 対数 | 連想コンテナ間のパフォーマンスの違いは少ない。用途で選択すること。 | |||
| multimap | <map> | 連想 | (償却) | 対数 | 対数 | ||||
| set | <set> | 連想 | (償却) | 対数 | 対数 | ||||
| multiset | <set> | 連想 | (償却) | 対数 | 対数 |