| \ | . | possible implementation | insert/remove at the beginning | insert/remove at the end | find |
| vector | sequence, key not unique, back-insertion | dynamic array (malloc) | o(n) | o(1) | o(1) (operator[]) o(n) (iter or algo) |
| list | sequence, key not unique | doubly-linked list | o(1) | o(1) | o(n) (iter or algo) |
| set | sorted associative container, key unique | sorted tree | o(log(n)) | o(log(n)) | o(log(n)) |
| map | sorted associative container, key unique | sorted tree | o(log(n)) | o(log(n)) | o(log(n)) |
| hash_map | hashed associative container, key unique | hashmap | o(1) | o(1) | o(1) |
Notes:
- for insert/remove in list, assumes we have the iterator at the right position
- no push_back on associative containers
| \ | . | possible implementation | insert/remove at the beginning | insert/remove at the end | find |
| deque | sequence, key not unique o(n) in the middle | dynamic array or doubly-linked list | o(1) | o(1) | o(n) |
| slist | sequence, key not unique, single direction iterator, front-insertion | single-linked list | o(1) | o(n) o(1) if insert_after | o(n) |
1. vector
2. deque
3. list
4. slist
5. bit_vector
1. set
2. map
3. multiset
4. multimap
5. hash_set
6. hash_map
7. hash_multiset
8. hash_multimap
1. stack (LIFO)
2. queue (FIFO)
3. priority_queue
.
