The C++ STL can be broadly divided into four parts:
- Containers
- Functor (Not important)
- Iterators
- Algorithms
Containers are used to manage collections of objects of a certain kind. There are several different types of containers like dequeue, list, vector, map etc.
A short overview of all containers:
-
Vector - Dynamic arrays
-
String - Essentially a vector of characters with extra string functionality.
-
List - Doubly linked lists
-
Dequeue - Double ended Queue
-
Array - A container that encapsulates fixed size arrays.
-
Queue - Queue data structure
-
Stack - Stack Data structure
-
Priority Queue - A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
-
Set - It is an associative container that contains a sorted set of unique objects.
-
Multiset - Same as set but supports repeated elements
-
Map - It is a sorted associative container that contains key-value pairs with unique keys.
-
Multimap - Same as map, while permitting multiple entries with the same key.
-
Unordered_set - It is an associative container that contains a set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity.
-
Unordered_multiset - Same as unordered set but supports repeated elements.
-
Unordered_map - It is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.
-
Unordered_multimap - Same as map but supports mapping one key to many values.
It is recommended that you go through the methods present on each of these containers and understand what they achieve and the time complexity of that method.
A wonderful feature that was introduced in recent versions of C++ is the range based for loop.
For those that come from other programming backgrounds, this would be a metaphor to a For-Each loop.
A range based for loop provides an easy way of iterating over complex containers without having to setup your beginning and ending conditions.
Tutorial on range based for loops
PS: [ Iterators are not all that common but sometimes you'll have no choice but to use them and that's why this section exists. Example - Deleting a single element from a multiset can be achieved using mostly iterators. ]
An iterator is an object (like a pointer) that points to an element inside the container. We can use iterators to move through the contents of the container. They can be visualized as something similar to a pointer pointing to some location and we can access the content at that particular location using them.
The C++ STL comes with some pre-implemented algorithms and it is important for you to at least know that the following ones exist at your disposal:
-
std::sort - Sorting a container.
-
std::reverse - Reversing a container.
-
std::max_element - Returns an iterator to the largest element of a container.
-
std::min_element - Returns an iterator to the smallest element of a container.
-
std::binary_search - Binary search in an ordered container to check existence of element.
-
std::lower_bound - Returns an iterator pointing to the first element in the range that is not less than (i.e. greater or equal to) value.
-
std::upper_bound - Returns an iterator pointing to the first element in the range that is greater than value.
-
std::next_permutation - Permutes the range into the next permutation, where the set of all permutations is ordered lexicographically with respect to operator < or comp.
-
std::prev_permutation - Transforms the range into the previous permutation from the set of all permutations that are lexicographically ordered with respect to operator < or comp.