- n → number of elements
- k → key length (for maps/sets of strings, etc.)
- amort. → amortized
- All maps/sets assume balanced BST (Red-Black Tree) or hashing as per their underlying implementation
C++ STL Data Structures Time Complexity Table
| Data Structure |
Access |
Insertion |
Deletion |
Search |
Traversal |
array |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
vector |
O(1) |
O(1) amortized |
O(n) (worst-case) |
O(n) |
O(n) |
deque |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
list (doubly) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
forward_list |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
stack |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
queue |
O(1) |
O(1) |
O(1) |
O(n) |
O(n) |
priority_queue |
N/A |
O(log n) |
O(log n) |
O(n) |
O(n) |
set (std::set) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
multiset |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
unordered_set |
O(1) |
O(1) avg / O(n) worst |
O(1) avg / O(n) worst |
O(1) avg / O(n) worst |
O(n) |
map (std::map) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
multimap |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(n) |
unordered_map |
O(1) |
O(1) avg / O(n) worst |
O(1) avg / O(n) worst |
O(1) avg / O(n) worst |
O(n) |
bitset |
O(1) |
O(1) |
O(1) |
O(1) |
O(n) |
string |
O(1) |
O(1) amortized |
O(n) |
O(n) |
O(n) |
Notes:
vector insert/delete at end is O(1) amortized; insert at middle or front is O(n)unordered_map and unordered_set can degrade to O(n) if many collisions occurmap and set are implemented using Red-Black Trees, hence O(log n)priority_queue uses a heap, so insertion and deletion (pop) are O(log n)bitset is efficient for fixed-size binary data manipulationlist and forward_list give O(1) insertion/deletion if you already have the iterator