17

CHAPTER

Overview of Standard Template Library (STL)

17.1 INTRODUCTION TO STL

We have studied templates, which allow us to do generic programming. Generic functions or classes support all data types. The Standard Template Library is an advanced application of templates. It contains several in-built functions and operators that help the programmer to develop complex programs. The programmer only needs to include appropriate header file to use the function or operator from file like library functions. STL library helps to write programs free from bugs. In case, any bug is present, it is easy to debug. For example, if a programmer wants to create link list, he/she may require writing a program that may be of 40 to 50 lines. However, using STL functions (list algorithm), it can be done in a few minutes.

The Standard Template Library (STL) is a new feature of C++ language. All-famous compiler vendors provide the STL as a feature of their compilers. The STL is vast and heterogeneous collection of reusable container classes. It consists of vectors, lists, queues, and stacks. The STL is portable with various operating systems.

Meng Lee and Alexander Stepanov of Hewlett-Packard introduced the STL and it was accepted in 1994 as an addition to the customary C++ library. The STL provides well-coded and compiled data structures and functions that are helpful in generic programming. STL is reusable. STL topic is very vast, hence, its complete description is beyond the scope of this book. Only major features are explained. STL contents are defined in the namespace std. It is essential to write the statement using namespace std at the beginning of the program. In the next chapter namespaces are explained.

17.2 STL PROGRAMMING MODEL

STL is divided into three parts namely containers, algorithms, and iterators. All these three parts can be used for different programming problems. All these parts are closely associated with each other.

(1) Containers

A container is an object that contains data or other objects. The standard C++ library has a number of container classes that allow a programmer to perform common tasks. These containers support generic programming and can be used for handling data of different data types. All STL container classes are declared in namespace std. There are two types of containers sequence, container and associative container as shown in Figure 17.1. Sequence containers are created to allow sequential and random access to members. The associative container allows access to their elements through key.

(2) Algorithm

An algorithm is a technique that is useful to handle the data stored in containers. The STL comprises approximately 60 standard algorithms that give support to perform frequent and primary operations such as copying, finding, sorting, merging, and initializing. The standard algorithms are defined in the header file <algorithm>.

(3) Iterators

An iterator is an object. It exactly behaves like pointers. It indicates or points to data element in a container. It is utilized to move between the data items of containers. Iterators can be incremented or decremented like pointers. Iterators link algorithms with containers and handle data stored in the containers.

17.3 CONTAINERS

The standard C++ library has a sequence of container classes. The container classes are robust and support C++ programmers to control common programming operations. There are three types of STL container classes. They are sequence, associative and derived containers. Sequence containers are developed to allow sequential and random access to all the members. Associative containers are expanded to get their elements by values. Derived containers such as stack, queue, and priority queue can be created from various sequence containers. The STL has ten containers. They are divided into three types as shown in Figure 17.1.

Fig. 17.1 Classification of containers

17.4 SEQUENCE CONTAINERS

The STL sequence containers allow controlled sequential access to elements. Sequence containers hold data elements in a linear series as shown in Figure 17.2. Every element is associated by its location within the series. All these elements enlarge themselves to let insertion of element. These elements also allow various operations like copying, finding etc.

Fig. 17.2 Data items in sequence container

The STL has three types of sequence containers:

(i) vector

(ii) list

(iii) deque

Iterators are used to get the elements in all these containers. All these containers have different speed.

(1) Vector

We know that an array is used to store similar data elements. Elements of arrays are stored in successive memory locations and can be accessed, in order, from element number 0 onwards. The vector class exactly acts like an array. The vector container class is secured and efficient than arrays.

A vector container class is accelerated to allow quick access to its elements in sequence. It is defined in the header file <vector>. A vector is able to enlarge itself. For example a vector declared for 5 elements, if assigned 6 elements, then the vector automatically grows its size so that it can hold the 6th element. The vector class is declared next.

Declaration of Vector class

