17. Overview of Standard Template Library (STL) – Object-Oriented Programming with ANSI and Turbo C++

17

CHAPTER

Overview of Standard Template Library (STL)

C
H
A
P
T
E
R

O
U
T
L
I
N
E
—•    17.1 Introduction to STL
—•    17.2 STL Programming Model
—•    17.3 Containers
—•    17.4 Sequence Containers
—•    17.5 Associative Containers
—•    17.6 Algorithms
—•    17.7 Iterators
—•    17.8 Vector
—•    17.9 List
—•  17.10 Maps
—•  17.11 Function Objects

 

 

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

Operators Use
search_n( ) Searches a sequence of a given number of same elements.
find_if ( ) Searches first equivalent of a predicate in a sequence.
search( ) Searches sub-sequence in other sequence.
find_first_of ( ) Searches a value from one sequence to another.
find( ) Searches first presence of a value in a sequence.
find_end( ) Searches last occurrence of a value in a sequence.
adjacent_find( ) Searches contiguous pair of objects that are identical.
mismatch( ) Searches elements for which two sequences vary.
count( ) Calculates presence of a value in a sequence.
count_if( ) Calculates elements that are similar to a predicate.
equal( ) True if two series’ are identical.
for_each( ) Performs an operation with each element.

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.

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

# 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( ) \n";


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


}

OUTPUT

 

0123

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.

17.2 Write a program to demonstrate use of fill( ) 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(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( ) \n";

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

OUTPUT

55667777

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

Operators Use
binary_search( ) Performs a binary search on an indexed sequence
equal( ) Searches whether two sequences are equal
equal_range( ) Searches a sub-range of elements with a specified value
includes( ) Searches if a sequence is a sub-sequence of another sequence
inplace_merge( ) Combines two successive sorted sequences
lexicographical_compare( ) Compares in ascending order one sequence with other
lower_bound( ) Searches the first occurrence of a given value
make_heap( ) Makes a heap from a sequence
max( ) Returns greatest of two values
max_element( ) Returns the highest elements inside a sequence
merge( ) Combines two sorted sequences
min( ) Returns smallest of two values
min_element( ) Returns the smallest number of a sequence
mismatch( ) Searches the mismatch among the elements of two sequences
nth_elements( ) Places given elements in its appropriate places
partial_sort( ) Sorts a portion of a sequence
partial_sort_copy( ) Sorts a portion of a sequence and copies
pop_heap( ) Erases the uppermost elements
push_heap( ) Appends or adds an element to heap
set_difference( ) Builds a sequence that is the variance of two ordered sets
set_intersection( ) Makes a sequence that holds the intersection of ordered sets
set_symmetric_difference( ) Yields a set that is the symmetric variance between two ordered sets
set_union( ) Yields sorted union of two ordered sets
sort( ) Sorts the sequence container
sort_heap( ) Sorts a heap
stable_partion( ) Puts elements matching a predicate by first matching comparative order
stable_sort( ) Sorts arranging order of similar elements
upper_bound( ) Searches the last occurrence of a given value

Table 17.3 describes mutating sequence operations.

Table 17.3 Mutating sequence operations

Operators Use
swap_ranges( ) Exchanges two sequences
generate( ) Substitutes all elements with the result of an operation
copy_backward( ) Duplicates (copies) a sequence from the ends
fill( ) Fills up a series with a given value
reverse( ) Opposites (reverses) the order of elements
fill_n( ) Fills up first n elements with a given value
copy( ) Duplicates (copies) a sequence
unique( ) Erases similar contiguous elements
generate_n( ) Substitutes first n elements with the result of an operation
iter_swap( ) Exchanges elements pointed to by iterator
random_shuffle( ) Inserts elements in random order
remove( ) Erases elements of a given value
replace( ) Substitutes elements with a specified value
replace_if( ) Substitutes elements matching a predicate
remove_copy_if( ) Duplicates (copies) a sequence subsequently removing elements matching a predicate
unique_copy( ) Copies after removing similar contiguous elements
rotate( ) Rotates (turns) elements
remove_if( ) Erases elements matching a predicate
remove_copy( ) Duplicates (copies) a sequence subsequently removing a given value
replace_copy( ) Duplicates (copies) a sequence substituting elements with a specified value
transform( ) Applies an action to all elements
replace_copy_if( ) Duplicates (copies) a sequence substituting elements matching a predicate
rotate_copy( ) Issues (copies) a sequence into a rotated
swap( ) Exchanges two elements
reverse_copy( ) Copies a sequence into opposite direction

Table 17.4 describes numeric operations.

Table 17.4 Numeric operations

Operators Use
inner_product( ) Collects the details of operations on a pair of sequence
adjacent_difference( ) Creates a sequence from another sequence
accumulate( ) Collects the return values of operations on a sequence
partial_sum( ) Creates a sequence by applying an operation on a pair of sequence

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

Iterator Access mode Way of action I /O ability Comments
Forward
Bi-directional
Random
Input
Output
Linear
Linear
Random
Linear
Linear
Can move forward only
Can move front and back
Can move front and back
Can move forward only
Can move forward only
Can write and read
Can write and read
Can write and read
Can read only
Can write only
Storable
Storable
Storable
Non-storable
Non-storable

Table 17.6 Iterator status

Iterator status Meaning
Singular The value of iterator is not dereferenced in any container.
Past-the-end The iterator addresses to the object past the last object in the container.
Dereferenceable The iterator addresses the legal objects in the container.

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

Function Use
swap( ) Swaps the elements in the two given vectors
size( ) Provides the number of elements
resize( ) Changes the size of the vector
push_back( ) Appends an element to the end
pop_back( ) Erases the last element
insert( ) Inserts items (elements) in the vector
erase( ) Erases given elements
end( ) Provides reference to the end of the vector
empty( ) Determines whether the vector is empty
clear( ) Erases entire elements from the vector
capacity( ) Provides the present capacity (limit) of the vector
begin( ) Provides reference to the starting element
back( ) Provides reference to the last element
at ( ) Provides reference to an element

17.3 Write a program to remove elements from vector object.

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


int main( )
{
       vector<float> e;
       cout.precision(2);
       cout <<"\n 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 <<"\n The elements after erase( ) : ";
       for (k=0;k<s;k++)
       cout <<e[k]<<"  ";
       cout <<"\n";

  return 0; 
}

OUTPUT

 

Original elements    : 2.2 2.4 2.6 2.8 3 3.2 3.3

The elements after erase( ) : 2.2 2.4 2.6 3.2 3.3

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

Function Task
clear( ) Erases entire elements
back( ) Provides reference to the end elements
empty( ) Determines if the list is vacant or not
begin( ) Provides reference to the first element
erase( ) Erases given elements
end( ) Provides reference to the end element of the list
merge( ) Combines two sorted lists
pop_front( ) Erases the first elements
pop_back( ) Erases the last elements
remove( ) Erases elements as specified
reverse( ) Reverses the list elements
insert( ) Adds given elements
push_back( ) Appends an element to the end
push_front( ) Appends an element to the front
size( ) Provides the size of the list
unique( ) Erases identical elements in the list
resize( ) Changes the size of the list
swap( ) Swaps the element of a list with those in the calling list
sort( ) Sorts the list elements

17.4 Write a program to add elements to both the ends of the list and display the 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(5);
list.push_back(10);
list.push_back(15);
list.push_back(20);


cout<<"\nNumbers are ";
show(list);
list.push_front(1);
list.push_back(25);
cout<<"\nAfter adding numbers are ";
show(list);
return 0;
}

