Essential C++ Data Structures for Competitive Programming
What is C++ STL?
A standout feature of C++ is the Standard Template Library (STL), setting it apart from other programming languages. STL offers a collection of pre-defined templates, including containers, algorithms, and iterators, simplifying the implementation of various data structures without writing everything from scratch.
Containers and Functions in C++ STL
1. unordered_set
An unordered_set is a container that stores unique elements in no particular order. It allows fast retrieval of individual elements based on their value. 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 that can resize itself automatically when an element is added or removed. 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.size(): Returns the number of elements in the vector.
3. set
A set is a container that stores unique elements in a specific order. Elements are automatically sorted. 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. 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 an element.
5. multiset
A multiset is like a set, but it allows duplicate elements, and they are stored in a 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 an element.
6. unordered_map
An unordered_map is a key-value pair container where keys are unique, but the order of elements is not maintained. 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 given key.operator[key]: Accesses the value associated with the given key, inserting a new key-value pair if it doesn’t exist.
7. map
A map is an associative container that stores elements in key-value pairs with unique keys. Elements are stored in sorted order based on the key. 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 given key.operator[key]: Accesses the value associated with the given key, inserting a new key-value pair if it doesn’t exist.
8. unordered_multimap
An unordered_multimap is similar to an unordered_map, but it allows multiple pairs with the same 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 given key.
9. queue
A queue is a First-In-First-Out (FIFO) data structure that 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 of the queue.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 that allows insertion and removal of elements at the top of the stack. Common functions include:
push(value): Adds an element to the top of the stack.pop(): Removes the top element of the stack.top(): Returns a reference to the top element.
11. deque
A deque (double-ended queue) is a container that 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 type of queue where each element has a priority. Elements with higher priority are served before elements with lower priority, regardless of their order in the queue. Common functions include:
push(value): Adds an element to the queue based on its priority.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 given key.