template<class TE>, class B =allocator<TE>class vector

Here the class TE is the type of element in vector and class B is an allocator class. M_allocators are responsible for allocating memory and releasing them. By default, the new( ) and delete( ) operators are used for allocating memory and releasing. The default constructor of class TE is invoked to produce a new element. This allows entry of another parameter in order to define a default constructor for user-defined classes. The vector that holds integers and floats is declared below:

Vector declaration for int and float data

vector<int> vi     // for integer elements

vector <float> vf // for float elements

To declare a vector of 15 items a constructor can be declared as shown below:

vector<item> sale(15);

The compiler allocates memory to 15 elements. Here, the default constructor item :: item( ) is used.

(2) List

The list container allows usual deletion and insertion of items. A list is also a sequence that can be accessed bi-directionally. It is defined in header file <list>. It acts as double linked list. Every node is connected to both back and front node in the list. The iterator is used to transverse the link. The list class supports all the member functions of vector class. The elements in the linked list are accessed using pointers. The list container has a technique known as iterator, which is used to access elements of list container. An iterator is same as pointer. The iterator can be referenced like pointers to access elements.

(3) Deque

Deque is similar to a multiple ended vector. It has ability like vector class to perform sequential read and write operations. The deque class allows improved front-end and back-end operations. Deques are perfectly appropriate for the operation that contains insertion and deletion at one or both ends and where sequential access is essential.

17.5 ASSOCIATIVE CONTAINERS

The associative container allows fast access to the objects in the container. These containers are useful for huge dynamic tables in which we can search an element randomly and sequentially. These containers use tree like structures of elements instead of linked lists. These structures allow quick random update and retrieval operations. Associative containers are non-sequential and allow direct access to elements. Associative containers are divided into four categories:

(1) Set

(2) Multiset

(3) Map

(4) Multimap

All these above listed containers hold data elements in a structure called tree. The tree provides quick finding, deletion, and insertion. These containers perform very slowly in random access operation and are inappropriate for sorting operation.

Container set and multiset store data elements. They also allow various operations for managing them. The variable name is used as key name. A set might contain objects of player class. It can be sorted in ascending order using the names as keys. The multiset may have multiple set of elements i.e. it permits duplicate data elements. The set does not allow duplicate elements.

Containers, map and multimap, store both key name and value. The values are associated with key names. The values can be handled using key names. The values are also called as mapped values. Multimap allows the use of various keys. Map container permits single key.

17.6 ALGORITHMS

Algorithms are independent template functions. They are not members or friend functions. They allow the programmer in manipulating data stored in various containers. Algorithms carry out operations on containers by dereferencing iterators. Each container has its functions for performing common operations. Algorithm is nothing but a function template with arguments of iterator type. Algorithms receive iterators as arguments. The iterators inform the algorithm regarding objects of container on which operation is to be carried out. In addition, STL contains approximately sixty standard algorithms. These functions allow quick operations in complicated and large operations. Including the <algorithm> header file we can use these functions. The programmer reuses all these container classes.

Table 17.1 Non-mutating sequence operation

Non-mutating sequence algorithms as shown in Table 17.1 allow operations, which do not alter the elements in a sequence. For example, the operators for_each( ), find( ) search( ), count( ) etc. The program given next explains how to use for_each( ) algorithm.

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;


template <class S>
class show
{
    public:
       void operator( ) ( const S& s)
       {
            cout<<s;
       }


};


int main( )
{


     show<int> showvalue;
     vector<int> vi(4);


for ( int j=0;j<4;++j)
     vi[j]=j;


cout<<" for_each( ) 
";


for_each(vi.begin( ),vi.end( ),showvalue);
cout<<"
";
return 0;


}

