STL — Standard Template Library [Part 2]

Hemakshi Sachdev
Sep 30, 2018 · 6 min read

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.

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 map
end() — Returns an iterator to the theoretical element that follows last element in the map
size() — Returns the number of elements in the map
empty() — Returns whether the map is empty
insert(pair<data_type1, data_type2> (key, value)) — Adds a new element to the map
erase(iterator position) — Removes the element at the position pointed by the iterator
erase(const g) — Removes the key value ‘g’ from the map
clear() — 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.

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 set
end() — Returns an iterator to the theoretical element that follows last element in the set
size() — Returns the number of elements in the set
empty() — Returns whether the set is empty
insert(const g) — Adds a new element ‘g’ to the set
erase(const g) — Removes the value ‘g’ from the set
clear() — Removes all the elements from the set
find(const g) — Returns an iterator to the element ‘g’ in the set if found, else returns the iterator to end

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

Reverse

It reverses any given array or string.

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.

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

It works for only sorted vectors. Many containers like sets and map have their on lower_bound and upper_bound member function.

Programming Club, NIT Raipur

This blog would contain guide, resources and experience on…

Hemakshi Sachdev

Written by

Competitive Programmer • Full-Stack Web Developer • Self-Improvement Enthusiast

Programming Club, NIT Raipur

This blog would contain guide, resources and experience on how to start competetive programming.

Hemakshi Sachdev

Written by

Competitive Programmer • Full-Stack Web Developer • Self-Improvement Enthusiast

Programming Club, NIT Raipur

This blog would contain guide, resources and experience on how to start competetive programming.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store