Complexity of basic STL containers

\	.	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
  

Ones that I don't use often:

\	.	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)

Sequence container
1. vector
2. deque
3. list
4. slist
5. bit_vector

Associative containers
1. set
2. map
3. multiset
4. multimap
5. hash_set
6. hash_map
7. hash_multiset
8. hash_multimap

Container adaptors
1. stack (LIFO)
2. queue (FIFO)
3. priority_queue
.