Explanation: The operator( ) is overloaded in the class show. The showvalue is an object of the class show. A vector vi is created which can hold four elements. Using first for loop, 0 to 3 numbers are inserted in the vector. While reading numbers from vector, instead of using for loop the operator for_each( ) is used. The first argument of for_each( ) operator (vi.begin( )) gives the reference of first element. The second argument gives the reference of last element of the vector and the third argument (showvalue) is a function object. Thus, using for_each( ) operator members of vector can be accessed.

# include <iostream>
# include <vector>
# include <algorithm>

using namespace std;

template <class S>
class show
{
     public:
       void operator( ) ( const S& s)
       {
            cout<<s;
     }
};


int main( )
{
     show<int> showvalue;
     vector<int> vi(8);

     fill(vi.begin( ),vi.begin( ) + 2,5);
     fill(vi.begin( )+2,vi.begin( ) + 4,6);
     fill(vi.begin( )+4,vi.end( ),7);



cout<<" for_each( ) 
";

for_each(vi.begin( ),vi.end( ),showvalue);
cout<<"
";
return 0;
}

Explanation: This program is same as the previous one. Here, the algorithm fill( ) is used. The fill( ) is a mutating algorithm because it changes the elements of the vector.

The following statements are used to fill the elements in the vector:

fill(vi.begin( ),vi.begin( ) + 2, 5);

The above statement fills first 2 elements with value 5. The function begin( ) gives beginning reference and begin( ) + 2 gives reference for the second.

fill(vi.begin( )+2,vi.begin( ) + 4, 6);

The above statement fills value 6 at third and fourth location of the vector. Here also, begin( ) function is used.

fill(vi.begin( )+4, vi.end( ), 7);

The above statement fills value 7 from location number 5 to end.

Table 17.2 describes algorithm operations related to sorting.

Table 17.2 Sorting operations

Table 17.3 describes mutating sequence operations.

Table 17.3 Mutating sequence operations

Table 17.4 describes numeric operations.

Table 17.4 Numeric operations

17.7 ITERATORS

Iterators act as pointers. They are used for accessing contents of container classes. They allow movement from one element to another element. It is called iterating. Each container type supports one kind of iterator according to its necessity. The types are input, output, forward, bi-directional and random access. The hierarchy of iterators is shown in Figure 17.3 and described in Table 17.5 and 17.6.

Fig. 17.3 Iterator hierarchy

Table 17.5 Operation of container classes

Table 17.6 Iterator status

Iterators are used by algorithms to carry operations. Iterators are smart pointers. They are allowed to contain values that indicate one of the statutes of iterators as described in Table 17.6. Each iterator type supports all the attributes listed in Table 17.6 and shown in Figure 17.3. Iterators can be incremented, decremented, and their limits are up to the capacity of containers. Containers have member functions which return iterators.

17.8 VECTOR

The vector is a more useful container. Like arrays, it also stores elements in neighbouring memory locations. Each element can be directly accessed using the operator []. A vector is able to enlarge its size if extra element is assigned to it. Class vector has various constructors that can be used to create vector objects. The function of vector class is shown in Table 17.7.

Table 17.7 Functions of vector class

# include <iostream>
# include <vector>
# include <math.h>
using namespace std;


int main( )
{
       vector<float> e;
       cout.precision(2);
       cout <<"
 Original elements         : ";


  for (int k=5;k<12;k++)
  {
       e.push_back(sqrt(k));
       cout <<sqrt(k)<<"  ";
  }



       vector <float> ::iterator ir=e.begin( );
       e.erase (ir+3,ir+5);


       int s=e.size( );


       cout <<"
 The elements after erase( ) : ";
       for (k=0;k<s;k++)
       cout <<e[k]<<"  ";
       cout <<"
";

  return 0; 
}

Explanation: In the above program, e is an object of a vector capable of storing float values. The square roots of 5 to 12 numbers are stored in the object e. The erase( ) function erases 4th and 5th element. The variable ir is an iterator and it gives reference to the element. The erase ( ) function can be used with one or more arguments. The last for loop displays the elements after deletion.

17.9 LIST

