The Complete Practical Guide to C++ STL(Standard Template Library)

6 min readMay 21, 2019

C++ STL is an integral part of competitive programming in c++. If you are in an undergraduate college and want to appear in placements, then question from c++ stl will be asked in interviews.

I will start with some theory for foundation, then it is all practical.

So without wasting any more time, Let’s get started.

First of all, what is C++ STL?

C++ STL is a set of data structures and algorithms that we normally encounter during coding. For example, while solving a problem you wanted to use linked list, so will you create a linked list from scratch? The answer is no, you will use list built into c++ stl library. There are a lot of similar examples which I will be giving throughout this article.

STL has four components

Algorithms
Containers
Functors
Iterators

Algorithms

The header algorithm defines a lot of commonly used algorithms that we can use out of box. They provide various operation for containers. Some well-known algorithms are

sort() — for sorting.

binary_search() — for searching element

Containers

Containers or container classes store objects and data. Some container classes are given below

vector, list, forward_list, queue, priority_queue, stack, set, multiset, map, multimap, unordered_set

Iterators

As the name suggests, iterators are used for working upon a sequence of values.

Functors

The STL includes classes that overload the function call operator. Instances of such classes are called function objects or functors.

First, let’s understand a bit about pair.

Pair

Now starting with the most basic container

Vectors

Vector is a kind of array with a lot of extra functionalities. You must have used arrays and must be dissatisfied with the limitations of arrays. Vectors come into rescue.

#include<vector>
Syntax  — vector<DATA_TYPE> variable_name;
Example — vector<int> v; // v is a vector of int

General Vector Methods

begin() — Returns an iterator to the first element in the vectorend() — Returns an iterator to a location past last element in the vectorsize() — Returns the number of elements in the vector.resize() — Resizes the container.empty() — Returns whether the container is empty.front() — Returns a reference to the first element in the vectorback() — Returns a reference to the last element in the vectorpush_back() — It push the elements into a vector from the backpop_back() — It is used to pop or remove elements from a vector from the back.insert() — It inserts new elements before the element at the specified positionerase() — It is used to remove elements from a container from the specified position or range.clear() — It is used to remove all the elements of the vector container

In the first function displayVector, I have used normal method. It says that-

it is a constant iterator to vector of int. Here initially it is a pointer to first element in vector.

In the second function autoVector, auto keyword is used to take data type automatically. auto is not supported by old compilers.

The third function is the shorthand notation of the above two function. It says

for every element x of type int in vector v print the elements

also note that in all the above function I have passed the vector by reference so that it does not create a copy while passing the vector and I have also made it a const, which ensures that vector is not accidentally changed and compiler can also make some optimization in const type entities.

2D matrix using vectors

vector<vector<int>> matrix; // create a matrixvector<vector<int>> matrix(N, vector<int>(M, 0)); // create a N x M matrix and fill it with all 0

above are some basic operations on vector. But what if we want to insert multiple items multiple times and perform queries like lower_bound and upper_bound a number of times in such case we would have to sort the vector multiple times, so here set becomes perfect candidate to use.

Set

#include<set>

Set maintains elements sorted internally so we need not to call sort method again and again which will save O(NlogN) time at expense of (logN) time to maintain elements sorted internally by set.

set on pair

So now, we know that set maintains some order in elements but how does it compares ‘pair’ of elements to maintain order.

for two pairs {a, b} and {c, d} , {a, b} will be greater than {c, d} if (a > c) or (a == c and b > d)

Compiling all above points in set:

set stores element in ascending order(by default).
lower_bound gives the first element greater than or equal to some key.
for pair {a, b} and {c, d}, {a, b} == {c, d} if a == c && b == d and {a, b} < {c, d} if (a < c) || (a == c && b < d)

Maps

#include<map>

Maps map keys to value. What it means is that you can access value from their key.

Internally map is implemented as a Binary Search Tree(BST).

Unordered map

#include<unordered_map>

The unordered_map looks the same in functioning to map but there is a difference in how they are internally implemented.

Internally unordered_map is implemented as an array. Whatever key you give is passed into a hashing function and an index is generated by that hashing function, then the value is stored at that index of the array.

To learn more about hashing, check out this article.

Stack

#include<stack>

Stack is a last in first out data structure(LIFO), i.e the element that is last inserted is the first to come out. Imagine it like a pile of books.

Queue

#include<queue>

Queue is a first in first out(FIFO) data structure, i.e element first inserted is first to come out

List

#include<list>

List in c++ stl is implemented as a “doubly linked list”. It means that every element in the list keeps track of both the previous and next element.

Do not display list as in displayWrong method given below, use shorthand method or display like displayCorrect method.

What’s wrong in displayWrong method is that you cannot compare iterator for less than or greater than in case of non contiguous memory allocation data structures.
it < l.end() is wrong, it should be it != l.end()

Forward List

#include<forward_list>

Forward list implements “singly linked list”. That means is that every element in the list points to element next to it.

Priority queue

#include<queue>

A priority queue is a container that provides constant time extraction of the largest element, at the expense of logarithmic insertion. The internal implementation of priority_queue is binary-max-heap.

You can still implement binary-min-heap as follows:

priority_queue<Type, vector<Type>, comparator> min_heap;

Note that you cannot iterate on priority_queue, you have to get the top element and then pop to view all elements.

priority_queue finds their application in a number of standard algorithms like Dijkstra’s algorithm for shortest path.

Tuple and Tie

Here I have used watch macro to display variable content along with its name. This is a very popular macro, so you should start using it.

Bitset

Bitset in c++ stl makes it really easy to work with bits.

There are some problems in which you may find bitset very useful.

Syntax — bitset<size>

Reverse Bits - LeetCode

Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100Output…

leetcode.com

For more info visit gfg.

Algorithms

#include<algorithm>
#include<numeric>

Now let's have a look at some commonly used functions.

Above I have used macros to save a lot of my time and increase my productivity as a c++ programmer. If you want to learn more about increasing your productivity as a c++ programmer then check out this article.

Many times we want to perform operations on sets like union, intersection etc, these all operations are built into c++ stl library.

Remember that before applying these set operations, the vector must be sorted otherwise they will give unexpected results. So let's have a look at line #15

Here on the right side of the equal sign, we are creating a vector passing beginning (temp.begin()) and end iterator. This end iterator is returned by set_union.

Another use case is when finding permutations.

If you read uptill now, then I hope you liked this article and if you like this article then please Clap, as it motivates me to help the community.

Please comment if you found any discrepancy in this article or if you have any question related to this article.