Standard Template Library

1. Introduction to Standard Template Library

One of the succeeding editions to the C++ standard is the Standard Template Library. STL is an acronym for standard template library. STL contains C++ library of container classes, iterators, and algorithms. It is a set of C++ template classes that provide generic classes and function that can be used in the implementation of data structures and algorithms.

Standard Template Library is composed of the following libraries.

  1. Algorithms library
  2. Containers library
  3. Iterators library

2. Containers in STL

A container is a holder object that is used to hold a different kind of objects or elements which are dynamic in nature. STL containers are implemented as a class template and allow a flexibility in the types supported as elements.

STL containers can be divided into two broad categories, sequence, associative containers, unordered associative containers and containers adaptors.

2.1 Sequence Containers

Sequences containers control the order of elements or objects. The vectors, list, deque are all sequence containers in STL.

2.2 Associative Containers

In Associative containers, the container is responsible for controlling the position of elements within it. The elements of the associative containers can be accessed using a key. The container controls the position of elements within it. Set, multiset, map, multimap are all examples of associative containers in STL.

2.3 Unordered Associative Containers

Unordered associative containers are used to implement unsorted data structures.

2.4 Containers Adaptors

Containers adaptors are used to provide different interface to the Sequence containers. These are based on deque by default. Stack, queue, priority queue are some examples of Containers adaptors in STL.

Let us now discuss some common containers in the next section.

3. Common Containers in STL

Below we have listed and explained some of the common containers in STL.

3.1 Vectors

3.1.1 Introduction to Vectors

Vectors are dynamic sequence containers in STL representing array data structure that can grow and diminish in size. Vectors use contiguous storage locations just like arrays for the elements. Vectors have an advantage over arrays that the size of the container can be changed dynamically.

Elements can be added or removed at a constant time at the end or beginning of a vector. In the same way elements, can be added or removed in a linear time in the middle of a vector. Vector data structure provides automatic memory management i.e. there is no need to specify the number of elements.

3.1.2 Operations on Vectors

PROGRAM:

#include < iostream>
#include < vector>
using namespace std;
int main() {
// creating a vector data type
vector< int> vec; 
int i;
// Printing size of vector
cout << "The Size of Vector is = " << vec.size() << endl;
// Inserting 5 values into the vector
for(i = 0; i < 5; i++){
vec.push_back(i);
}
// Printing extended size of vec
cout << "extended vector size = " << vec.size() << endl;
// Printing 5 values from the vector
for(i = 0; i < 5; i++){
cout << "value of vec [" << i << "] = " << vec[i] << endl;
}
// Using iterator to access the values
vector< int>::iterator v = vec.begin();
while( v != vec.end()) {
cout << "value of v = " << *v << endl;
v++;
}
return 0; }

3.2 List

3.2.1 Introduction to List

Lists come under sequence containers and allow constant time insert and remove operations anywhere within the sequence. It can be iterated in both the directions.

List containers in STL are implemented as doubly-linked lists. List perform generally better in insertion, extraction, and relocation of elements in any position within the container as compared to other standard sequence containers like an array, vector, and deque. The main drawback of lists is that they lack direct access to the elements by their position and takes linear time in the distance.

3.2.2 Operations on List

PROGRAM:

#include < iostream>
#include < list>
int main ()
{
// defining constructors
std::list< int> first;                                // empty list of ints
std::list< int> second (4,100);                       // four ints with value 100
std::list< int> third (second.begin(),second.end());  // iterating through second
std::list< int> fourth (third);                       // a copy of third

// Using iterator constructor to construct from arrays:
int myints[] = {16,2,77,29};
std::list< int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

std::cout << "The contents of fifth are: ";
for (std::list< int>::iterator it = fifth.begin(); it != fifth.end(); it++)
std::cout << *it << ' ';
std::cout << '\n';
return 0;  }

3.3 Deque

3.3.1 Introduction to Deque

Deque known as a double-ended queue is an ordered collection of items in Data Structures. It is also often called a head tail linked list. What makes a deque stand out is the unrestrictive nature of adding and removing items i.e. it allows fast insertion and deletion of elements at both ends of the queue.

Deque and vectors inhibit the same functionality, but deque provides efficient insertion and deletion of elements at the beginning of the sequence as well and not only at the end. But, unlike vectors, deques do not guarantee to store all its elements in contiguous storage locations.

3.3.2 Operations on Deque

PROGRAM:

#include< iostream>
#include< conio.h>
#include< stdlib.h>
using namespace std;
 
class node
{
public:
int data;
class  node *next;
class node *prev;
};
 
