Essential C++ data structures for competitive programming

What is the C++ standard library (often called the STL)?

The C++ standard library (often called the STL) provides containers, algorithms, and iterators. It gives you standard implementations of common data structures, so you do not have to write each one from scratch. The STL does not remove the need to understand the tradeoffs: container choice affects ordering, lookup, memory use, and available operations.

STL containers and common functions

1. unordered_set

An unordered_set stores unique elements without maintaining a sorted order. Lookup is usually fast on average, but the order is unspecified and the worst case can be slower. Common functions include:

• insert(value): Adds an element to the set.
• find(value): Searches for an element and returns an iterator to it if found, otherwise returns the end iterator.
• erase(value): Removes an element from the set.

2. vector

A vector is a dynamic array whose size changes automatically when elements are added or removed. Adding elements can increase its capacity, while erasing elements changes the size but does not necessarily reduce the capacity. It provides random access to elements. Common functions include:

• push_back(value): Adds an element to the end of the vector.
• pop_back(): Removes the last element of the vector.
• at(index): Returns a reference to the element at the specified position and checks the bounds.
• size(): Returns the number of elements in the vector.

3. set

A set stores unique elements in sorted order according to its comparison rule. Common functions include:

• insert(value): Adds an element to the set.
• find(value): Searches for an element and returns an iterator to it if found.
• erase(value): Removes an element from the set.

4. unordered_multiset

An unordered_multiset is similar to an unordered_set, but it allows duplicate elements. The order is unspecified, and lookup performance is usually fast on average. Common functions include:

• insert(value): Adds an element to the multiset.
• count(value): Returns the number of occurrences of an element.
• erase(value): Removes all occurrences of the value.

5. multiset

A multiset is like a set, but it allows duplicate elements, and they are stored in sorted order. Common functions include:

• insert(value): Adds an element to the multiset.
• count(value): Returns the number of occurrences of an element.
• erase(value): Removes all occurrences of the value.

6. unordered_map

An unordered_map stores key-value pairs. Keys are unique, but the container does not maintain an order. Lookup is usually fast on average, with a possible worst-case slowdown. Common functions include:

• insert({key, value}): Adds a key-value pair to the map.
• find(key): Searches for an element by its key and returns an iterator to it if found.
• erase(key): Removes the element associated with the key.
• operator[](key): Accesses the value associated with the key, inserting a new key-value pair if the key does not exist.

7. map

A map is an associative container that stores key-value pairs with unique keys. Elements are stored in sorted order based on the key and its comparison rule. Common functions include:

• insert({key, value}): Adds a key-value pair to the map.
• find(key): Searches for an element by its key and returns an iterator to it if found.
• erase(key): Removes the element associated with the key.
• operator[](key): Accesses the value associated with the key, inserting a new key-value pair if the key does not exist.

8. unordered_multimap

An unordered_multimap is similar to an unordered_map, but it allows multiple pairs with the same key. The order is unspecified. Common functions include:

• insert({key, value}): Adds a key-value pair to the multimap.
• equal_range(key): Returns a range of elements with the same key.
• erase(key): Removes all elements associated with the key.

9. queue

A queue is a First-In-First-Out (FIFO) data structure. It allows insertion at the back and removal from the front. Common functions include:

• push(value): Adds an element to the back of the queue.
• pop(): Removes the front element. It does not return that element.
• front(): Returns a reference to the front element.
• back(): Returns a reference to the back element.

10. stack

A stack is a Last-In-First-Out (LIFO) data structure. It allows insertion and removal of elements at the top. Common functions include:

• push(value): Adds an element to the top of the stack.
• pop(): Removes the top element. It does not return that element.
• top(): Returns a reference to the top element.

11. deque

A deque (double-ended queue) allows insertion and deletion of elements from both the front and the back. Common functions include:

• push_back(value): Adds an element to the back of the deque.
• push_front(value): Adds an element to the front of the deque.
• pop_back(): Removes the last element of the deque.
• pop_front(): Removes the first element of the deque.

12. priority_queue

A priority_queue is a queue where the element at the top has the highest priority according to its comparison rule. By default, the largest element is at the top. Common functions include:

• push(value): Adds an element to the queue.
• pop(): Removes the element with the highest priority.
• top(): Returns a reference to the element with the highest priority.

13. multimap

A multimap is similar to a map, but it allows multiple values for the same key. Elements are stored in sorted order based on the key. Common functions include:

• insert({key, value}): Adds a key-value pair to the multimap.
• equal_range(key): Returns a range of elements with the same key.
• erase(key): Removes all elements associated with the key.

When an operation accesses a value, make sure the container is not empty. Also remember that pop() removes an element but does not return it, so read it with front(), back(), top(), or the relevant iterator before removing it.