Standard Library

Containers usage in the Standard library

	Description	Implementation	Best case	Worst case	Insert	Remove	Look up
List	Fast insertion and deletion Sequencial access	Abstraction for a doubly linked list	Good for storing an unpredictable number of items specially if it fluctuates Lots of inserts and deletes Many items unknown amount	Store small data (a 32 bit integer for example will account for 96 bits in total) Can rapidly lead to bad memory fragmentation If you need constant time random access	O(1)	O(1)	O(n)
Vectors	Fastest iteration Random access	The default allocator will just double the size of the internal  buffer when current capacity is reached Compilers may use different strategies  Efficient when pushing back Deleting and removing in the middle of the vector is very expensive Random access and low latency reads	Consider it when you have a rough idea of the number of items Data can be either added all in one go Access the contents in any order	Do frequent inserts/deletes anywhere other than the back of the vector Don't know how much data to put in it	O()		O(1)
Dequeu	Dynamic one dimentional array The size of the buffer may possibly be greater  than the size of the data Similar to vector Add/Remove from head and tail	Efficient when appending front or back	Growing the buffer is very costly No mechanism to reserve buffer Internal buffer memory may not shrink when the container is cleared Don't insert in the middle				O(1)
Map	Sorted associative container that represents an abstraction of an ordered,  unique key	Typically implemented as a binary search tree	Sorted order Sorted inforced real time Filter out duplicates Store data appending to existing data access  contents in any orde The need for compatibility with C style arrays Not good when doing frequent inserts or deletes anywhere than back or front	Size of your data items is very small			O(1)
Multimap
Set	Associative container of an ordered unique key. The value is itself the key	Implemented as a binary tree sparse hash set, dense hast set	Sorted order Sorted inforced real time Filter out duplicates	Can't use third party hash Nature of data means doesn't has well (many collisions) The size of your data is very small. Cannot afford to accet the fact that access is not in constant time You can get away with using a has set			O(log N)
Multiset
Queue
Stack