class dqueue: public node
{
node *head,*tail;
int top1,top2;
public:
dqueue()
{
top1=0;
top2=0;
head=NULL;
tail=NULL;
}
void push(int x){
node *temp;
int ch;
if(top1+top2 >=5)
{
cout <<"dqueue overflow";
return ;
}
if( top1+top2 == 0)
{
head = new node;
head->data=x;
head->next=NULL;
head->prev=NULL;
tail=head;
top1++;
}
else
{
cout <<" Add element 1.FIRST 2.LAST\n enter ur choice:";
cin >> ch;
 
if(ch==1)
{
top1++;
temp=new node;
temp->data=x;
temp->next=head; 
temp->prev=NULL;
head->prev=temp;
head=temp;
}
else
{
top2++;
temp=new node;
temp->data=x;
temp->next=NULL;
temp->prev=tail;
tail->next=temp;
tail=temp;
}
}
}
void pop()
{
int ch;
cout <<"Delete 1.First Node 2.Last Node\n Enter ur choice:";
cin >>ch;
if(top1 + top2 <=0)
{
cout <<"\nDqueue under flow";
return;
}
if(ch==1)
{
head=head->next;
head->prev=NULL;
top1--;
}
else
{
top2--;
tail=tail->prev;
tail->next=NULL;
}
}
void display()
{
int ch;
node *temp;
cout <<"display from 1.Staring 2.Ending\n Enter ur choice";
cin >>ch;
if(top1+top2 <=0)
{
cout <<"under flow";
return ;
}
if (ch==1)
{
temp=head;
while(temp!=NULL)
{
cout << temp->data <<" ";
temp=temp->next;
}
}
else
{
temp=tail;
while( temp!=NULL) 
{
cout << temp->data << " ";
temp=temp->prev;
}
}
}
};
 
main()
{
dqueue d1;
int ch;
while (1){
cout <<"1.INSERT  2.DELETE  3.DISPLAU  4.EXIT\n Enter ur choice:";
cin >>ch; 
switch(ch)
{
case 1: cout <<"enter element";
cin >> ch;
d1.push(ch); break;
case 2: d1.pop(); break;
case 3: d1.display(); break;
case 4: exit(1);
}  }}

3.4 Set

3.4.1 Introduction to Set

Sets are associative containers type in STL which store unique elements following a certain order. In a set, the value of an element is itself the key, of type T and each value must be unique. The value of the elements in the set container cannot be manipulated but the insert and remove operations can be performed on the values of the container.

Set containers are generally slower as compared to Unordered Set containers in case of accessing individual elements by their key. But they allow the direct iteration on subsets based on the order.

Sets can be implemented as binary search trees.

3.4.2 Operations on set

PROGRAM:

#include < iostream>
#include < set>
#include < iterator>
 using namespace std;
int main()
{
set < int, greater < int> > gquiz1;        
gquiz1.insert(40);
gquiz1.insert(30);
gquiz1.insert(60);
gquiz1.insert(20);
gquiz1.insert(50);
gquiz1.insert(50); 
gquiz1.insert(10);
 
// Printing set values
set < int, greater < int> > :: iterator itr;
cout << "\nThe set gquiz1 is : ";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr)
{
cout << '\t' << *itr;
}
cout << endl;
set < int> gquiz2(gquiz1.begin(), gquiz1.end());
cout << "\nThe set gquiz2 after assign from gquiz1 is : ";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << *itr;
}
cout << endl;
cout << "\ngquiz2 after removal of elements less than 30 : ";
gquiz2.erase(gquiz2.begin(), gquiz2.find(30));
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << *itr;
}
int num;
num = gquiz2.erase (50);
cout << "\ngquiz2.erase(50) : ";
cout << num << " removed \t" ;
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr)
{
cout << '\t' << *itr;
}
cout << endl;
cout << "gquiz1.lower_bound(40) : "
<< *gquiz1.lower_bound(40) << endl;
cout << "gquiz1.upper_bound(40) : "
<< *gquiz1.upper_bound(40) << endl;
//lower bound and upper bound for set gquiz2
cout << "gquiz2.lower_bound(40) : "
<< *gquiz2.lower_bound(40) << endl;
cout << "gquiz2.upper_bound(40) : "
<< *gquiz2.upper_bound(40) << endl;
return 0;

3.5 Stack

3.5.1 Introduction to Stack

Stacks comes under Container Adaptor in STL containers. The stack is designed to work in a Last in First Out context. In LIFO, elements are added and removed from one end of the container only.

In Stack, data structure elements are pushed and popped from the end of the container, which can be also called as the top of the stack.

3.5.2 Operations on Stack

PROGRAM:

#include< iostream>
#include< conio.h>
#include< stdlib.h>
using namespace std;
class stack
{
int stk[5];
int top;
public:
stack()
{
top=-1;
}
void push(int x)
{
if(top >  4)
{
cout <<"stack over flow";
return;
}
stk[++top]=x;
cout <<"inserted" << x;
}
void pop()
{
if(top <0)
{
cout <<"stack under flow";
return;
}
cout <<"deleted" << stk[top--];
}
void display()
{
if(top<0)
{
cout <<" stack empty";
return;
}
for(int i=top;i>=0;i--)
cout << stk[i] <<" ";
}
};
 
