Cases
- B … Best case
- A … Average case
- W … Worst case
If there is nothing mentioned, it matches all cases.
1. Sequence containers
| Operation | Array | Vector | Deque | Forward_list | List |
|---|---|---|---|---|---|
| Access Head | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
| Access Index | Θ(1) | Θ(1) | Θ(1) | B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
| Access Tail | Θ(1) | Θ(1) | Θ(1) | Θ(n) | Θ(1) |
| Insert Head | – | Θ(n) | Θ(1) | Θ(1) | Θ(1) |
| Insert Index | – | B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
| Insert Tail | – | B, A: Θ(1) W[1]: Θ(n) |
Θ(1) | Θ(n) | Θ(1) |
| Remove Head | – | Θ(n) | Θ(1) | Θ(1) | Θ(1) |
| Remove Index | – | B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
| Remove Tail | – | Θ(1) | Θ(1) | Θ(n) | Θ(1) |
| Search by Value | B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
B: Θ(1) A, W: Θ(n) |
2. Associative containers
| Operation | Set | Map | Unordered_set | Unordered_map |
|---|---|---|---|---|
| Insert Key (+Val) | Θ(log(n)) | Θ(log(n)) | B, A: Θ(1) W[2]: Θ(n) |
B, A: Θ(1) W[2]: Θ(n) |
| Search by Key | B: Θ(1) A, W: Θ(log(n)) |
B: Θ(1) A, W: Θ(log(n)) |
B, A: Θ(1) W[α]: Θ(n) |
B, A: Θ(1) W[α]: Θ(n) |
| Search by Value | – | B: Θ(1) A, W: Θ(n) |
– | B: Θ(1) A, W: Θ(n) |
| Remove by Key | Θ(log(n)) | Θ(log(n)) | B, A: Θ(1) W[α]: Θ(n) |
B, A: Θ(1) W[α]: Θ(n) |
| Remove by Value | – | B: Θ(1) A, W: Θ(n) |
– | B: Θ(1) A, W: Θ(n) |
[α] … All items are in one bucket.
3. Container adaptors
| Operation | Stack[α1] | Queue[α1] | Priority_queue[α2] |
|---|---|---|---|
| Access Head | Θ(1) | Θ(1) | – |
| Access Tail | – | Θ(1) | Θ(1) |
| Insert Head | Θ(1) | – | – |
| Insert Tail | – | Θ(1) | – |
| Insert Value | – | – | B, A[β]: Θ(1) W[1]: Θ(n) |
| Remove Head | Θ(1) | Θ(1) | – |
| Remove Tail | – | – | B[γ]: Θ(1) A, W: Θ(log(n)) |
[α1] … Container underneath is std::deque (default).
[α2] … Container underneath is std::vector (default).
[β] … “Average Case Analysis of Heap Building by Repeated Insertion” (by Hayward & McDiarmid)
[γ] … All nodes have the same value.
Notes
[1] … Insert element triggers a relocation.
[2] … Insert element triggers a rehashing.