The list is frequently used feature. It allows bi-directional linear list. Elements can be inserted or deleted at both the ends. The elements in the list can be accessed sequentially. Iterators are used to access individual elements of the list. Table 17.8 shows the functions of list class.

Table 17.8 Functions of list class

# include <iostream>
# include <list>


using namespace std;


void show( list <int> &num)
{
     list<int> :: iterator n;
     for (n=num.begin( );n!=num.end( ); ++n)
       cout <<*n<<" ";
}


int main( )
{
list <int> list;
list.push_back(5);
list.push_back(10);
list.push_back(15);
list.push_back(20);


cout<<"
Numbers are ";
show(list);
list.push_front(1);
list.push_back(25);
cout<<"
After adding numbers are ";
show(list);
return 0;
}

Explanation: The above program is same as the previous one. In addition, here two elements are added to both the ends of the list. The function push.front( ) adds elements to the front end of the list and push_back( ) function appends the element to the rear end of the list. The output shows all the elements of the list.

# include <iostream>
# include <list>


using namespace std;


void show( list <int> &num)
{
     list<int> :: iterator n;
     for (n=num.begin( );n!=num.end( ); ++n)
       cout <<*n<<" ";
}


int main( )
{
  list <int> list;
  list.push_back(5);
  list.push_back(10);
  list.push_back(15);
  list.push_back(20);


  cout<<"
Numbers are ";
  show(list);
  list.pop_front( );
  list.pop_back( );
  cout<<"
After deleting numbers are ";
  show(list);
  return 0;
}

Explanation: In the above program, the member function pop_front( ) is used to delete the front element of the list and the pop.back( ) function is used to delete the back element of the list. The output shows the list of numbers.

# include <iostream>
# include <list>


using namespace std;
void show( list <int> &num)
{
     list<int> :: iterator n;
     for (n=num.begin( );n!=num.end( ); ++n)
       cout <<*n<<" ";
}


int main( )
{
     list <int> list;
list.push_back(23);
list.push_back(19);
list.push_back(5);
list.push_back(15);
list.push_back(25);
list.push_back(20);


cout<<"
 Unsorted list :";
show(list);
cout<<"
 Sorted   list : ";
list.sort( );
show(list);
return 0;
}

Explanation: In the above program, the push_back( ) function is used to add elements to the list object. The function sort( ) is used to sort the list element in ascending order. The program shows the list of unsorted and sorted elements using show( ) function.

# include <iostream>
# include <list>


using namespace std;


void show( list <int> &num)
{
     list<int> :: iterator n;
     for (n=num.begin( );n!=num.end( ); ++n)
       cout <<*n<<" ";
}



int main( )
{
  list <int> listX,listY;
  listX.push_back(23);
  listX.push_back(19);
  listX.push_back(5);


  listY.push_back(15);
  listY.push_back(25);
  listY.push_back(20);


  cout<<"
 Elements of listX :";
  show(listX);
  cout<<"
 Elements of listY :";
  show(listY);


  listX.merge(listY);
  cout <<"
 Merged list : ";
  show(listX);
  return 0;
}

Explanation: In the above program, the listX and listY are initialized with three objects each with the function push_back( ). The merge( ) function merges the elements of two list objects into one. The elements are merged in the calling object. Thus, in this program, listX calls the function and listY is sent as an argument. The listX contains its own elements and elements of listY. In the output elements of listX and listY are displayed.

17.10 MAPS

A map is a series of pairs of key names and values associated with it as shown in Figure 17.4. Access to data values depends upon the key and it is very quick. We must specify the key to get the corresponding value.

Fig. 17.4 Keys and values in maps

# include <iostream>
# include <map>
# include <string>
using namespace std;


typedef map<string,int> item_map;