main()
{
int ch;
stack st;
while(1)
{
cout <<"\n1.push  2.pop  3.display  4.exit\nEnter ur choice";
cin >> ch;
switch(ch)
{
case 1:  cout <<"enter the element";
cin >> ch;
st.push(ch);
break;
case 2:  st.pop();  break;
case 3:  st.display();break;
case 4:  exit(0);
}
}
return (0);
}

3.6 Queue

3.6.1 Introduction to Queue

Queues also come under Container Adaptor in STL containers. This data structure is designed to operate in a First in First Out context. Here elements or objects are added to one end of the container and removed from the other.

Objects or elements are pushed into the back of the container and popped from its front in the Queue data structure.

3.6.2 Operations on Queue

PROGRAM:

#include< iostream.h>
#include< conio.h>
class queue
{
public:
int q[5],front,rear,x,result;
void enq();
void dque();
void disp();
queue()
{
front=0;
rear=0;
}
};
void queue::enq()
{
if(rear>=5)
cout<<"\nOverflow!!\n";
else
{
cout<<"\n number to be inserted: ";
cin>>x;
rear++;
q[rear]=x;
cout<<"\nNumber pushed in the queue:"<< q[rear];
}
}
void queue::dque()
{
if(rear==0)
cout<<"\nUnderflow!!\n";
else
{
if(front==rear)
{
front=0;
rear=0;
}
else
front++;
}
cout<<"\nDeleted element is:";
result=q[front];
cout<< result;
}
void queue::disp()
{
if(rear==0)
cout<<"\nUnderflow!!\n";
else
cout<<"\nPrinting Contents of queue:";
for(int i=front+1;i<=rear;i++)
cout<< q[i]<<"\t";
}
void main()
{
int c;
queue qu;
clrscr();
//  cout<<"\n*****";
//  cout<<"\nQUEUE";
//  cout<<"\n*****";
do
{
cout<<"\n1.Insertion\n2.Deletion\n3.Display\n";
cout<<"\nEnter your choice:";
cin>>c;
switch(c)
{
case 1:
qu.enq();
break;
case 2:
qu.dque();
break;
case 3:
qu.disp();
break;
default:
cout<<"\nInvalid choice!!\n";
}
}
while(c<4);
getch();
}

3.7 Priority Queue

3.7.1 Introduction to Priority Queue

Priority Queue also comes under Container Adaptor and provides constant time lookup of the largest element. But it does so at the expense of logarithmic insertion and extraction. Working with a Priority Queue is similar to working with a heap in the context of some random-access container. It provides the benefit of not being able to accidentally invalidate the heap.

3.7.2 Operations on Priority Queue

PROGRAM:

#include< iostream.h>
#include< conio.h>

const int MAX=5;

class pqueue
{
int front,rear;
public:
struct data
{
int val,p,o;
}d[MAX];
pqueue()
{
front=rear=-1;
}
void insert(data d1);
data deletion();
void display();
};
void pqueue :: insert(data d1)
{
if(rear==MAX-1)
cout<<"The Queue is Full
";
else
{
rear++;
d[rear]=d1;
if(front==-1)
front=0;
data temp;
for(int i=front;i<=rear;i++)
for(int j=i+1;j<=rear;j++)
{
if(d[i].p > d[j].p)
{
temp=d[i];
d[i]=d[j];
d[j]=temp;
}
else
{
if(d[i].p==d[j].p)
{
if(d[i].o > d[j].o)
{
temp=d[i];
d[i]=d[j];
d[j]=temp;
}
}
}
}
}
}
data pqueue :: deletion()
{
data d1;
if(front==-1)
cout<<"The Queue is Empty
";
else
{
d1=d[front];
if(front==rear)
front=rear=-1;
else
front++;
}
return d1;
}
void pqueue :: display()
{
if(front==-1)
cout<<"The Queue is Empty
";
else
{
for(int i=front;i<=rear;i++)
{
cout<<"Object  :"<< i+1<< endl;
cout<<"Value ="<< d[i].val<< endl;
cout<<"Priority="<< d[i].p<< endl;
cout<< "Order =  "<< d[i].o<< endl;
}
}
}
void main()
{
pqueue p1;

data d1;
char op;
do
{
int ch;

clrscr();
		
";
cout<<"1.Insert
2.Delete
3.Print
4.Exit
";
cout<<"Enter Choice<1..4> ?";
cin>>ch;
switch(ch)
{
case 1 : cout<<"Enter Value ?";
cin>>d1.val;
cout<<"Enter Priority";
cin>>d1.p;
cout<<"Enter Order";
cin>>d1.o;
p1.insert(d1);
break;
case 2 :  d1=p1.deletion();
cout<<"Value = "<< d1.val<< endl;
cout<<"Priority = "<< d1.p<< endl;
cout<<"Order ="<< d1.o<< endl;
break;
case 3 :  p1.display();
break;
}
cout<<"Do You Want to Continue Y/N?";
cin>>op;
}while(op=='Y' || op=='y');
getch();
}