Standard Template Library

<div>

<h1>Standard Template Library</h1>

<h2>1. Introduction to Standard Template Library</h2>

<p>One of the succeeding editions to the C++ standard is the <strong>Standard Template Library</strong>. 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.</p>

<p>Standard Template Library is composed of the following libraries.</p>

<ol>

<li>Algorithms library</li>

<li>Containers library</li>

<li>Iterators library</li>

</ol>

<h2>2. Containers in STL</h2>

<p>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.</p>

<p>STL containers can be divided into two broad categories, <strong>sequence, associative containers, unordered associative containers and containers adaptors.</strong></p>

<h3>2.1 Sequence Containers</h3>

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

<h3>2.2 Associative Containers</h3>

<p>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.</p>

<h3>2.3 Unordered Associative Containers </h3>

<p>Unordered associative containers are used to implement unsorted data structures.</p>

<h3>2.4 Containers Adaptors</h3>

<p>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.</p>

<p>Let us now discuss some common containers in the next section.</p>

<h2>3. Common Containers in STL</h2>

<p>Below we have listed and explained some of the common containers in STL.</p>

<h3>3.1 Vectors</h3>

<h4>3.1.1 Introduction to Vectors</h4>

<p>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.</p>

<p>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.</p>

<h4>3.1.2 Operations on Vectors</h4>

<p><strong>PROGRAM:</strong></p>

<pre>

#include < iostream>

#include < vector>

using namespace std;

int main()

// creating a vector data type

vector<int>vec;

inti;

// 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>::iteratorv=vec.begin();

while( v != vec.end())

cout << "value of v = " << *v << endl;

v++;

return0;

</pre>

<h4>3.2.1IntroductiontoList</h4>

<p>Listscomeundersequencecontainersandallowconstanttimeinsertandremoveoperationsanywherewithinthesequence. Itcanbeiteratedinboththedirections.</p>

<p>ListcontainersinSTLareimplementedasdoubly-linkedlists. Listperformgenerallybetterininsertion, extraction, andrelocationofelementsinanypositionwithinthecontainerascomparedtootherstandardsequencecontainerslikeanarray, vector, anddeque. Themaindrawbackoflistsisthattheylackdirectaccesstotheelementsbytheirpositionandtakeslineartimeinthedistance.</p>

<h4>3.2.2OperationsonList</h4>

<p><strong>PROGRAM:</strong></p>

<pre>

#include < iostream>

#include < list>

intmain ()

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

intmyints[] = 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>::iteratorit=fifth.begin(); it != fifth.end(); it++)

std::cout << *it << '';

std::cout << '\n';

return0;

</pre>

<h3>3.3Deque</h3>

<h4>3.3.1IntroductiontoDeque</h4>

<p>Dequeknownasadouble-endedqueueisanorderedcollectionofitemsinDataStructures. Itisalsooftencalledaheadtaillinkedlist. Whatmakesadequestandoutistheunrestrictivenatureofaddingandremovingitemsi.e. itallowsfastinsertionanddeletionofelementsatbothendsofthequeue.</p>

<p>Dequeandvectorsinhibitthesamefunctionality, butdequeprovidesefficientinsertionanddeletionofelementsatthebeginningofthesequenceaswellandnotonlyattheend. But, unlikevectors, dequesdonotguaranteetostoreallitselementsincontiguousstoragelocations.</p>

<h4>3.3.2OperationsonDeque</h4>

<p><strong>PROGRAM:</strong></p>

<pre>

#include< iostream>

#include< conio.h>

#include< stdlib.h>

usingnamespacestd;

classnode

public:

intdata;

classnode *next;

classnode *prev;

;

classdqueue:publicnode

node *head,*tail;

inttop1,top2;

public:

dqueue()

top1=0;

top2=0;

head=NULL;

tail=NULL;

voidpush(intx)

node*temp;

intch;

if(top1+top2>=5)

cout<<"dqueue overflow";

return ;

if( top1+top2==0)

head=newnode;

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=newnode;

temp->data=x;

temp->next=head;

temp->prev=NULL;

head->prev=temp;

head=temp;

else

top2++;

temp=newnode;

temp->data=x;

temp->next=NULL;

temp->prev=tail;

tail->next=temp;

tail=temp;

voidpop()

intch;

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;

voiddisplay()

intch;

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

dqueued1;

intch;

while (1)

cout<<"1.INSERT 2.DELETE 3.DISPLAU 4.EXIT\n Enter ur choice:";

cin>>ch;

switch(ch)

case1: cout<<"enter element";

cin>>ch;

d1.push(ch); break;

case2: d1.pop(); break;

case3: d1.display(); break;

case4: exit(1);

</pre>

<h4>3.4.1IntroductiontoSet</h4>

<p>SetsareassociativecontainerstypeinSTLwhichstoreuniqueelementsfollowingacertainorder. Inaset, thevalueofanelementisitselfthekey, oftypeTandeachvaluemustbeunique. Thevalueoftheelementsinthesetcontainercannotbemanipulatedbuttheinsertandremoveoperationscanbeperformedonthevaluesofthecontainer.</p>

<p>SetcontainersaregenerallyslowerascomparedtoUnorderedSetcontainersincaseofaccessingindividualelementsbytheirkey. Buttheyallowthedirectiterationonsubsetsbasedontheorder.</p>

<p>Setscanbeimplementedasbinarysearchtrees.</p>

<h4>3.4.2Operationsonset</h4>

<p><strong>PROGRAM:</strong></p>

<pre>

#include < iostream>

#include < set>

#include < iterator>

usingnamespacestd;

intmain()

set < int, greater < int> > gquiz1;