OUTPUT

Numbers are 5 10 15 20

After adding numbers are 1 5 10 15 20 25

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.

17.5 Write a program to delete elements from both ends 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<<"\nNumbers are ";
  show(list);
  list.pop_front( );
  list.pop_back( );
  cout<<"\nAfter deleting numbers are ";
  show(list);
  return 0;
}

OUTPUT

Numbers are 5 10 15 20

After deleting numbers are 10 15

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.

17.6 Write a program to sort the list elements and display them.

# 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<<"\n Unsorted list :";
show(list);
cout<<"\n Sorted   list : ";
list.sort( );
show(list);
return 0;
}

OUTPUT

 Unsorted list :23 19 5 15 25 20

 Sorted list : 5 15 19 20 23 25

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.

17.7 Write a program to merge two lists and display the merged 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> 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<<"\n Elements of listX :";
  show(listX);
  cout<<"\n Elements of listY :";
  show(listY);


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

OUTPUT

Elements of listX :23 19 5

Elements of listY :15 25 20

Merged list : 15 23 19 5 25 20

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

17.8 Write a program to manipulate list of item names and their code numbers using 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: \n";
     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<<"\n Size of map :"<<sz <<"\n\n";
     cout <<"List of item name and code numbers \n";
     item_map::iterator t;
     for ( t=item.begin( );t!=item.end( );t++)
       cout <<(*t).first <<" " <<(*t).second<<"\n";cout <<"\n";
     cout <<"Enter item name : ";
     cin>>item_name;
     codeno=item[item_name];
     cout <<"Code Number : "<<codeno <<"\n";
     return 0;
}

OUTPUT

 

Enter item name and code for 2 items:

TV 51

CD 52

 

 Size of map :4

 

List of item name and code numbers

CD 52

PC 2510

TV 51

printer 2211

 

Enter item name : PC

Code Number : 2510

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.

17.9 Write a program to clear map using clear( ) function.

# 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<<"\n Size of map :"<<sz <<"\n\n";


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


     cout<<"\n after clear ( ) Size of map :"<<sz <<"\n\n";
     return 0;
}

OUTPUT

 

Size of map :2

after clear ( ) Size of map :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

Function Task
clear( ) Removes all elements from the map
begin( ) Provides reference to the first element
erase( ) Removes the given elements
insert( ) Inserts the elements as given
empty( ) Determines whether the map is vacant or not
end( ) Provides reference to the end of the map
size( ) Provides the size of the map
find( ) Provides the location of the given elements
swap( ) Swaps the elements of the given map with those of the calling map

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

Function object Narration
not_equal_to<K> a != b
equal_to<K> a = = b
greater<K> a > b
greater_equal<K> a >= b
less<K> a < b
less_equal<K> a <= b

Table 17.11 Logical function objects

Function object Narration
logical_and<K> a && b
logical_not<K> ! a
logical_or<K> a | | b

Table 17.12 Arithmetic function objects

Function object Narration
plus<K> a + b
divides<K> a / b
modulus<K> a % b
multiplies<K> a * b
minus<K> a – b
negate<K> - a

17.10 Write a program to sort an array using function object.

# 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 <<"\n";


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


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


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

OUTPUT

6.5 2.5 1.5

1.4 4.8 6.4

1.4 4.8 6.4 6.5 2.5 1.5

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.