Standard Template Library

This article provides a comprehensive overview of Standard Template Library (STL) in C++ programming language along with example programs.

 

Introduction

The Standard Template Library (STL) is a collection of components to implement data structures and frequently used operations on data. Three major components in STL are:

1. Containers
2. Algorithms
3. Iterators

 

Containers

 

Container is an object that can:

• Store data.
• Define how the data can be stored and manipulated using operations.

 

Containers are similar to data structures and are implemented using templates. So, a container can store data of different types. Examples of containers are: Vector, List, Dequeue, Set, MultiSet, Map, MultiMap, Stack, Queue, PriorityQueue etc.

 

Containers are of three types:

1. Sequence Containers
2. Associative Containers
3. Derived Containers

 

Sequence Containers

 

Data is stored in a linear fashion. Each element is related to other elements by its position. Elements can be accessed using an iterator. Examples of sequence containers are: Vector, List, and Dequeue.

 

Vector: Dynamic array that allows insertion and deletion of elements at any position. Elements in a vector are contiguous. Allows direct access of an element. Defined in header file <vector>.

 

List: A bi-directional list that allows insertion and deletion of elements at any position. Elements in a list are not contiguous. Defined in header file <list>.

 

Dequeue: A double ended queue which allows insertion and deletion at both ends. Allows direct access of any element. Defined in header file <deque>.

 

Associative Containers

 

There is no sequential ordering of elements. Data is sorted while giving input. Supports direct access of elements using keys. Data is stored as a tree. They facilitate fast searching, insertion, and deletion. Not efficient for sorting and random access. Examples of associative containers are: Set, multiset, Map, and multimap.

 

Set and multiset: Store multiple elements and provide functions to manipulate them using their keys. A set does not allow duplicate elements. But a multiset allows duplicate elements. They are defined in the header file <set>.

 

Map and multimap: Stores the elements as pair of key and value. Key is used for indexing and sorting the values. Values can be manipulated using keys. Map does not allows multiple values for a key. But a multimap allows multiple values for a key. They are defined in the header file <map>. An example for multimap is dictionary.

 

Derived Containers

 

These containers are created from sequence containers. They don’t support iterators. As there are no iterators, data cannot be manipulated. Examples of derived containers are: Stack, Queue, and PriorityQueue.

 

Stack: Data is stored in Last In First Out (LIFO) order. Insertion and deletion of elements can be done only at one end.

 

Queue: Data is stored in First In First Out (FIFO) order. Insertion is done at one end and deletion is done at the other end.

 

PriorityQueue: The first element to be taken out is the element with highest priority.

 

Algorithms

 

The STL algorithms contains several functions that can be reused to perform several operations on the containers. Although each container provided basic functions to manipulate the data, STL provides around 60 algorithms (functions) which provided extended or complex functionality. These algorithms are categorized into five types as follows:

 

Retrieve or non-mutating algorithms

 

 

Mutating Algorithms

 

 

Sorting Algorithms

 

 

Set Algorithms

 

 

Relational Algorithms

 

 

Iterators

 

An iterator is an entity that allows programs to traverse the data in a container. Iterators are generally used to traverse the elements in a container. All containers except derived containers provides two types of containers:

 

container :: iterator (which provides a read/write iterator)

container :: const_iterator (which provides a read-only iterator)

 

STL provides five types of iterators as shown below for all containers except for derived containers.

 

 

All container classes provides four basic functions which can be used with the assignment operator. These functions are as follows:

 

begin() – Returns an iterator to the beginning of elements in the container.

cbegin() – Returns a read-only iterator to the beginning of elements in the container.

end() – Returns an iterator just past the end of the elements.

cend() – Returns a read-only iterator just past the end of the elements.

 

Vector

 

A vector is like a dynamic array where all the elements are stored contiguously. Elements can be added or removed at run-time as and when needed. Vector provides the following functions for working with the data stored in it:

 

 

Following program demonstrates working with a vector:

#include<iostream>
#include<vector>
using namespace std;
//print function to print the elements in the vector
void print(vector<int> &v)
{
	cout<<"Elements in the vector are: ";
	for(int i=0; i<v.size(); i++)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;
}
int main()
{
	vector<int> myvector;
	int num;
	cout<<"Enter 5 elements to store into vector: ";
	for(int i=0; i<5; i++)
	{
		cin>>num;
		myvector.push_back(num);  //inserts elements at the end
	}
	print(myvector);
	//Print the size (no. of elements) of vector
	cout<<"Size of vector is: "<<myvector.size()<<endl;
	//Print the capacity of vector
	cout<<"Capacity of vector is: "<<myvector.capacity()<<endl;
	//Get an iterator which points to the first element
	vector<int> :: iterator itr = myvector.begin();
	//Insert an element at index 2
	myvector.insert(itr+2, 8);
	cout<<"After inserting: "<<endl;
	print(myvector);
	//Delete an element at index 4
	myvector.erase(itr+4);
	cout<<"After deletion: "<<endl;
	print(myvector);
}

Input and output for the above program is as follows:

Enter 5 elements to store into vector: 1 4 6 9 2
Elements in the vector are: 1 4 6 9 2
Size of vector is: 5
Capacity of vector is: 8
After inserting:
Elements in the vector are: 1 4 8 6 9 2
After deletion:
Elements in the vector are: 1 4 8 6 2

 

List

 

A list (linked list) is a container in which an element points to next element and previous element. Direct access is not possible in a list. To reach nth element, we have to traverse all n-1 elements. The list container provides the following functions:

 

 

Following program demonstrates working with a list:

#include<iostream>
#include<list>
using namespace std;
//print function to print the elements in a list
void print(list<int> &tmplist)
{
	list<int> :: iterator itr;
	for(itr=tmplist.begin(); itr!=tmplist.end(); itr++)
	{
		cout<<*itr<<" ";
	}
	cout<<endl;
}
int main()
{
	list<int> list1;
	list<int> list2;
	int num;
	cout<<"Enter 5 numbers into list 1: ";
	for(int i=0; i<5; i++)
	{
		cin>>num;
		list1.push_back(num);	//inserts elements into list
	}
	cout<<"Enter 5 numbers into list 2: ";
	for(int i=0; i<5; i++)
	{
		cin>>num;
		list2.push_back(num);	//inserts elements into list
	}
	cout<<"Elements in list 1 are: ";
	print(list1);
	cout<<"Elements in list 2 are: ";
	print(list2);
	//Sorting list 1
	list1.sort();
	cout<<"After sorting, elements in list 1 are: ";
	print(list1);
	//Reversing list 2
	list2.reverse();
	cout<<"After reversing, elements in list 2 are: ";
	print(list2);
	//Merging two lists
	list1.merge(list2);
	cout<<"After merging list2 with list1, elements in list 1 are: ";
	print(list1);
	return 0;
}

Input and output for the above program is as follows:

Enter 5 numbers into list 1: 5 4 3 2 1
Enter 5 numbers into list 2: 6 7 8 9 10
Elements in list 1 are: 5 4 3 2 1
Elements in list 2 are: 6 7 8 9 10
After sorting, elements in list 1 are: 1 2 3 4 5
After reversing, elements in list 2 are: 10 9 8 7 6
After merging list2 with list1, elements in list 1 are: 1 2 3 4 5 10 9 8 7 6

 

Maps

 

A map is like an associative array where each element is made of a pair. A pair contains a key and a value. Key serves as an index. The entries in a map are automatically sorted based on key when data is entered. Map container provides the following functions:

 

 

Following program demonstrates working with a map:

#include<iostream>
#include<map>
using namespace std;
int main()
{
	map<string,int> STDcode;
	string area;
	int code;
	for(int i=1; i<=5; i++)
	{
		cout<<"Enter city: ";
		getline(cin, area);
		cout<<"Enter STD code: ";
		cin>>code;
		fflush(stdin);
		STDcode[area] = code;
	}
	STDcode["Chennai"] = 56;	//First way to insert
	STDcode.insert(pair<string,int>("Banglore",57));	//Second way to insert
	map<string,int> :: iterator itr;
	cout<<"Map entries are: "<<endl;
	//Printing map entries
	for(itr = STDcode.begin(); itr!=STDcode.end(); itr++)
	{
		cout<<(*itr).first<<", "<<(*itr).second<<endl;
	}
	return 0;
}

Input and output for the above program is as follows:

Enter city: Hyderabad
Enter STD code: 51
Enter city: Vizag
Enter STD code: 52
Enter city: Guntur
Enter STD code: 53
Enter city: Simla
Enter STD code: 54
Enter city: Goa
Enter STD code: 55
Map entries are:
Banglore, 57
Chennai, 56
Goa, 55
Guntur, 53
Hyderabad, 51
Simla, 54
Vizag, 52