CHAPTER 18
STANDARD TEMPLATE LIBRARY
WHY STL (STANDARD TEMPLATE LIBRARY)?
There are common data structures and algorithms that are used over and over in programs. C++ provides ready-made solutions for these data structures and algorithms by including them in a library. Therefore, a programmer can simply use them rather than make them. The advantage is that the programmer can use these data structures and algorithms that are defined, standardized, tested, and ready to be used rather than starting from scratch each time. In addition to the original built-in functions of C/C++, in 1994 STL became part of the standard library by adding new classes that work with any data type, promoting reuse rather than reinventing the wheel. Certain data structures and algorithms are used over and over by programmers, so why not automate these data structures and algorithms? Certain components of STL are better suited for different circumstances.
For beginners or even experienced programmers STL can be difficult to grasp. The syntax of STL is a little intimidating. After observing the capabilities of STL, the value of this tool becomes obvious and you want to use it more. Just keep in mind that the goal of STL is to provide you with a collection of generic tools so that you can enhance your programmability. If you have had difficulty building a linked list and operating it manually, using STL you can request an automatic double linked list with the all the necessary functions to operate it. Just remember STL by itself is a vast topic and you need time to become acquainted with it.
THREE COMPONENTS OF STL: CONTAINERS, ALGORITHMS, AND ITERATORS
STL comes with three components that work with each other to solve problems of all different kinds. These three components are known as containers, iterators, and algorithms. As the name suggests, a container represents storage units that hold data elements (data structure). An iterator is like a loop that moves and scans through the container. An iterator that points to the contents of a container can be used to traverse through the elements of that container. Each container has its own algorithms (functions); there are also algorithms that work with all containers. In summary, the algorithms are the programs (functions) that are applied to data structures.
CONTAINER TYPES
Containers can be divided into two parts: sequence containers and associative containers. Sequence containers are: vector, list, and deque (double-ended queue). Associative containers are sets and maps. From sequence containers other containers have been created, such as stacks and queues, which are known as adapters.
STL ITERATORS
The main job of STL iterators is to access the elements of a container. The word iterator reminds one of a loop or iteration; however, iterators are more like pointers than loops. Some see STL iterators as smart pointers. Iterators are an abstraction of pointers. An iterater points to a container and the iterator can be incremented, decremented, and checked for equality (= =, !=) in the same way as a pointer pointing to an element of an array. The content of what an iterator points to can be accessed with * indirection operator (*iter) or (*iter).first for the map and set (or alternatively iter ->first). The functions begin( ) and end( ) return iterators than can be used to access the beginning of the container and the terminating end of the container. Iterators are the bridge between algorithms and containers. Containers may have specified iterators. In addition to traversing the data elements of a container, there are two kinds of iterators that are connected to the input/output streams known as input iterator (inputIterator) and output iterator (outputIterator). These iterators allow you to copy the contents directly to the output device or access the data from the input device and copy it to the container.
STL ALGORITHMS
STL consists of several standardized generic functions (algorithms) that can be used on any of the containers. Therefore, many container functions can be applied to other containers. For example, the functions insert( ) and remove( ) insert and remove elements from a vector, list, or string using the same interface (function call and parameters). The list of other major algorithms are: find( ) (to look for a value), binary_search( ) (search for value in a sorted sequence), unique( ) (ensures that the sequence is unique, no duplicates), sort( ) (sorts sequence in ascending order), replace( ) (replaces the old value with the new value), for_each( ) (applies a function to every element in the sequence), max_element( ) (finds the maximum element in the sequence), min_element( ) (finds minimum element in the sequence), and count( ) (returns the frequency of a value in the data). There are other algorithms that will be discussed later.
TEN IMPORTANT STL CONTAINERS:
vector: A vector contains a sequence of contiguous storage units (linear) and objects are pushed at one end (back end). The elements of a vector can be accessed randomly. A vector is similar to a C-style array, but you do not have to declare the size. The function size( ) returns the current number of elements in the vector and the function push_back() pushes an element into the vector. The general syntax for vector, is vector <datatype> objectname, for example: vector <string> v
Vector is the best container when you want to push an element at the end of a sequence.
deque: A sequence of noncontiguous storage; elements can be pushed at both the beginning and the end.
list: A sequence of noncontiguous storage where elements can be inserted anywhere in the sequence, at the beginning, middle, or end.
stack: It is a last in first out container which can be built from any of the above containers (vector, list, dequeue). Example, stack(c) where c can be built from vector(t), dequeue(t), or list(t).
queue: It is a first in first out container and can be created from either list or deque; elements can be inserted at the beginning or end.
priority_queue: It is a first in, first out, sorted container and can be built from either vector or deque.
map: Associated array with keys and values, for each key there is one value. For example: name and telephone number.
multimap: Same as map but now you can have duplicates.
set: Is a set of objects with no duplication allowed.
multiset: Is a set of objects where duplications are allowed.
It is possible to perform what you want to do with more than one kind of container but there is usually one container that is optimal for the application. The first task is to find the right container and the rest will fall into place.
SEQUENTIAL CONTIGUOUS DYNAMIC ARRAY WITH ONE END: vector
The STL vector is a single-ended sequential container and is one of the most widely used containers. One reason for its popularity is its resemblance to the C-style array. Vectors perform the same functions as arrays and much more. With vectors, you do not need to worry about the size in the declaration or the maximum size. The major operations on a vector are shown in the following program:
![Text Box: #include<iostream>
#include<vector>
using namespace std;
int main(){
vector <int> v; //declaring v as a vector of type int
int element;
cin>>element;
v.push_back(element); //inserting an element into vector, no need to increment the index
cout<<v[0]<<endl; //through the index an element of vector can be accessed
cout<<*v.begin()<<endl; //to access first element, and vector base address
cin>>element;
v.push_back(element); //push more element into vector
vector <int>::iterator p; //declaring an interator point to the vector of type int
p = v.begin();
while(p != v.end( )){ //end() will point to one-past-the-end
cout<<*p<<" "; p++; }//display the content of iterator (what p points to)
return 0;
}// MAIN](http://www.geocities.com/lonairl1/chap18_files/image001.gif)
vector PROGRAM WITH OPERATIONS: empty( ) AND size( )
In addition to the above vector member functions, the following program demonstrates how you can use the functions empty( ) and size( ). The function empty( ) returns true if the vector is empty. The function size( ) returns the number of elements in the vector.
![Text Box: #include<iostream>
#include<vector>
using namespace std;
int main(){
vector <double> employee;
double salary;
if(employee.empty()) cout<<"VECTOR IS EMPTY"<<endl;
cout<<"NUMBER OF ELEMENTS IN THE VECTOR: "<<employee.size()<<endl;
cout<<"ENTER EMPLOYEES SALARIES, CTRL/D TO STOP: "<<endl;
while(cin>>salary){
employee.push_back(salary);}//WHILE
cout<<"NUMBER OF ELEMENTS IN THE VECTOR: "<<employee.size()<<endl;
for(int i=0; i<employee.size();i++) cout<<employee[i]<<" "<<endl;
return 0;
}//MAIN](http://www.geocities.com/lonairl1/chap18_files/image005.gif)
VECTORS, ITERATORS, AND ALGORITHMS
The next program takes in five names, sorts them, and displays them in order. The names are stored in a string vector called v; the vector is declared as: vector<string> v
After getting the name from the user you have to push it back into the vector
using: v.push_back(name);
To sort the names use the sort function sort(v.begin(),v.end()); from the algorithm class.
In order to print the vector container we have to create an iterator to loop through the vector: for(vector<string>::iterator p = v.begin(); p != v.end(); p++)