int main ( )
{
     int sz;
     string item_name;
     int codeno;
     item_map item;
     cout <<"Enter item name and code number for 2 items: 
";
     for (int i=0;i<2;i++)
     {
       cin>>item_name;
       cin>>codeno;
       item[item_name]=codeno;
}
     item["PC"]=2510;

     item.insert(pair<string,int> ("printer",2211));
     sz=item.size( );
     cout<<"
 Size of map :"<<sz <<"

";
     cout <<"List of item name and code numbers 
";
     item_map::iterator t;
     for ( t=item.begin( );t!=item.end( );t++)
       cout <<(*t).first <<" " <<(*t).second<<"
";cout <<"
";
     cout <<"Enter item name : ";
     cin>>item_name;
     codeno=item[item_name];
     cout <<"Code Number : "<<codeno <<"
";
     return 0;
}

Explanation: In the above program, using typedef statement item_map variable is created. The first for loop and cin statement reads two records through the keyboard. Using member function insert( ) and assignment two records are inserted. The size( ) member function returns the number of records. The variable t is an iterator to the map. The second for loop and the iterator produces the list of item names and code numbers. At the end, the program displays code number associated with the entered item name. The item_name is a key. The list is automatically arranged in sorted order.

A map is also known as an associative array. The key is given with the help of subscript operator [ ] as given below:

item [“PC”] = 2510;

The above statement creates record for “PC” and links it with code number 2510. The codeno is an object. It is also possible to insert and remove pairs at any point in the map. The insert( ) and delete( ) functions perform these tasks. Frequently used functions are described in Table 17.9.

# include <iostream>
# include <map>
# include <string>
using namespace std;
typedef map<string,int> item_map;


int main( )
{
     int sz;
     string item_name;
     int codeno;
     item_map item;


     item["PC"]=2510;


     item.insert(pair<string,int> ("printer",2211));
     sz=item.size( );
     cout<<"
 Size of map :"<<sz <<"

";


     item.clear( );
     sz=item.size( );


     cout<<"
 after clear ( ) Size of map :"<<sz <<"

";
     return 0;
}

Explanation: In the above program, two records are added in the map item_map. Using size( ) function, size (total number of records) are displayed i.e. the clear( ) function clears the contents of the map. After clear( ) function, the size of map becomes zero.

Table 17.9 describes important functions of map class.

Table 17.9 Important functions of the map class

17.11 FUNCTION OBJECTS

A function object is a function. It is embedded in a class and hence behaves as an object. The class has same characteristics as template and can be put to use with different data types. The class can hold only one member function and the overloaded ( ) operator and never accommodates data. Function objects are frequently used as parameters for algorithms and containers.

sort( num,num+3, greater <float>( ));

Here, num[] is an array. We can use object greater<float>( ) to sort elements of the array in descending order. The standard template library also contains several pre-defined objects. These objects perform arithmetical and logical operations. The header file <functional> should be included while performing these operations. There are function objects matching to foremost C++ operators. The variables a and b are objects of the class. K is a parameter sent to the function object. All the function objects described in the Tables 17.10, 17.11 and 17.12 are defined in functional header file.

Table 17.10 Relational function objects

Table 17.11 Logical function objects

Table 17.12 Arithmetic function objects

# include <iostream>
# include <algorithm>
# include <functional>


using namespace std;


int main( )
{
     float a[]={1.5,6.5,2.5};
     float b[]={6.4,4.8,1.4};


     sort (a,a+3,greater<int>( ));
     sort (b,b+3);


     for (int j=0;j<3;j++) cout <<a[j]<<" ";


     cout <<"
";


     for (int k=0;k<3;k++)   cout <<b[k]<<" ";
     cout <<"
";


     float s[6];
     merge (a,a+3,b,b+3,s);


     for (j=0;j<6;j++)  cout <<s[j] <<" ";
     cout <<"
";
     return 0;
}

Explanation: In the above program, two float arrays a[ ] and b[ ] are declared and initialized. The function sort( ) both the arrays. The array a[ ] is sorted with the help of function object greater<float> and the array b[ ] is sorted without function. At the end, the merge( ) function combines elements of both the arrays and the resulting array is stored in the array s[ ]. The contents of the merged array is displayed.

