Sequential containers
| Container | std::array |
std::vector |
std::list |
|---|---|---|---|
| Low-level implementation | Fixed capacity array. | A contiguous array that can grow in capacity dynamically. | Doubly linked list |
Access: front() |
\(O(1)\) | \(O(1)\) | \(O(1)\) |
Access: back() |
\(O(1)\) | \(O(1)\) | \(O(1)\) (not supported by std::forward_list) |
Access: at(idx) |
\(O(1)\) | \(O(1)\) | Not supported |
Search: .find |
\(O(n)\) | \(O(n)\) | \(O(n)\) |
Insertion:insert(@begin,val) |
— | \(O(n+m)\) | \(O(1)\) |
Insertion:insert(@pos,val) |
— | \(O(n+m)\) | \(O(1)\) |
Insertion:insert(@end,val) |
— | Amortized \(O(1)\) | \(O(1)\) |
Deletion:.erase |
— | \(O(n+m)\) | \(O(1)\) |
| Deletion: Middle | — | \(O(n+m)\) | \(O(1)\) |
| Deletion: End | — | \(O(1)\) | \(O(1)\) |
Associative containers
| Container | std::set |
std::map |
std::unordered_set |
std::unordered_map |
|---|---|---|---|---|
| Low-level implementation | Red-Black Tree | Red-Black Tree | Hash-table | Hash-table |
Access: operator[](Key key) |
\(O(\log n)\) | \(O(\log n)\) | Average case - Amortized \(O(1)\) Worst case - \(O(n)\) |
Average case - Amortized \(O(1)\) Worst case - \(O(n)\) |
| Insertion | \(O(\log n)\) | \(O(\log n)\) | Average case - Amortized \(O(1)\) Worst case - \(O(n)\) |
Average case - Amortized \(O(1)\) Worst case - \(O(n)\) |
| Deletion | \(O(\log n)\) (Amortized \(O(1)\) iterator) |
\(O(\log n)\) (Amortized \(O(1)\) with an iterator) |
Average case - Amortized \(O(1)\) Worst case - \(O(n)\) |
Average case - Amortized \(O(1)\) Worst case - \(O(n)\) |