gquiz1.insert(40);

gquiz1.insert(30);

gquiz1.insert(60);

gquiz1.insert(20);

gquiz1.insert(50);

gquiz1.insert(10);

// Printing set values

set < int, greater < int> > ::iteratoritr;

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;

intnum;

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;

return0;

</pre>

<h3>3.5Stack</h3>

<h4>3.5.1IntroductiontoStack</h4>

<p>StackscomesunderContainerAdaptorinSTLcontainers. ThestackisdesignedtoworkinaLastinFirstOutcontext. InLIFO, elementsareaddedandremovedfromoneendofthecontaineronly.</p>

<p>InStack, datastructureelementsarepushedandpoppedfromtheendofthecontainer, whichcanbealsocalledasthetopofthestack.</p>

<h4>3.5.2OperationsonStack</h4>

<p><strong>PROGRAM:</strong></p>

<pre>

#include< iostream>

#include< conio.h>

#include< stdlib.h>

usingnamespacestd;

classstack

intstk[5];

inttop;

public:

stack()

top=-1;

voidpush(intx)

if(top > 4)

cout <<"stack over flow";

return;

stk[++top]=x;

cout <<"inserted" << x;

voidpop()

if(top <0)

cout <<"stack under flow";

return;

cout <<"deleted" << stk[top--];

voiddisplay()

if(top<0)

cout <<" stack empty";

return;

for(inti=top;i>=0;i--)

cout << stk[i] <<"";

;

main()

intch;

stackst;

while(1)

cout <<"\n1.push 2.pop 3.display 4.exit\nEnter ur choice";

cin >> ch;

switch(ch)

case1:cout <<"enter the element";

cin >> ch;

st.push(ch);

break;

case2:st.pop(); break;

case3:st.display();break;

case4:exit(0);

return (0);

</pre>

<h3>3.6Queue</h3>

<h4>3.6.1IntroductiontoQueue</h4>

<p>QueuesalsocomeunderContainerAdaptorinSTLcontainers. ThisdatastructureisdesignedtooperateinaFirstinFirstOutcontext. Hereelementsorobjectsareaddedtooneendofthecontainerandremovedfromtheother.</p>

<p>ObjectsorelementsarepushedintothebackofthecontainerandpoppedfromitsfrontintheQueuedatastructure.</p>

<h4>3.6.2OperationsonQueue</h4>

<p><strong>PROGRAM:</strong></p>

<pre>

#include< iostream.h>

#include< conio.h>

classqueue

public:

intq[5],front,rear,x,result;

voidenq();

voiddque();

voiddisp();

queue()

front=0;

rear=0;

;

voidqueue::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];

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

voidqueue::disp()

if(rear==0)

cout<<"\nUnderflow!!\n";

else

cout<<"\nPrinting Contents of queue:";

for(inti=front+1;i<=rear;i++)

cout<< q[i]<<"\t";

voidmain()

intc;

queuequ;

clrscr();

// cout<<"\n*****";

// cout<<"\nQUEUE";

// cout<<"\n*****";

cout<<"\n1.Insertion\n2.Deletion\n3.Display\n";

cout<<"\nEnter your choice:";

cin>>c;

switch(c)

case1:

qu.enq();

break;

case2:

qu.dque();

break;

case3:

qu.disp();

break;

default:

cout<<"\nInvalid choice!!\n";

while(c<4);

getch();

</pre>

<h3>3.7PriorityQueue</h3>

<h4>3.7.1IntroductiontoPriorityQueue</h4>

<p>PriorityQueuealsocomesunderContainerAdaptorandprovidesconstanttimelookupofthelargestelement. Butitdoessoattheexpenseoflogarithmicinsertionandextraction. WorkingwithaPriorityQueueissimilartoworkingwithaheapinthecontextofsomerandom-accesscontainer. Itprovidesthebenefitofnotbeingabletoaccidentallyinvalidatetheheap.</p>

<h4>3.7.2OperationsonPriorityQueue</h4>

<p><strong>PROGRAM:</strong></p>

<pre>#include< iostream.h>

#include< conio.h>

constintMAX=5;

classpqueue

intfront,rear;

public:

structdata

intval,p,o;

d[MAX];

pqueue()

front=rear=-1;

voidinsert(datad1);

datadeletion();

voiddisplay();

;

voidpqueue::insert(datad1)

if(rear==MAX-1)

cout<<"The Queue is Full

else

rear++;

d[rear]=d1;

if(front==-1)

front=0;

datatemp;

for(inti=front;i<=rear;i++)

for(intj=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;

datapqueue::deletion()

datad1;

if(front==-1)

cout<<"The Queue is Empty

else

d1=d[front];

if(front==rear)

front=rear=-1;

else

front++;

returnd1;

voidpqueue::display()

if(front==-1)

cout<<"The Queue is Empty

else

for(inti=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;

voidmain()

pqueuep1;

datad1;

charop;

intch;

clrscr();

cout<<"1.Insert

2.Delete

3.Print

4.Exit

cout<<"Enter Choice<1..4> ?";

cin>>ch;

switch(ch)

case1:cout<<"Enter Value ?";

cin>>d1.val;

cout<<"Enter Priority";

cin>>d1.p;

cout<<"Enter Order";

cin>>d1.o;

p1.insert(d1);

break;

case2:d1=p1.deletion();

cout<<"Value = "<< d1.val<< endl;

cout<<"Priority = "<< d1.p<< endl;

cout<<"Order ="<< d1.o<< endl;

break;

case3:p1.display();

break;

cout<<"Do You Want to Continue Y/N?";

cin>>op;

while(op=='Y' || op=='y');

getch();

</pre>

</div>