Useful C++ libraries in Competitive Programming

C++ libraries in Competitive Programming
C++ libraries in Competitive Programming

In this tutorial, we will focus on some of the most important and popular libraries of C++ from the view of competitive programming and interview preparation. This will help you a lot in future for coding and programming.

Well, we know that C++ is the most common language recommended by competitive programmers or coders. In competitive programming, we have no time to make programs like sorting, map, searching etc. For these purposes, we use some of the very popular C++ libraries to make our code faster and also to save time. C++ STL (Standard Template Library) contains lots of containers which are useful for different purposes.

What is STL?
It’s a sophisticated and powerful library of template classes and template functions that implement many common data structures and algorithms and forms part of the C++ Standard Library.

Why should a C++ programmer be interested in the STL?
Because the STL embodies the concept of reusable software components and provides off-the-shelf solutions to a wide variety of programming problems. It is also extensible, in the sense that any programmer can write new software (containers and algorithms, for example), that “fit in” to the STL and work with the already-existing parts of the STL, provided the programmer follows the appropriate design guidelines.

Let’s discuss some of the popular and mostly used STL libraries during Coding: –

STACK: It is based on the LIFO order(Last In First Out), where we add new element on the top and removing of the element is also form that end. The functions we perform in stack are:- Empty(), Size(), Top(), Push(), Pop().

Syntax to implement Stack using STL:-

<include>stack

Using namespace std;
Int main() {
// Declare Stack Variable
Stack s;
// Insert Elements
s.push(X);

QUEUE: It works on the FIFO order(First In First Out), where we add an element in the last end and removing of the element is done from the top end. Examples of the queue are, level order traversal of a tree, BFS (Breadth-First Search) of a tree and its variations etc.

Syntax to implement Stack using STL :-

include<queue>

Using namespace std;
Int main() {
// Declare Queue Variable
queue q;
// Insert Elements
q.push(X);

Priority Queue: It is also a part of the queue but there is a slight difference that the first element of the queue is largest of all. Also, every element has its priority (Fixed Order). We can also implement it by the heap. By default, it takes the Max (Maximum)  Heap but we can also implement from Min (Minimum) Heap. It is used for solving very popular problems like prim’s algorithm, Huffman coding etc.

Syntax to implement priority_queue using STL:-

include<queue>

Using namespace std;
Int main() {
// Declare priority_queue Variable
Priority_queue g;
// Insert Elements
q.push(X);

DEQUEUE: It is another which supports the insertions and deletion from both ends in less time and space complexity. It is implemented from the array so it allows to random access of the elements. Same as vectors but more efficient than the vectors. One more interesting thing is that we can implement stack and queue with the help of dequeue. Some popular examples are the maximum of all subarray of size k.

Syntax to implement Stack using STL :-

include<dequeue>

Using namespace std;
Int main() {
// Declare dequeue Variable
queue gquiz;
// Insert Elements
gquiz.push_back(X);

SET: Sets are the type of associative containers in which every element is unique because the element is known by its value given to that. The value of the element can not be modified once it entered in the set, we can modify only by removing that element and then add to set. It is implemented through the balancing binary search tree. Used in such cases where we want to store elements in sorted order.

Syntax to implement Set using STL :-

include<set>

Using namespace std;
Int main() {
// Empty Set container
Set< int, greater > s1;
// Insert Elements
S1.insert(X);

MAP: It is also a type of associative containers in mapped functions. Each element has a key value and a mapped value associated with that. No two elements can have the same key value. It is implemented through the balancing binary search tree (basically Red Black Tree). It performs all the operations on time.

Syntax to implement Stack using STL :-

include<map>

Using namespace std;
Int main() {
// Declare Map Variable
Map gquiz;
// Insert Elements
gquiz.insert(pair ( X , Y));

UNORDERED_SET: It is implemented by the hash tables where the keys are hashed into indices of a hash table so that all the functions are randomized and takes only O(1) on average and O(n) in worst case. Used when to perform fast search, delete, insert. Most popular data structures in the industry and also in the competitive coding.

Syntax to implement Set using STL :-

include<set>

Using namespace std;
Int main() {
// Empty Set container
Unordered_set< string> uns1;
// Insert Elements
Stringset . insert(“X”);

UNORDERED_MAP: It is also implemented by the hashing with chaining. It stores the value in the pair of key-value and a mapped value. Both the value and key are pre-defined or user can also define these. It also takes O(1) complexity to perform all operations. Popular examples are union and intersection of the two sorted arrays, count distinct elements etc.

Syntax to implement Stack using STL :-

include<unordered_map>

Using namespace std;
Int main() {
// Declare Map Variable
Unordered_map unmap;
// Insert Elements
gquiz.insert(pair ( X , Y));

MULTISET: It is associative containers the same as the set, with an exception that multiple elements can have the same values means allows you to insert duplicate elements.

Syntax to implement Set using STL :-

include<set>

Using namespace std;
Int main() {
// Empty Set container
Set< int, greater > s1;
// Insert Elements
S1.insert(X);

VECTOR: It is same as a dynamic array with the resize itself automatically means when we insert the element in an array and if array will full then it will automatically be handled. They are placed in contiguous storage so that they can be accessed and traversed by iterators.

Syntax to implement Set using STL :-

include<vector>

Using namespace std;
Int main() {
// Empty Set container
Vector v1;
// Insert Elements
for (int i = 1; i <= 5; i++)
g1.push_back(i);

LIST:- List is sequence containers that allow non-contiguous memory allocation. As compared to vector it has slow traversal, but once the position has been found deletion and other functions will be quick. Normally when we say a list, we talk about the doubly linked list.

Syntax to implement Set using STL :-

include<list>

Using namespace std;
Int main() {
// Empty Set container
List alist , alist2;
// Insert Elements
list :: iterator it;
for(it = g.begin(); it != g.end(); ++it)
cout << ‘\t’ << *it;

PAIR: It is a simple container defined in <utility> header consisting of data elements or objects. The first element is referenced as ‘first’ and second element referenced as ‘second’ and the order is fixed. It provides us to give two heterogenous values in the pair. Pair can be assigned, copied and compared.  

Syntax to implement Set using STL :-

include<utility>

Using namespace std;
Int main() {
Pair < int , char > pair1;
// Insert Elements
PAIR1.first = 100;
PAIR1.second = ‘G’ ;

HEAP: It can be implemented by a wide range of STL which allows faster input into a heap and a number always results in largest number means the largest of remaining elements will popped out first. Numbers are arranged in descending order.

Syntax to implement Heap using STL :-

include<vector>

using namespace std;
int main()
{

// Initialising a vector 
vector<int> v1 = {20, 30, 40, 25, 15}; 

// Converting vector into a heap 
// using make_he ap() 
make_heap(v1.begin(), v1.end());

Note: We can use a header file which basically contains all the standard template libraries. During coding just use this and you are done approx all the STL libraries you can take. The header file is  #include < bits / stdc++ .h>. In programming contests, using this file is a good idea, when you want to reduce the time wasted in doing chores; especially when your rank is time-sensitive.

To read more about C++, click here.

By Akhil Sharma