//
//  When to use which container
//


                    vector    deque      list       set    multiset    map     multimap

typical internal    dynamic  array of    doubly    binary   binary    binary    binary
data structure      array     arrays   linked list  tree     tree      tree      tree

elements            value      value     value     value    value    key/value key/value

duplicates allowed   yes        yes       yes        no       yes       no        yes

random access        yes        yes       no         no       no      with key    no
iterator category   random    random   bidirect.  bidirect. bidirect. bidirect. bidirect.

search/find elem     slow      slow    very slow    fast      fast    fast(key) fast(key)

fast insert/remove  at end    at begin  abywhere     ---       ---       ---       ---
                              and end
inserting/removing
invalidates        on realloc  always     never     never     never     never     never
iterator, ptr, ref

frees memory         never    sometimes   always    always    always    always    always
for removed elems

allows memory         yes         no        ---       ---       ---        ---      ---
reservation

transaction safe  push_back() push_back()    all    all (except multiple element insert())
(success or       pop_back()  pop_back()   (except
 no effect)                   push_front()  sort())
                              pop_front()