The Standard Template Library: vector, set, map and Algorithms

Hello students, welcome to Kwickprep. Would you write your own sorting code for every program? Good programmers do not. C plus plus comes with a ready made toolbox called the Standard Template Library. Today we learn why it exists, vector and iterators, set, map and pair, and four famous algorithms: sort, find, count and binary search.

Why does the STL, the Standard Template Library, exist? Most programs store data, search it and sort it. Writing that code again in every program wastes time and invites bugs. The STL gives ready made tools, already tested by experts and fast. It is built with templates, so the same tool works for int, string or any type. And it is part of standard C plus plus, so it works with every modern compiler.

The STL has three main parts. Containers are objects that hold data, like vector, set and map. Iterators are like pointers that move through a container, using begin and end. Algorithms are ready made functions that work on the data, like sort, find and count.

A vector is like an array that can grow. To use it, include the header vector. Here runs is a vector of int holding two cricket scores, forty five and twelve. Push back adds seventy eight at the end, so the size becomes three. Runs at index two is seventy eight. So the output is three and seventy eight.

Here are the vector functions you will use most. Push back adds a value at the end. Pop back removes the last value. Size tells how many items the vector holds. Square brackets read an item by index, and the at function does the same but also checks that the index is valid. Best of all, a vector grows by itself, while a normal array has a fixed size.

An iterator is an object that points to one item in a container, like a finger moving along a list. Here the vector named m holds three marks. The loop starts at m dot begin, which points to the first item. It keeps going while the iterator is not equal to m dot end. Star i gives the value it points to, and i plus plus moves to the next item. So it prints seventy two, eighty five and sixty four.

Let us make iterators clear. Begin points to the first item. End points one step past the last item, not to the last item itself, so never read star end. Star gives the value at the current position. Plus plus moves the iterator to the next item. The keyword auto lets the compiler work out the long iterator type for you.

A set stores each value only once, and always keeps values in sorted order. Pause and predict. We put in thirty, ten, thirty and twenty. What is the size? The repeated thirty is dropped, and the rest are sorted. So it prints ten, twenty, thirty, and the size is three.

A pair joins two values, which can be of different types, into one object. Here the pair named p holds the name Riya and her marks, ninety two. The first value is reached with dot first. The second value is reached with dot second. So it prints Riya ninety two.

A map stores key and value pairs, like a canteen price list. The key is the item name, and the value is its price. Fee of Tea is ten rupees, and fee of Samosa is fifteen. Each entry inside a map is a pair. A map keeps its keys sorted, so Samosa comes before Tea. Finally, fee of Tea looks up the price, ten.

How do you choose? A set holds unique values, which suits a list of roll numbers with no repeats. A map links a key to a value, which suits an item name and its price. A pair holds exactly two values, which suits a student name with marks.

Now the algorithms, which need the header algorithm. Sort arranges items in ascending order. We pass two iterators, v dot begin and v dot end, to say sort the whole vector. The marks sixty four, twelve, eighty five and twelve become twelve, twelve, sixty four, eighty five.

Count tells how many times a value appears between two iterators. Pause and predict. How many times does twelve appear? Two times. So count prints two.

Find searches for a value and returns an iterator to its first match. Here it finds eighty five. Subtracting v dot begin from that iterator gives the index, which is two. If the value is not there, find returns v dot end, so always compare with end before using it.

Binary search only answers yes or no. It is found, or it is not. The data must already be sorted, or the answer can be wrong. Here the vector is sorted, and sixty four is present, so it prints one, meaning true. Searching for fifty would print zero. It is much faster than find on large sorted data, because it halves the search each step.

Some exams ask you to write the search yourself in pseudocode. This is a linear search, the same idea find uses. We set Found to false. The loop checks each mark from position one to four. If a mark equals eighty five, Found becomes true. At the end we output Found. Exam arrays in pseudocode often start at one, while C plus plus starts at zero.

Let us revise what we learned today. The STL gives ready made, tested containers and algorithms. A vector grows by itself, and iterators from begin to end walk through it. A set keeps unique values in sorted order, and a map links a key to a value. A pair holds two values, called first and second. Sort, find and count work on any range, but binary search needs sorted data. Try storing your class marks in a vector and sorting them.