// // 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()