Loading....
Coupon Accepted Successfully!

 

Algorithms

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.

adjecent_find( )

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

for_each(vi.begin(),vi.end(),showvalue);

cout<<“\n”;

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

sort_heap( )

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





Test Your Skills Now!
Take a Quiz now
Reviewer Name