Data Structures And STL

• queue: FIFO container.
• priority_queue: its first element is always the greatest of the elements it contains, according to some strict weak ordering condition.
• deque: Double-Ended QUEue (pronounced as 'deck'). Elements can be accessped by their index (time complexity: O(n). other operations: O(1) ); Iteration over the elements can be performed in any order; elements can be added and removed from both sides (queue: only one side). lacking some guarantees on iterator validity after altering the deque.
• list: a doubly-linked list; elements not stored in contiguous memory.
• list<bool>: optimizes for space by storing bool values as bits.
• vector: a dynamic array, capable of random access, with the ability to automatically resize itself when inserting or erasing objects. All elements allocated in continuous block of memory.
• map: a sorted associative array; allows mapping from a key to a value. Type of key must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree.
• multimap: map allowing duplicate keys.
• set: a sorted set; inserting/erasing elements in a set does not invalidate iterators pointing in the set. Provides set operations union, intersection, difference, symmetric difference and test of inclusion. Type of data must implement comparison operator < or custom comparator function must be specified. Implemented using a self-balancing binary search tree.
• multiset: a set allowing duplicate elements.
• hash_set, hash_multiset, hash_map, hash_multimap: implemented using a hash table; keys are not sorted, but a hash function must exist for key type. These containers are not part of the C++ Standard Library, but are included in SGI's STL extensions, and are included in common libraries such as the GNU C++ Library in the __gnu_cxx namespace. These are scheduled to be added to the C++ standard as part of TR1, with the slightly different names of unordered_set, unordered_multiset, unordered_map and unordered_multimap.
• bitset: stores series of bits similar to a fixed-sized vector<bool>. Implements bitwise operations and lacks iterators. Not a Sequence.
• valarray: another C-like array like vector, but is designed for high speed numerics at the expense of some programming ease and general purpose use. It has many features that make it ideally suited for use with vector processors in traditional vector supercomputers and SIMD units in consumer-level scalar processors, and also ease vector mathematics programming even in scalar computers.
• stack: LIFO container.

Deque, vector and list

A deque is usually implemented as a list, so insertions / deletions in it is much faster than in vectors. Also, adding/taking elements from both ends are as fast as O(1). In order to improve the performance, the deque is usually implemented as a list of pages, inside each page several elements are held in the continuous memory (as in a vector). This makes a deque looks like a 'deck' of cards, and the speed of traversing through elements is between O(1) and O(n) (but it still takes several times of the amount of the same operations in a vector).

vector vs list vs deque:

*1 When a lot of elements are added, you need to call vector::reserve(n) to reserve a big block of memory, so vector won't keep increasing its capacity; when a lot of elements are deleted, you need to call vector::shrink_to_fit() to release the reserved memory (calling vector::reserve(smaller_num) won't work).