Day 13 | Standard Template Library (STL) | C++

You should try out these questions by yourself.

1. Cupboards | C++ Implementation

2. I_love_%username% | C++ Implementation

3. Tram | C++ Implementation

4. Pashmak and Flowers | C++ Implementation

Today instead of questions, we will be discussing one of the very important C++ concepts used in competitive programming.

Standard Template Library

The standard template library is one of the most important libraries in C++. It comprises a collection of various containers which are very efficient and will be helpful in the future when we will directly use implementation from STL library rather than re-implementing it ourselves.

I would like to give you all a glimpse of what STL can do. You do not need to remember all this, we will face questions in the future where we will be using them tons of times and thus revising them.

What header to include?

For competitive programming sites, you can directly use the following header which includes the majority of common STL files in g++ compilers.

#include<bits/stdc++.h>

Mac users can face issues including this header. You can do this to create the header

Note: Each container has a huge set of operations that can be done on them. I will be editing this blog as I keep using different things in problems.

Vector

vector is a linear container. It is similar to the array if explained in layman's terms but has the ability to increase/decrease size on demand.

Creating a vector

vector<int> A = {1,2,3,4}; // Way 1 to create a vector
vector<int> B; //Create an empty B vector
vector<int> C(10); Creates a vector of size 10 with all values to be 0
vector<int> D(10, 5); Creates a vector of size 10 with all values to be 5

Inserting into vector

A.push_back(10); // Inserts value 10 into array

Accessing ith element in a vector

cout << A[i]; // Print ith value in the vector

Sets

Sets are very advanced data structures if implemented from scratch. In layman's terms, they keep your data in sorted order. Actually, they do not keep your data in sorted order but themselves are implementing Binary Search Trees, which when traversed in order give sorted results.

Creating a set

set<int> s;

Inserting into set

s.insert(10); // Inserts value 10 into set

Accessing ith element in a set

You cannot ith element in set 

Printing all values in the set

for(int i : s) cout << i << " ";

Note: Sets do not contain duplicates of data so if we insert 1,2,3,4,3,5. Then output will be 1,2,3,4,5.

Maps

Maps are the storage of key-value pairs. They are also implementation of Binary Search Tree thus are sorted in order of keys

Creating a map

map<int,int> m;

Setting the value of key k = value v

m[k] = v;

Accessing value for pair with key = k

cout << m[k]; // Prints v

Printing all key-value pairs

for(pair<int,int> x : m) cout << x.first << " " << x.second << "\n";