STL — Standard Template Library [Part 2]
In the previous post we discussed about some important and most widely used STLs like vector, string, stack, queue, etc.
Here we are going to take a step further on STLs and learn about pairs, map, sets and some in-built functions like sort, lower_bound, upper_bound and how we can tweak them according to our needs. So, let’s start with sets
Pairs
Pairs are simple containers to store two data elements together. The first element is referenced as first and the second as second. Pairs provide a way to store two heterogeneous values together as a single unit.
Library:- utility (#include <utility>)Declaration:- pair<data_type1, data_type2> p;
Pairs can be sometimes useful when we have to store the values of a vector and sort them, but also remember there previous index. So, the first value can be the array value and second it’s index. We can even have a vector of pairs.
#include <iostream>
#include <vector>
#include <utility> // Library to include pair
#include <string>
using namespace std;int main()
{
pair<int, string> p1;
p1.first = 5;
p1.second = "five";
cout << "Pair p1 is - " << p1.first <<" "<< p1.second << endl; pair<int, string> p2 (7, "seven");
cout << "Pair p2 is - " << p2.first <<" "<< p2.second << endl; vector<pair<int, int> > vec;
// make_pair is a member function which returns a pair without
// writing the data type explicitly.
vec.push_back(make_pair(5, 5));
cout << "Inserted pair - ";
cout << vec[0].first << " " << vec[0].second << endl; return 0;
}Output:-
Pair p1 is - 5 five
Pair p2 is - 7 seven
Inserted pair - 5 5
Maps
Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have same key values.
Library:- map (#include <map>)Declaration:- map<data_type1, data_type2> mp;
Here data_type1 is the data type of the key and data_type2 is the data type of the mapped value.
Some important and frequently used member functions of map are:-
begin() — Returns an iterator to the first element in the mapend() — Returns an iterator to the theoretical element that follows last element in the mapsize() — Returns the number of elements in the mapempty() — Returns whether the map is emptyinsert(pair<data_type1, data_type2> (key, value)) — Adds a new element to the maperase(iterator position) — Removes the element at the position pointed by the iteratorerase(const g) — Removes the key value ‘g’ from the mapclear() — Removes all the elements from the map
Let’s see how we can use maps to keep a count of the frequency of characters in a string.
#include <iostream>
#include <map>
#include <string>
#include <iterator>
using namespace std;int main()
{
map<char, int> mp;
string s = "occurrence"; for (int i = 0; i < s.length(); i++) {
mp[s[i]]++;
}
map<char, int> :: iterator it;
for (it = mp.begin(); it != mp.end(); it++) {
cout << it->first << " has " << it->second << " entries";
cout << endl;
} mp.insert(make_pair('s',1)); // Insertion
cout << "Size of Map is - " << mp.size() << endl; // Remove the key 'c' from map.
mp.erase('c'); cout << "Size of Map after removal - " << mp.size() << endl; mp.clear(); // Remove all the elements from map
if (mp.empty()) {
cout << "Map is empty" << endl;
} return 0;
}Output:-
c has 3 entries
e has 2 entries
n has 1 entries
o has 1 entries
r has 2 entries
u has 1 entries
Size of Map is - 7
Size of Map after removal is - 6
Map is empty
Sets
A set is a collection of distinct objects in sorted order. Each element is unique because it’s value identifies it. Thus, a value cannot be modified once it is added in the set, we can only remove and add them.
Library:- set (#include <set>)Declaration:- set<data_type> s;
Some common member functions are:-
begin() — Returns an iterator to the first element in the setend() — Returns an iterator to the theoretical element that follows last element in the setsize() — Returns the number of elements in the setempty() — Returns whether the set is emptyinsert(const g) — Adds a new element ‘g’ to the seterase(const g) — Removes the value ‘g’ from the setclear() — Removes all the elements from the setfind(const g) — Returns an iterator to the element ‘g’ in the set if found, else returns the iterator to end
#include <iostream>
#include <set>
#include <iterator>
using namespace std;int main()
{
set<int> s;
s.insert(10);
s.insert(50);
s.insert(40);
s.insert(20);
s.insert(30);
s.insert(50); // Only one 50 will be present in the set set<int> :: iterator it; cout << "Elements of Set s are: ";
for (it = s.begin(); it != s.end(); it++) {
cout << *it << " ";
} cout << "\nSize of the set s is: " << s.size() << endl; // Creating a set from elements of s in descending order
set<int, greater<int> > s2(s.begin(), s.end());
cout << "Elements of Set s2 are: ";
for (it = s2.begin(); it != s2.end(); it++) {
cout << *it << " ";
} // Remove the value 10 from set s.
s.erase(10); // Complexity of 'find' is O(logn)
if (s.find(10) == s.end()) {
cout << "\nElement 10 not present in the set s" << endl;
} return 0;
}Output:-
Elements of Set s are: 10 20 30 40 50
Size of the set s is: 5
Elements of Set s2 are: 50 40 30 20 10
Element 10 not present in the set s
The Algorithm Library
The algorithm library comes with a rich collection of very important in-built functions like sort, reverse, binary_search, lower_bound, upper_bound and much more!
Sort
As the name suggests, it sorts a given array or vector. We can also provide our own comparison function to sort as the third argument.
sort(start, end, myComp);
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;// Sort according to first element, if equal then check second
bool myComp(pair<int, int>& a, pair<int, int>& b) {
if (a.first == b.first)
return a.second < b.second;
else
return a.first < b.first;
}int main()
{
int arr[10] = {5, 1, 8, 4, 3, 7, 2, 9, 6, 0};
sort(arr, arr + 10); // starting pointer and ending pointer cout << "Array after sorting: ";
for (int i = 0; i < 10; i++)
cout<< arr[i] << " "; vector<pair<int, int> > v;
v.push_back(make_pair(4, 5));
v.push_back(make_pair(1, 3));
v.push_back(make_pair(2, 1));
v.push_back(make_pair(4, 4));
v.push_back(make_pair(3, 4)); sort(v.begin(), v.end(), myComp);
cout << "\nVector v after sorting: " << endl;
for (int i = 0; i < v.size(); i++)
cout << v[i].first << " " << v[i].second << endl; return 0;
}Output:-
Array after sorting: 0 1 2 3 4 5 6 7 8 9
Vector v after sorting:
1 3
2 1
3 4
4 4
4 5
Reverse
It reverses any given array or string.
string s = "Hello, world!"
reverse(s.begin(), s.end()); // s = !dlrow ,olleHint a[5] = {1, 5, 3, 9, 8};
reverse(a, a + 5); // a = {8, 9, 3, 5, 1}
Binary Search, Lower Bound & Upper Bound
Binary Search: It returns a boolean value, stating whether an element is present in the array/vector or not. The array/vector must be sorted.
int arr[5] = {1, 4, 7, 10, 45};
bool b = binary_search(arr, arr + 5, 23); // false
bool b1 = binary_search(arr, arr + 5, 10); // truevector<int> v(arr, arr + 5);
bool b2 = binary_search(v.begin(), v.end(), 4); // true
Lower Bound: Returns an iterator pointing to the first element in the range [first, last) which does not compare less than val.
It’s like saying, “Hey! I have a sorted array and a val, I want to know the position of the first element which is either equal to val or greater than it.”
Upper Bound: Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.
It’s like saying, “Hey! I have a sorted array and a val, I want to know the position of the first element which is greater than val.”
int arr[8] = {5, 2, 1, 3, 8, 8, 3, 4};
vector<int> v(arr, arr + 8);sort(v.begin(), v.end()); // 1 2 3 3 4 5 8 8
l u
vector<int> :: iterator l, u;
l = lower_bound(v.begin(), v.end(), 5); // Position=5, Element=5
u = upper_bound(v.begin(), v.end(), 5); // Position=6, Element=8
It works for only sorted vectors. Many containers like sets and map have their on lower_bound and upper_bound member function.
