Skip to main content

STL-2

 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;
}

Labels:

Comments

Post a Comment

Popular posts from this blog

NT Part 6: Sieve of Eratosthenes(Details)

  About 2300 years ago from today, famous Greek mathematician Euclid proved that there are an infinite number of prime numbers. Since then people have been searching for these prime numbers. In 1849, one of the greatest mathematician of all time, Carl Fredrick Gauss, had identified almost all of the prime numbers within the first 3 hundred thousand whole numbers. In the age of computers, we can find large prime numbers in the blink of an eye. But to do that, we need to know a bit of programming and a 2000 year old algorithm. By the end of this tutorial, you will be able to figure out a solution on your own to Gauss’s problem. What is a Prime Number? A prime number is an integer number that is divisible by 1 and the number itself only. For example, 7 is divisible by 1 and 7 only. But 6 is not a prime number because 6 is be divisible by 2 and 3 as well. It is worth mentioning that 1 itself is not a prime number. Now if you are asked to determine if a number is a prime number, you can...
Post a Comment
Read more

Binary Search & The Kahini!

  Suppose you are given an array of numbers and you need to find whether the number X is in the array. The straight forward approach to do that would be to run a loop and compare each number in the array with X. This is what the pseudo code would look like: function findNumber ( A , x ) for i = 0 to length of array A if A [ i ] == x return true return false For example, let’s assume you are given this array: [7, 14, 17, 21, 35, 60, 92, 121, 155] And, you were looking for the number 92. The loop would start checking each of the number in the array against 92 and would find after iterating through the array 7 times. The worst case time complexity of this approach would be O(n). However, whenever the array itself is in sorted order (like in this case where the numbers are increasing in value from left to right of the array), you can perform something that is much more efficient: binary search. The prerequisite of binary search is that the array should be sor...
Post a Comment
Read more

NT Part 3: Playing with Modulars, and Euler Phi Function

  Quick stuff first, fast exponentiation in logarithm time. Let us calculate   in modular   in  . It uses binary expansion of  ,  and is very very straightforward. ll exp ( ll x, ll n ) { if ( n == 0 ) return 1 ; if ( n == 1 ) return x ; if ( n % 2 == 0 ) return exp ( ( x * x ) % mod,n / 2 ) ; if ( n % 2 == 1 ) return ( x * exp ( ( x * x ) % mod,n / 2 ) ) % mod ; } Now, let us talk about modular inverses. By using Extended Euclidean Algorithm, we can get the inverse of   modulo  . #include <iostream> int inv ( int a, int m ) { int temp = m, q, t, u = 0 , v = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { q = a / m ; t = m ; m = a % m ; a = t ; t = u ; u = v - q * u ; v = t ; } if ( v < 0 ) v + = temp ; return v ; } int main ( void ) { int a, m ; std :: cin ...
Post a Comment
Read more