SUMMARY

(1) The STL is a new expansion in C++ language. All-famous compiler vendors give STL as a feature of their compilers.

(2) Meng Lee and Alexander Stepanov of Hewlett-Packard introduced STL.

(3) STL is portative between different operating systems. STL contents are defined in the namespace std.

(4) The important subdivisions are (a) containers, (b) algorithms and (c) iterators.

(5) A container is an object that holds data or other objects. An algorithm is a process that is useful to handle the data stored in containers. The STL consists of about 60 standard algorithms that give support to perform frequent and primary operations such as copying, finding, sorting, merging, and initializing.

(6) An iterator is an object. It is treated as a pointer. It indicates or points to data elements in a container. It is utilized to move between the data of containers.

(7) The standard C++ library has a sequence of container classes. The container classes are robust and support C++ programmers to control common programming operations.

(8) Sequence containers hold data elements in a linear series.

(9) We know that arrays are used to store similar data elements. The data elements are stored in continuous memory locations. The container class vector is same as the array.

(10) A vector container class is accelerated to allow quick access to its elements in sequence.

(11) The list container allows a programmer for usual deletion and insertion of items. It is defined in header file <list>. It acts as double linked list.

(12) A deque is similar to a multiple ended vector. It has ability like vector class to perform sequential read and write operations. The deque class allows improved front-end and back-end operations.

(13) The stack, queue, and priority_queue are called as container adaptors. All these container adaptors can be produced from unlike sequence containers.

(14) Algorithms are independent template functions. They are not member or friend functions. They allow the programmer to manipulate data stored in various containers. Each container has functions for performing common operations.

(15) Iterators act as pointers. They are used for accessing contents of container classes.

(16) The vector is a more useful container. Like arrays, it stores elements in neighbouring memory locations. Each vector can be directly accessed using the operator []. A vector is able to enlarge its size if extra element is assigned to it.

(17) The list is a frequently used feature. It allows bi-directional linear list. Elements can be inserted or deleted at both the ends.

(18) A map is a series of pairs of key names and values associated with it.

EXERCISES

[A] Answer the following questions.

(1) What is STL? Explain in brief.

(2) Describe different sub-divisions of STL with their definitions.

(3) What are containers? Describe types of containers with their components.

(4) What do you mean by algorithms?

(5) What are iterators?

(6) What is the difference between iterator and pointer?

(7) Describe any four functions of a vector class with their operations.

(8) Describe any four functions of a list class with their operations.

(9) What is a map? How does it work?

(10) What do you mean by function object ?

(11) Describe any four functions of a map class with their operations.

(12) What are function objects?

[B] Answer the following by selecting the appropriate options.

(1) A container is an object that

a) stores data

b) holds data temporarily

(c) both (a) and (b)

(d) none of the above

(2) An algorithm is a process that

(a) processes the data

(b) stores the data

(c) sorts the data

(d) none of the above

(3) An iterator is similar to

(a) pointer

(b) array

(c) class

(d) none of the above

(4) The function object is similar to

(a) object

(b) variable

(c) both (a) and (b)

(d) none of the above

(5) An algorithm is a part of

(a) standard template library

(b) class template

(c) iostream

(d) none of the above

[C] Attempt the following programs.

(1) Write a program to demonstrate use of operator for_each( ).

(2) Write a program to create function object.

(3) Write a program to manipulate list of item names and their code numbers using maps.

(4) Write a program to copy elements of one list object to another object. Display the contents of both the objects.

(5) Write a program to merge two lists and display the merged list.

(6) Write a program to demonstrate use of fill( ) algorithm.

(7) Write a program to transverse list using iterators.

(8) Write a program to add and display elements in the vector object.

(9) Write a program to add elements to both ends of the list and display the numbers.

(10) Write a program to insert an element in the vector object. Use member function and iterator.