We have studied about the template that enables us to do generic programming. Generic functions or classes support all data types. The standard template library is an advance application of templates. It contains several in-built functions and operators that help the programmer develop complex programs. The programmer only needs to include an appropriate header file to use the function or operator from the file, such as library functions. The STL library helps write a bug-free program. In case any bug presents, it is easy to debug it. For example, if a programmer wants to create a link list, he/she may require to write a program that may be of 40 to 50 lines. However, using STL functions (list algorithm), it is a task of 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. 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.
The Meng Lee and Alexander Stepanov of Hewlett-Packard introduced the STL and accepted it 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; and it is reusable. The STL topics are very vast; hence, their 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.
The STL is divided into three parts. They are containers, algorithms, and iterators. All these three parts can be used for different programming problems, and are closely associated with one another.
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 stacks, queues, and priority queues can be created from various sequence containers. Containers are shown in Figure 20.1.
Fig. 20.1 Classification of containers
The STL sequence containers allow controlled sequential access to elements. Sequence containers hold data elements in a linear series, as observed in Figure 20.2. Every element is associated by its location within the series. All these elements enlarge themselves to enable the insertion of elements. These elements also allow various operations, such as copying and finding.
Fig. 20.2 Data items in sequence container.
The STL has three types of sequence containers:
Iterators are used to get the elements in all these containers. All these containers have a different speed.
We know that an array is used to store similar data elements. Elements of the array are stored in successive memory locations and are accessed in order from element number 0 onward. The vector class exactly acts similar to an array. This class is more secure and efficient than arrays.
It is used to insert or delete an element. All the elements are accessed randomly; that is, they support random access to individual elements.
A vector container class is accelerated to enable quick access to its elements in sequence. It is defined in the header file <vector>. A vector is able to enlarge itself. For example, if a vector declared for 5 elements is assigned 6 elements, then the vector automatically develops its size so that it can hold the 6th element. The vector class is declared in the following manner:
template <class TE>, class B =allocator <TE> class vector
Here, the class TE is the type of element in the vector; the class B is an allocator class. M_allocators are responsible for the allocation and release of memory. By default, the new() and delete() operators are also used for the allocation and release of memory. The default constructor of the class TE is invoked to produce a new element. This allows the entry of another parameter in order to define a default constructor for the user defined classes. The vectors that hold integers and floats are declared as follows:
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 follows:
vector<item> sale(15);
The compiler allocates memory for 15 elements. Here, the default constructor item :: item() is used.
The list container enables the programmer to perform the 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 a double-linked list. Every node has a connection to both back and front nodes in the list. The iterator is used to transverse the link. The list class supports all the member functions of the vector class. The elements in the linked list are accessed using pointers. The list container has a technique known as an iterator, which is used to access the elements of the list container. An iterator is similar to a pointer. The iterator can be referenced similar to pointers to access elements.
A deque is similar to a multiple-ended vector. Similar to the vector class, it has the ability 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.
The associative container allows fast access to the object in the container. These containers are useful for huge dynamic tables in which we can search for 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; these containers are divided into four categories:
All the containers listed above hold data elements in a structure called a tree. The tree provides quick finding, deletions, and insertions. These containers perform very slowly in random access operations and are inappropriate for sorting operations.
Container sets and multisets store data elements. They also allow various operations to manage them. The variable name is used as a key name. Suppose a set contains objects of the player class. It can be sorted in ascending order using the names as keys. The multiset may have multiple sets of elements; that is, it permits duplicate data elements. The set does not allow duplicate elements.
Containers map and multimap stores both key names and values. The values are associated with key names. The values can be handled using key names. The values are also called mapped values. Multimaps allow various keys. Map containers permit single keys.
Algorithms are independent template functions. They are not members or friend functions. They enable the programmer to manipulate the data stored in various containers. Algorithms carry out operations on containers by dereferencing iterators. Each container has its functions for performing common operations. An algorithm is nothing but a function template with arguments of iterator type. Algorithms receive iterators as arguments. The iterator informs the algorithm regarding the object of the container on which the operation is to be carried out. In addition, the STL contains approximately 60 standard algorithms. These functions enable 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 20.1 gives non-mutating sequence operations (algorithms).
Table 20.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 in another. |
find( ) |
Searches first presence of a value in a sequence. |
find_end( ) |
Searches last occurrence of a value in a sequence. |
Searches contiguous pair of objects that are identical. |
|
mismatch( ) |
Searches element for which two sequences vary. |
count( ) |
Calculate presence of a value in a sequence. |
count_if( ) |
Calculate elements that similar a predicate |
equal( ) |
True if two series’ are the identical. |
for_each( ) |
Performs a operation with each element. |
Non-mutating sequence algorithms enable operations that do not alter the elements in a sequence. For example, the operators for_each(), find(), search(), and count(). The following program explains how to use the for_each() algorithm:
20.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() ”;
for_each(vi.begin(),vi.end(),showvalue);
cout<<“ ”;
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 the first for loop, 0 to 3 numbers are inserted in the vector. While reading numbers from the vector instead of using the for loop, the operator for_each() is used. The first argument of in for_each() operator (vi.begin()) gives the reference of the first element. The second argument gives the reference of the last element of the vector, and the third argument (showvalue) is a function object. Thus, using the for_each() operator, members of the vector can be accessed.
20.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() ”;
for_each(vi.begin(),vi.end(),showvalue);
cout<<“ ”;
return 0;
}
OUTPUT
55667777
Explanation: This program is similar to the previous one. In addition, 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 element in the vector:
fill(vi.begin(),vi.begin() + 2,5);
The above statement fills the first 2 elements with the value 5. The function begin() gives a beginning reference, and begin() + 2 gives a reference for the second.
fill(vi.begin()+2,vi.begin() + 4,6);
The above statement fills the value 6 at the third and fourth locations of the vector. Here also, the begin() function is used.
fill(vi.begin()+4,vi.end(),7);
The above statement fills the value 7 from location number 5 to the end. Table 20.2 describes sorting operations (algorithms).
Table 20.2 Sorting operations
Operators |
Use |
---|---|
binery_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 sequence |
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 |
Sorts a heap |
|
stable_partion( ) |
Puts elements matching an estimate first matching relative order |
stable_sort( ) |
Sorts arranging order of similar elements |
upper_bound( ) |
Searches the last occurrence of a given value |
Table 20.3 describes mutating sequence operations (algorithms).
Table 20.3 Mutating sequence operations
Operators |
Use |
---|---|
swap_ranges( ) |
Exchange two sequences |
generate( ) |
Substitutes all elements with the result of an operation |
copy_backward( ) |
Duplicate (copies) a sequence from the ends |
fill( ) |
Fill up a series with a given value |
reverse( ) |
Opposites (reverse) the order of elements |
fill_n( ) |
Fill 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( ) |
Substitute 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 a sequence into rotate sequence |
swap( ) |
Exchange two elements |
reverse_copy( ) |
Copies a sequence into opposite direction |
Numeric algorithms are provided in Table 20.4
Table 20.4 Numeric operations
Operators |
Use |
---|---|
Inner_product( ) |
Collects the details of operation on a pair of sequence |
Adjacent_difference( ) |
Creates a sequence from another sequence |
Accumulate( ) |
Collects the return values of operation on a sequence |
partial_sum( ) |
Creates a sequence by applying an operation on a pair of sequence |
Iterators acts as pointers. They are used for accessing contents of container classes. They allow movement from one element to another element, and this is known as iterating. Each container type supports one kind of iterator according to the container’s necessity. The types are input, output, forward, bi-directional, and random access. The hierarchy of iterators is shown in Figure 20.3 and described in Tables 20.5 and 20.6.
Fig. 20.3 Iterator hierarchy
Table 20.5 Operation of container classes
Table 20.6 Iterator status
Iterator status |
Meaning |
---|---|
singular |
The value of iterator does not dereference 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 object in the container. |
Iterators are used by the algorithms to carry out operations. Iterators are smart pointers. They are allowed to contain values that indicate one of the statuses of iterators as described in Table 20.10. Each iterator type supports all the attributes listed in Table 20.9 and shown in Figure 20.3. Iterators can be incremented, decremented, and their limits are up to the capacity of the containers. Containers have member functions that return iterators.
20.3 Write a program to transverse list using iterator.
#include<iostream>
#include<list>
using namespace std;
typedef list<int> num_list;
int main()
{
num_list num;
for (int j=0;j<=5;++j)
num.push_back(j);
for (num_list::const_iterator ls=num.begin(); ls!=num.end();++ls)
cout<<*ls<<“”;
return 0;
}
OUTPUT
0 1 2 3 4 5
Explanation: In the above program, num is an object of type num_list. The member function push_back() adds a number in the list. In the for loop, the statement num_list::const_iterator ls = num.begin(); declares an iterator ls and initializes with the beginning reference of the list (reference of the first element). The second statement ls! = num.end() continues the loop until the ls points to the last element of the list. The statement ++ls dereference the iterator so that successive numbers are accessed.
A vector is a more useful container. Similar to an array, it also stores elements in neighboring memory locations. Each element can be directly accessed using the operator[]. A vector is able to enlarge its size if an extra element is assigned to it. A class vector has various constructors that can be used to create vector objects.
The vector class supports various functions and they are listed in Table 20.7.
Table 20.7 Functions of vector class
Function |
Use |
---|---|
swap( ) |
Swap the elements in the given two vector |
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 elements |
insert( ) |
Inserts items (elements) in the vector |
erase( ) |
Erases given elements |
end( ) |
Provides reference to the end of the vector |
empty( ) |
Determine whether the vector is empty |
clear( ) |
Erases entire elements from the vector |
capacity( ) |
Provides the present capacity (limit) of the vector |
begain( ) |
Provides a reference to the starting element |
back( ) |
Provides a reference to the last element |
at( ) |
Provides a reference to an element |
20.4 Write a program to add and display elements in the vector object.
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> e;
e.push_back(5);
e.push_back(8);
e.push_back(9);
cout<<“ The elements are : ”<<“ ”;
cout<<e[0]<<“”;
cout<<e[1]<<“”;
cout<<e[2]<<“”;
return 0;
}
OUTPUT
The elements are :
5 8 9
Explanation: In the above program, e is an object of the vector class that can hold data of integer type. The member function push_back() is used to add the element in the vector object. Three integer elements 5, 8, and 9 are added to the vector. These elements are stored in contiguous memory locations. These elements can be accessed in the same manner as we access the array elements. The vector object name followed by the element number in the [ ] operator displays the specified number. Here, the overloaded operator [ ] is used.
20.5 Write a program to insert an element in the vector object. Use member function and iterator.
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> e;
for (int x=0;x<3;x++)
e.push_back(x+1);
cout<<“ The elements are:”<<“ ”;
for (x=0;x<3;x++)
cout<<e[x]<<“”;
vector <int> :: iterator it =e.begin();
it=it+1;
e.insert(it,7);
cout<<“ The elements after insertion:”<<“ ”;
for (x=0;x<4;x++)
cout<<e[x]<<“”;
return 0;
}
OUTPUT
The elements are :
1 2 3
The elements after insertion :
1 7 2 3 Press any key to continue
Explanation: In the above program, the first for loop and the function push_back() add elements to the object e. The elements indicated by the loop variable x are stored in the object e. The second for loop and cout() statement display the contents of the object e.
The it is an iterator. The statement vector <int> :: iterator it = e.begin() declares the iterator. The iterator acts similar to a pointer. The begin() function is used to assign the reference (address) of the first element. The statement it = it+1 assigns the address of the second element where the element is to be inserted. The member function is invoked with two arguments as per the g statement e.insert (it, 7).
The first argument is an iterator that indicates the location, and the second argument is an integer value. The number 7 is inserted at the location indicated by the iterator it. The last for loop displays the contents of the vector object e after insertion.
20.6 Write a program to display the elements of vector object in ascending and descending orders.
#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> e;
cout<<“Elements in ascending order:”;
for (int x=0;x<8;x++)
{
e.push_back(x+1);
cout<<x+1 <<“”;
}
int s=e.size()-1;
cout<<“ Elements in descending order:”;
for (int j=s;j>=0;j--)
cout<<e[j]<<“”;
cout<<“ ”;
return 0;
}
OUTPUT
Elements in ascending order : 1 2 3 4 5 6 7 8
Elements in descending order : 8 7 6 5 4 3 2 1
Explanation: In the above program, the first for loop and the member function push_back() are used to add numbers in the vector element e. The cout() statement in the same loop displays the elements. All the elements are stored and displayed in ascending order. The member function size() returns the total number of the elements. The total number of the elements is stored in the integer variable s. The second for loop is executed in reverse order, and the value of the loop variable j is used with the object e to display the number. Thus, all the numbers are displayed in the reverse order.
20.7 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<<“ 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;
}
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 the vector that is capable of storing float values. The square roots of 5 to 12 numbers are stored in the object e. The erase() function erases the 4th and 5th elements. The variable ir is an iterator that gives the reference of the element. The erase() can be used with one or more argument. The last for loop displays the elements after deletion.
20.8 Write a program to declare a vector object. Add elements and display them. Use member functions.
#include<iostream>
#include<vector>
{
for (int j=0;j<e.size();j++)
{ cout<<e[j];
cout<<“ ”;
}
}
int main()
{
vector<int> e;
cout<<“Initial size of e= ” <<e.size() <<“ ”;
int k;
cout<<“ Enter five integers values:”;
for (int j=0;j<3;j++)
{
cin>>k;
e.push_back(k);
}
cout<<“ Size of e after adding 3 values:”;
cout<<e.size();
cout<<“ current contents:”<<“ ”;
show(e);
return 0;
}
OUTPUT
Initial size of e= 0
Enter five integers values : 7 3 4
Size of e after adding 3 values : 3
Current contents :
7 3 4
Explanation: In the above program, e is an object of the vector class that is capable of storing integer values. The size() member function gives the number of elements stored in the object e. The for loop and the cin statement within it reads three integers through the keyboard. The member function push_back() adds the element to the object e. It adds the element at the end. After adding elements again, the size() function displays the number of elements. It displays 3, that is the number of total elements added in the object e. The show() function is used to display the contents of the object e. The for loop and the statement cout <<e[j] are used to display the elements. The overloaded operator [ ] is used to access the specified element by the variable j.
The list is a frequently used feature. It allows a bi-directional linear list. Element can be inserted or deleted at both the ends. The elements in the list can be accessed sequentially. Iterators are used for accessing individual elements of the list.
The list class supports various functions and they are listed in Table 20.8.
Table 20.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 |
begain( ) |
Provides reference to the first element |
erase( ) |
Erases given element |
end( ) |
Provides reference of the end element of the list |
merge( ) |
Combines two sorted lists |
pop_fornt( ) |
Erases the first elements |
pop_back( ) |
Erases the last elements |
remove( ) |
Erases elements as specified |
reverse( ) |
Reverse the list elements |
insert( ) |
Adds given element |
push_back( ) |
Appends an element to the end |
push_front( ) |
Appends an element to the front |
size( ) |
Provides the sizes of the list |
unique( ) |
Erases the 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 |
20.9 Write a program to create list of four numbers 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(5);
list.push_back(10);
list.push_back(15);
list.push_back(20);
cout<<“Numbers are”;
show(list);
return 0;
}
OUTPUT
Numbers are 5 10 15 20
Explanation: In the above program, list is the object of list container class that is able to hold integer values. The push_back() functions adds elements to the list. Four integer numbers are added in the list. The show() function is used to display the numbers on the screen. The num reference variable receives the reference of the first element. The iterator n is used to display the numbers. It is used exactly as a pointer.
20.10 Write a program to add element to both 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<<“ Numbers are”;
list.push_front(1);
list.push_back(25);
cout<<“ After adding Numbers are”;
show(list);
return 0;
}
OUTPUT
Numbers are 50 10 15 20
After adding Numbers are 1 5 10 15 20 25
Explanation: The above program is similar to the previous one. In addition, here two elements are added to the front and rear ends of the list. The function push.front() adds elements to the front end of the list, and the function push_back() appends elements to the rear end of the list. The output shows all the elements of the list.
20.11 Write a program to delete elements from 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”;
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 function pop.back() is used to delete the back element of the list. The output shows the list of numbers.
20.12 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<<“ Unsorted list:”;
show(list);
cout<<“ Sorted list:”;
list.sort();
show(list);
return 0;
}
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 elements in sorted and unsorted elements using the show() function.
20.13 Write a program to display the elements in reverse order.
#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<<“ Original list:”;
show(list);
cout<<“ Reverse list:”;
list.reverse();
show(list);
return 0;
}
OUTPUT
Original list :23 19 5 15 25 20
Reverse list : 20 25 15 5 19 23
Explanation: The above program is similar to a previous one. Here, the reverse() function arranges the list elements in reverse order. The output shows the list of elements in original and reversed order.
20.14 Write a program to copy elements of one list object to another object. Display the contents of both the objects.
#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);
listX.push_back(15);
listX.push_back(25);
listX.push_back(20);
listY=listX;
cout<<“ Elements of listX:”;
show(listX);
cout<<“ Elements of listY:”;
show(listY);
return 0;
}
OUTPUT
Elements of listX :23 19 5 15 25 20
Elements of listY :23 19 5 15 25 20
Explanation: In the above program, listX and listY are two objects of the list container. The listX is initialized with six integer elements using the push_back() functions. The statement listY = listX copies elements of the listX object to the listY object.
20.15 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<< Elements of listX:;
show(listX);
cout<< Elements of listY:;
show(listY);
listX.merge(listY);
cout<< 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 objects 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 the elements of listY. In the output, the contents of objects listX and listY are displayed.
A map is a series of pairs of key names and values associated with it as per Figure 20.4. Access of data values depends on the key, and it is very quick. We should specify the key to get the corresponding value.
Fig. 20.4 Key and values in maps
20.16 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 no number for 2 items: ”;
for (int i=0;i<2;i++)
{
cin>>item_name;
cin>>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;
}
OUTPUT
Enter item name and code no number 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, a map variable is created. The first for loop and cin statement read two records through the keyboard. Using the 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 produce the list of item names and code numbers. At the end, the program displays a code number that is associated with the entered item name. The item_name is a key. The list is automatically arranged in sorted order.
A map is generally also known as an associative array. The key is given with the help of the subscript operator [ ] in the following manner:
item[“PC”]=2510;
The above statement creates a 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() delete() function performs these tasks. Frequently used functions are described in Table 20.10.
20.17 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<<“ Size of map:”<<sz <<“ ”;
item.clear();
sz=item.size();
cout<<“ after clear() Size of map:”<<sz <<“ ”;
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 the size() function, the size (total number of records) is displayed; that is, the clear() function clears the contents of the map. After the clear() function, the size of the map becomes zero.
Table 20.9 describes important functions of map class.
Table 20.9 Important functions of the map class
Function |
Task |
---|---|
clear( ) | Removes all elements from the map |
begin( ) | Provides references of 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 references 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 |
A function object is a function. It is embedded in a class and hence behaves similar to an object. The class has same characteristics of a template and can be put to use with different data types. The class holds 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>( ));
where num[] is an array. We can use an 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 that match 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 Tables 20.10, 20.11, and 20.12 are defined in the functional header file.
Table 20.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 20.11 Logical function objects
Function object |
Narration |
---|---|
logical_and<K> |
a && b |
logical_not<K> |
! a |
logical _or<K> |
a | | b |
Table 20.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 |
20.18 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<<“ ”;
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;
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. Elements of two arrays are sorted by sort()function. The array a[ ] is sorted with the help of the function object greater<float>, and the array b[ ] is sorted without the 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 are displayed.
20.19 Write a program to create function object.
#include<iostream>
using namespace std;
template <class S>
class show
{
public:
void operator() ( const S& s)
{
cout<<s;
}
};
int main()
{
show<int> showvalue;
for (int j=0;j<8;++j) showvalue(j);
}
OUTPUT
01234567
Explanation: In the above program, the operator() is overloaded in the class show. The showvalue is an object of the class show. The overloaded operator() can be used with an object of the class show type similar to the statement showvalue(j); to display the value; so, it is called a function object.
(A) Answer the following questions
(B) Answer the following by selecting the appropriate option
(C) Attempt the following programs