Queue
- <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.
Example
#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;
}
Fibonacci Series in C++
Stack
-
<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;
}
Sets
- <set>, <multiset>, <unordered_set>
Sets are associative containers in which each element is unique. The elements cannot be modified once inserted inset. 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;
}
Multiset
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
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
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
Multimap can have key-value pairs with 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;
}
Unordered Map
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
- <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;
}
Also, see Literals in C. Also see, Dynamic Binding in C++
Frequently Asked Questions
Is C++ good for competitive programming?
Yes, C++ is great for competitive programming. It has all the necessary tools and libraries which will help a programmer in his competitive programming journey.
Where can I learn C++ for competitive programming?
You can refer to free resources by CodeChef and Hackerrank online or you can take up a mentor led course such as that of Coding Ninjas wherein you’ll get the perfect guidance for all your needs.
Is STL allowed in competitive programming?
Yes it is. In addition to this, STL is preferred in competitive programming as the programmer does not have to worry about implementing a data structure and lose his time. He can completely focus on the problem at hand.
Should I use Java or C++ for competitive programming?
Java is considered to be easier while going for competitive programming however C++ has its own benefits. It doesn’t matter which language you are choosing, what matters is that you’re good in the basics.
Conclusion
In this article, we learned about important C++ libraries for Competitive Programming.
We hope that this blog has helped you enhance your knowledge regarding C++ libraries for Competitive Programming.
Check out these useful blogs on -
You can also consider our competitive programming course to give your career an edge over others!
Do upvote our blog to help other ninjas grow
Happy Reading!!