Container Adaptors and Algorithms
The following topics are covered in this section:
Container adaptors adapt and use one of the previously discussed data structures. They do not have their own data structure implementation but instead we can select the data structure. They do not support iterators and there are 3 types of container adaptors:
By default the stack and queue are based on deque while priority queue is based on vector. Of course you can specify your own data structure to override the default but generally programmers will not change the default container.
Stack
The stack is built upon a deque. You might be wondering why we need a stack when it is ultimately based on one of the other existing containers? The reason is that by using a stack you clearly define the purpose for the container. When you use a stack it indicates that you are only going to perform valid stack operations and that you won’t violate the stack by using other operations. You can perform the functions of the stack container using a deque or vector but when you use these containers other operations (which are not stack operations) are also valid. Basically the stack adaptor converts the underlying data structure into a stack (i.e. such that only stack operations are permitted).
The header file needed to use a stack is: <stack>. Iterating through the elements of a stack is not permitted (iterators are not supported). You can push and pop elements from a stack. The pop( ) function will not return the value of the element present at the top. To read the element at the top you have to use the top( ) function.
We have already seen a program using the STL stack container.
//Program to illustrate the stack container of STL
#include <iostream>
#include
<stack>
using namespace std;
int main( )
{
stack<int>
intstack;
int i;
//Adding 5 values to the stack (100 101 102
103 104)
for( i=100; i<105; i++
)
{
intstack.push(i);
}
//Displaying the size of the
stack
cout<<endl<<"Number of elements
in the stack: "<<intstack.size( );
//Popping the elements of the stack till it
becomes empty.
//Before popping we display the value of the element which is
// going to be popped
cout<<endl<<endl<<"Popping the elements one by one"<<endl;
for (i=0; !intstack.empty( );
i++)
{
cout<<endl<<intstack.top( );
intstack.pop(
);
cout<<endl<<"Size of stack after popping:
"<<intstack.size( );
}
return 0;
}
The output will be:
Number of elements in the stack: 5
Popping the elements one by one
104
Size of stack after popping:
4
103
Size of stack after popping: 3
102
Size of stack after
popping: 2
101
Size of stack after popping: 1
100
Size of stack
after popping: 0
Suppose you want to use a different data stucture as the base for the stack then you have to declare the stack as:
stack<int,vector<int> > intvec;
This declares ‘intvec’ as a stack using a vector as the underlying data structure.
Queue
The queue adaptor is by default modeled on the deque. The reason for this adaptor is the same as the reason why stack exists. Only queue operations can be performed when using the queue container. The reason for using queue instead of deque is to emphasize on the fact that you will be using only queue operations. Just like a stack we have the push and pop functions but instead of top( ) we have the front( ) function to read the first element in the queue.
An example program using the queue adaptor container has been discussed earlier.
//A program to illustrate the STL container for queues
#include <iostream>
#include <queue>
using namespace std;
int main( )
{
queue<int> intqueue;
int i;
//adding 5 values to the queue (0 1 2 3 4)
for(i = 0; i < 5 ; i++)
{
intqueue.push(i);
}
cout<<endl<<"The first element is :
"<<intqueue.front( );
cout<<endl<<"The last element is : "<<intqueue.back( );
cout<<endl<<"The size of the queue is: "<<intqueue.size( );
//Removing the elements of the
queue one by one
cout<<endl<<"Queue contents are : ";
for (i = 0; !intqueue.empty( ); i++)
{
cout<<endl<<"Element removed: "<<intqueue.front( );
intqueue.pop( );
cout<<endl<<"Size of queue after popping: "<<intqueue.size( );
}
return 0;
}
The output of the program will be:
The first element is : 0
The last element is : 4
The size of the queue is: 5
Queue contents are :
Element removed: 0
Size of queue after popping: 4
Element removed: 1
Size of queue after popping: 3
Element removed: 2
Size of queue after popping: 2
Element removed: 3
Size of queue after popping: 1
Element removed: 4
Size of queue after popping: 0
Priority Queue
This is similar to a queue except that the elements get inserted into the queue based on their priority. Thus you can insert elements in sorted order into the underlying data structure (which is a vector by default). Take a look at the program below:
#include <iostream>
#include <queue>
using namespace std;
int main( )
{
priority_queue<int,vector<int>,less<int> > intque;
for (int i=0;i<5;i++)
{
intque.push(i);
}
while (intque.empty( )!=true)
{
cout<<" "<<intque.top( );
intque.pop( );
}
return 0;
}
The output will be:
4 3 2 1 0
As you can see even though the first element to enter the queue was 0 it ended up being the last element of the queue because all the other elements had a greater priority. To decide on the priority take a look at the declaration of the priority queue:
priority_queue<int,vector<int>,less<int> > intque;
Since we have specified less<int>, this indicates that the elements with higher value will be given greater priority (and hence they will be placed at the front of the queue). Instead of less<int> we can also use greater<int>. This has the opposite effect and elements with lower values will be placed at the front of the queue.
You will want to perform a lot of operations on your data structure. Some of the operations are quite common ones like sorting, searching, shuffling, finding the minimum or maximum element etc.
STL provides with a set of algorithms that can be applied across all data structures. These algorithms are generalized (i.e. they do not depend on the internal structure of the elements). For ex: the random_shuffle algorithm can work on vectors as well as on linked lists even though both are different data structures. How are algorithms implemented? Algorithms are basically template functions and most of the algorithms take iterators as arguments (thus they avoid relying on the data structure type). Some of these functions might also be available as member functions in some data types. In this case which one should we choose (the general function or the specific function)? It is better to use the specific member function since member functions are developed for specific data structures (they will be more efficient than the general algorithms).
There are many algorithms available in STL and we won’t be looking at all of them. To provide a basic idea of how they are used try out the following program:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main( )
{
vector<int> intvec1;
for (int i=10;i<20;i++)
{
intvec1.push_back(i);
}
cout<<endl<<"Original Vector is: ";
for (i=0;i<intvec1.size( );i++)
{
cout<<intvec1[i]<<" ";
}
random_shuffle(intvec1.begin(),intvec1.end());
cout<<endl<<"Shuffled vector is: ";
for (i=0;i<intvec1.size();i++)
{
cout<<intvec1[i]<<" ";
}
sort(intvec1.begin(),intvec1.end());
cout<<endl<<"Sorted vector is : ";
for (i=0;i<intvec1.size();i++)
{
cout<<intvec1[i]<<" ";
}
return 0;
}
The output will be:
Original Vector is: 10 11 12 13 14 15 16 17 18 19
Shuffled vector is: 14 13 10 12 16 17 18 19 15 11
Sorted vector is : 10 11 12 13 14 15 16 17 18 19
The two algorithms used above are: sort( ) and random_shuffle( ). The names are self-explanatory. We need to pass two iterators to define the range of elements on which we want the algorithm to act upon. In our program we’ve specified the entire range of the vector.
Some other algorithms available are:
min_element(iter1, iter2)
max_element(iter1, iter2)
find(iter1, iter2, value)
Remember: These algorithms are not member functions. Do not use the dot operator to invoke them.
Go back to Contents page 2.
Copyright © 2004 Sethu Subramanian All rights reserved.