Imagine a situation when you are giving an online competition of coding and there stuck a problem. In the last five minutes, you clicked the idea that the question implements a queue data structure. But you don’t have time to write the whole push, pop functions. So, now you are STUCK and you could not finish on time.
Here comes the most powerful weapon of competitive programming the STL libraries. The above problem statement could be done with the library “queue”. This library has all the inbuilt functions of queue data structure like pop, push, etc. Moreover, all these libraries are generic and can be implemented for any data type.
Below mentioned libraries are a major boon for Competitive Programming:
- <vector>: The major problem with c++ arrays is to resize. Vectors come with this beautiful feature to resize. It has more features like cache friendliness, no need to pass the size, can be returned from a function. It has rich library functions to access the elements. Further, the elements can be accessed with the help of loops and iterators. Vectors internally work as dynamically allocated arrays.
Header file: #include<vector>
Declaration: vector variable_name
Functions:
- push_back(): Pushes an element at the back of array in a serial manner.
- pop_back(): It pops the last element from a vector.
- front(): Returns the first element of a vector.
- back(): Returns the last element of a vector.
- size(): Returns the size of the vector.
- clear(): It deletes all elements in the vector.
- empty(): It returns a Boolean value after checking whether the vector is empty or not.
Convert an array to a vector:
int arr[] = {10, 5, 20};
int n = sizeof(arr)/ sizeof(arr[0]);
vector v(arr, arr+n); // It makes a vector of size n and array elements alike arr.
Example:
#include<vector>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
vector v;
v.push_back(10);
v.push_back(20);
v.push_back(30);
// iterator traversal
for(auto it = v.begin(); it != v.end(); it++)
cout << (*it) << “ “ ; // Outputs 10 20 30
// new way of vector initialisation
vector vi(5, 10); // Initialise a vector with size 5 and value 10 of whole vector.
return 0;
}
- <queue>: Queue uses a FIFO structure. This can be implemented using the queue class of STL.
Header file: #include
Declaration: queue variable_name
Functions:
- push(): Push elements to queue
- pop(): Pop elements from queue from the front.
- back(): Returns the last element of queue
- size(): Gives the size of the queue.
- front(): It gives the front element of the queue.
- last(): It gives the last element of the queue.
- empty(): It returns a Boolean value after checking whether a queue is empty or not.
Note – All these functions are O(1) time complexity. By default a queue is implemented by deque container.
#include<queue>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
queue q;
q.push(15);
q.push(25);
q.push(50);
q.push(30);
q.push(80);
// Queue traversal
while(q.empty() == false) // while queue is not empty
{
cout<< q.front() << “ “ << q.back();
q.pop(); // Pops the first element from queue
}
return 0;
}
- <stack>: This data structure uses a LIFO manner of inserting elements. Some problems like reversing an element or string, parenthesis check, print next greater element, postfix expression, etc, can be done using stack class rather than making all the functions we can use its inbuilt functions.
Header file: #include<stack>
Declaration: stack variable_name
Functions:
- push(): Push elements to stack on top
- pop(): Pop elements from queue from the top.
- size(): Gives the size of the stack
- empty(): Checks whether the stack is empty or not
- top(): It returns the top element of the stack
Example:
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
stack s;
s.push(1);
s.push(2);
s.push(3);
s.push(4);
s.push(5);
// Stack traversal
while(s.empty() == false) // while stack is not empty
{
cout<< s.top() << “ “ ; // Outputs – 5 4 3 2 1
s.pop(); // Pops the element from stack from top
}
return 0;
}
- <set>, <multiset>, <unordered_set>
Sets are associative containers in which each element is unique. The elements cannot be modified once inserted in set. A set ignores the duplicate values and all the elements are stored in sorted order.
Header file: #include<set>
Declaration: stack variable_name
Functions:
- insert(): This function is used to insert a new element in the Set.
- begin(): This function returns an iterator to the first element in the set.
- end(): It returns an iterator to the theoretical element that follows the last element in the set.
- size(): Returns the total size of the set.
- find(): It returns an iterator to the searched element if present. If not, it gives an iterator to the end.
- count(): Returns the count of occurrences in a set. 1 if present, else 0.
Example:
#include<set>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
set s;
s.insert(10);
s.insert(20);
s.insert(30);
s.insert(40);
s.insert(50);
// Set traversal
for(auto it = s.begin(); it != s.end(); it++)
cout << (*it) << “ “ ;
// find function
auto it = s.find(30); // checks If 30 is present or not in set
if ( it == s.end()) // i.e, if not present then it will give end iterator
cout << “ Not present “ ;
else
cout << “ present “ ;
return 0;
}
A multiset is similar to set but internally it implements a red-black tree, which does insertion, deletion in log(n) time. Unlike a set, multiset can have duplicate values. All of them are stored in sorted order. Most functions of sets work for multiset. Some functions like erase(), count(), lower_bound(), upper_bound() work differently.
Header file: #include<multiset>
Declaration: multiset variable_name
Example:
#include<multiset>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
multiset s;
s.insert(10);
s.insert(20);
s.insert(10);
s.insert(40);
s.insert(40);
// MultiSet traversal
for(auto x : s)
cout << x << “ “ ; // Outputs 10 10 20 40 40
returns 0;
}
unordered_set internally uses a hash table. When compared to sets the elements in sets are arranged in sorted order but not in an unordered set. The functions like insert(), delete(), takes log(n) time in set whereas, it takes O(1) in unordered_set.
The unordered set can output the elements in any order depending on compilers. Rest functions are the same as a set. Complex problems like a union of two arrays(unsorted), check for a pair sum, candies distribution can be done with the help of this library.
Header file: #include<unordered_set>
Declaration: unordered_set variable_name
Example:
#include<unordered_set>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
unordered_set s;
s.insert(10);
s.insert(5);
s.insert(15);
s.insert(20);
s.insert(40);
// unordered set traversal
for(auto x : s)
cout << x << “ “ ; // Outputs 10 15 40 20 5
returns 0;
}
<map>, <multimap>, <unordered_map>
Map stores the elements in the form of a key-value pair. The pair is increasing in order by default. We can change it by using our own comparison function. Internally, it uses a red-black tree for storing elements. The map does not contain any duplicates. Some functions are find(), insert(), count(), lower_bound(), upper_bound(), etc.
Header file: #include<map>
Declaration: map variable_name
Example:
include<map>
using namespace std;
int main()
{
map mp;
mp.insert({10, 200});
mp[5]= 100; // Another way of inserting elements
// map traversal
for(auto &x : mp)
cout<< x.first << “ “ << x.second << endl; // first refers to the // key and second refer to the value
return 0;
}
Multimap can have key-value pairs with the multiple same keys. Rather than each element is unique, the key-value and mapped value pair have to be unique in this case. We can implement a dictionary using multimap.
Note: Inserting values by [] is not allowed in multimap.
Header file: #include<map>
Declaration: map variable_name
Example:
#include<map>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
multimap mp;
mp.insert({10, 20});
mp.insert({10, 30});
mp.insert({25, 100});
for(auto x : mp)
cout << x.first << “ “ << x.second << endl;
return 0;
}
The unordered_map is an associated container that stores elements formed by a combination of key-value pairs. The key value is used to uniquely identify the element and mapped value is the content associated with the key. Both key and value can be of any type of predefined or user-defined.
Internally unordered_map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O(1).
Header file: #include<map>
Declaration: unordered_map variable_name
Example:
#include<map>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
unordered_map mp;
mp.insert({10, 20});
mp.insert({15, 30});
mp[20]= 70;// another way
mp.insert({25, 100});
for(auto x : mp)
cout << x.first << “ “ << x.second << endl;
return 0;
}
- <priority_queue>: This implements heap data structure. By default, a max heap is built. Functions are push(), pop(), size(), empty() , top() which work as explained above.
Header file: #include
Declaration:
1) For max heap
priority_queue variable_name
2) For min heap
priority_queue,greater> variable_name
Complex problems like finding k largest or smallest elements, merge k unsorted arrays, etc. can be implemented easily.
Example:
#include<queue>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
priority_queue pq;
pq.push(10);
pq.push(15);
pq.push(5);
cout << pq.size(); // 3
cout << pq.top(); // 15 as by default it’s a max heap
// Traversal
while(pq.empty() == false)
{
cout << pq.top() << “ “ ; // 15 10 5
pq.pop();
}
return 0;
}
Comments
Post a Comment