それぞれのデータ操作に対するコンテナの処理速度
| コンテナの種類 | 先頭へ要素を追加/削除 | 末尾に要素を追加/削除 | コンテナの途中に要素を追加/削除 | ランダム･アクセス | 検索 | |
|---|---|---|---|---|---|---|
| vector | O(N)+ | O(1)+ | O(N)+ | O(1) | O(N) | |
| deque | O(1)+ | O(1) | O(N) | O(1) | O(N) | |
| list | O(1) | O(1) | O(1) | × | O(N) | |
| map | O(logN) | O(logN) | O(logN) | × | O(logN) | |
| multimap | O(logN) | O(logN) | O(logN) | × | O(logN) | |
| set | O(logN) | O(logN) | O(logN) | × | O(logN) | |
| multiset | O(logN) | O(logN) | O(logN) | × | O(logN) |
- O(N)は、要素の個数Nが増加するにつれて、Nに比例して時間がかかる
- O(logN)はNの対数に比例する
- O(1)は要素の個数によらない
- その後ろに+がついているのは、まれに余計に名時間がかかるケースがあることを意味する
- Nが十分に大きい時、速度はO(1)
- 要素数が少ない時は、データ構造が単純なコンテナがオーバーヘッドが少なく、高速
