Monday, June 28, 2010

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