# 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;intmain()

{

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

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

— Returns an iterator to the first element in the map**begin()**

— Returns an iterator to the theoretical element that follows last element in the map**end()**

— Returns the number of elements in the map**size()**

— Returns whether the map is empty**empty()**

— Adds a new element to the map**insert(pair<data_type1, data_type2> (key, value))**

— Removes the element at the position pointed by the iterator**erase(iterator position)**

— Removes the key value ‘g’ from the map**erase(const g)**

— Removes all the elements from the map**clear()**

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;intmain()

{

map<char,int> mp;

string s = "occurrence";for(inti = 0; i < s.length(); i++) {

mp[s[i]]++;

}

map<char,int> ::iteratorit;

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;

}return0;

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

— Returns an iterator to the first element in the set**begin()**

— Returns an iterator to the theoretical element that follows last element in the set**end()**

— Returns the number of elements in the set**size()**

— Returns whether the set is empty**empty()**

— Adds a new element ‘g’ to the set**insert(const g)**

— Removes the value ‘g’ from the set**erase(const g)**

— Removes all the elements from the set**clear()**

— Returns an iterator to the element ‘g’ in the set if found, else returns the iterator to end**find(const g)**

#include<iostream>

#include<set>

#include<iterator>using namespace std;intmain()

{

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> ::iteratorit;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;

}return0;

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

#include// Sort according to first element, if equal then check second

using namespace std;boolmyComp(pair<int,int>& a, pair<int,int>& b) {

if(a.first == b.first)

returna.second < b.second;

else

returna.first < b.first;

}intmain()

{

intarr[10] = {5, 1, 8, 4, 3, 7, 2, 9, 6, 0};

sort(arr, arr + 10); // starting pointer and ending pointercout<< "Array after sorting: ";

for(inti = 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(inti = 0; i < v.size(); i++)

cout<< v[i].first << " " << v[i].second <<endl;return0;

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

intarr[5] = {1, 4, 7, 10, 45};boolb =binary_search(arr, arr + 5, 23); // falseboolb1 =binary_search(arr, arr + 5, 10); // truevector<int> v(arr, arr + 5);boolb2 =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*

*.”*

intarr[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> ::iteratorl, 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.