# My Training Period: xx hours

More <algorithm> member function program examples. Code examples compiled using Microsoft VisualC++ .Net, win32 empty console mode application. g++ compilation on Fedora Core 3 example is given at the end of this Module. The source code for this tutorial is available inC++ STL Algorithm source codes.

4. # Algorithm, lower_bound() program example

35.1  Continuation from the previous Module…

# inplace_merge()

• Combines the elements from two consecutive sorted ranges into a single sorted range, where the ordering criterion may be specified by a binary predicate.

1. template<class BidirectionalIterator>void inplace_merge( BidirectionalIterator _First, BidirectionalIterator _Middle, BidirectionalIterator _Last );

2. template<class BidirectionalIterator, class Pr>void inplace_merge( BidirectionalIterator _First, BidirectionalIterator _Middle, BidirectionalIterator _Last, BinaryPredicate _Comp );

# Parameters

## Parameter

_First

_Middle

_Last

_Comp

#### Table 35.1

• The sorted consecutive ranges referenced must be valid; all pointers must be de-referenceable and, within each sequence, the last position must be reachable from the first by incrementation.

• The sorted consecutive ranges must each be arranged as a precondition to the application of the inplace_merge() algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined ranges.

• The operation is stable as the relative order of elements within each range is preserved. When there are equivalent elements in both source ranges, the element is the first range precedes the element from the second in the combined range.

• The complexity depends on the available memory as the algorithm allocates memory to a temporary buffer. If sufficient memory is available, the best case is linear with (_Last – _First)–1 comparisons; if no auxiliary memory is available, the worst case isN log(N), where N = (_Last–_First).

// algorithm, inplace_merge()

#include <vector>

#include <algorithm>

// for greater<int>()

#include <functional>

#include <iostream>

using namespace std;

// return whether modulus of elem1 is less than modulus of elem2

bool mod_lesser(int elem1, int elem2)

{

if(elem1 < 0)

elem1 = - elem1;

if(elem2 < 0)

elem2 = - elem2;

return (elem1 < elem2);

}

int main()

{

vector <int> vec1;

vector <int>::iterator Iter1, Iter2, Iter3;

// constructing vector vec1 with default less-than ordering

int i;

for(i = 0; i <= 5; i++)

vec1.push_back(i);

int j;

for(j =-5; j <= 0; j++)

vec1.push_back(j);

cout<<"vector vec1 data with subranges sorted by the "<<"binary\npredicate less than is: ";

for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl;

// constructing vector vec2 with ranges sorted by greater

vector <int> vec2(vec1);

vector <int>::iterator break2;

break2 = find(vec2.begin(), vec2.end(), -5);

sort(vec2.begin(), break2, greater<int>());

sort(break2, vec2.end(), greater<int>());

cout<<"\nvector vec2 data with subranges sorted by the "<<"binary\npredicate greater is: ";

for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)

cout<<*Iter2<<" ";

cout<<endl;

// constructing vector vec3 with ranges sorted by mod_lesser

vector <int> vec3(vec1);

vector <int>::iterator break3;

break3 = find(vec3.begin(), vec3.end(), -5);

sort(vec3.begin(), break3, mod_lesser);

sort(break3, vec3.end(), mod_lesser);

cout<<"\nvector vec3 data with subranges sorted by the "<<"binary\npredicate mod_lesser is: ";

for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)

cout<<*Iter3<<" ";

cout<<endl;

vector <int>::iterator break1;

break1 = find(vec1.begin(), vec1.end(), -5);

inplace_merge(vec1.begin(), break1, vec1.end());

cout<<"\nvector vec1merg data, merged inplace with\ndefault order: ";

for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl;

// to merge inplace in descending order, specify binary  predicate greater<int>()

inplace_merge(vec2.begin(), break2, vec2.end(), greater<int>());

cout<<"\nvector vec2merg data, merged inplace with binary\npredicate greater specified: ";

for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)

cout<<*Iter2<<" ";

cout<<endl;

// applying a user defined binary predicate mod_lesser

inplace_merge(vec3.begin(), break3, vec3.end(), mod_lesser);

cout<<"\nvector vec3merg data, merged inplace with binary\npredicate mod_lesser specified: ";

for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)

cout<<*Iter3<<" ";

cout<<endl;

return 0;

}

# Output: # iter_swap()

• Exchanges two values referred to by a pair of specified iterators.

`template<class ForwardIterator1, class ForwardIterator2> void iter_swap( ForwardIterator1 _Left, ForwardIterator2 _Right );`

# Parameters

#### Table 35.2

• swap() should be used in preference toiter_swap(), which was included in the C++ Standard for backward compatibility. If Fit1 and Fit2 are forward iterators, theniter_swap(Fit1, Fit2), is equivalent toswap(*Fit1, *Fit2).

• The value types of the input forward iterators must have the same value.

// algorithm, iter_swap()

#include <vector>

#include <deque>

#include <algorithm>

#include <iostream>

using namespace std;

class CInt;

ostream& operator<<(ostream& osIn, const CInt& rhs);

class CInt

{

public:

CInt(int n = 0) : m_nVal(n){}

CInt(const CInt& rhs) : m_nVal(rhs.m_nVal){}

CInt& operator=(const CInt& rhs)

{ m_nVal = rhs.m_nVal; return *this;}

bool operator<(const CInt& rhs) const

{ return (m_nVal < rhs.m_nVal);}

friend ostream& operator<<(ostream& osIn, const CInt& rhs);

private:

int m_nVal;

};

inline ostream& operator<<(ostream& osIn, const CInt& rhs)

{

osIn<<"CInt(" <<rhs.m_nVal<< ")";

return osIn;

}

// return whether modulus of elem1 is less than modulus of elem2

bool mod_lesser(int elem1, int elem2)

{

if(elem1 < 0)

elem1 = - elem1;

if(elem2 < 0)

elem2 = - elem2;

return (elem1 < elem2);

};

int main()

{

CInt c1 = 9, c2 = 12, c3 = 17;

deque<CInt> deq;

deque<CInt>::iterator deqIter;

deq.push_back(c1);

deq.push_back(c2);

deq.push_back(c3);

cout<<"The deque of CInts data is:\n";

for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)

cout<<" "<<*deqIter<<",";

deqIter = --deq.end();

cout<<" "<<*deqIter<<endl;

// exchanging first and last elements with iter_swap

iter_swap(deq.begin(), --deq.end());

cout<<"\nThe deque of CInts data with first and last\nelements swapped is: ";

for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)

cout<<" "<<*deqIter<<",";

deqIter = --deq.end();

cout<<" "<<*deqIter<<endl;

// swapping back first and last elements with swap

swap(*deq.begin(), *(deq.end() -1));

cout<<"\nThe deque of CInts data with first and last\nelements re swapped is: ";

for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)

cout<<" "<<*deqIter<<",";

deqIter = --deq.end();

cout<<" "<<*deqIter<<endl;

// swapping a vector element with a deque element

vector <int> vec;

vector <int>::iterator Iter1;

deque <int> deq1;

deque <int>::iterator deq1Iter;

int i;

for(i = 10; i <= 14; i++)

vec.push_back(i);

int j;

for(j = 16; j <= 20; j++)

deq1.push_back(j);

cout<<"\nVector vec data: ";

for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl;

cout<<"\nDeque deq1 data: ";

for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)

cout<<*deq1Iter<<" ";

cout<<endl;

iter_swap(vec.begin(), deq1.begin());

cout<<"\nAfter exchanging first elements,\nvector vec data is: ";

for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl<<"and deque deq1 data is: ";

for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)

cout<<*deq1Iter<<" ";

cout<<endl;

return 0;

}

# Output: # lexicographical_compare()

• Compares element by element between two sequences to determine which is lesser of the two.

1. template<class InputIterator1, class InputIterator2>bool lexicographical_compare( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2 );

2. template<class InputIterator1, class InputIterator2, class BinaryPredicate>bool lexicographical_compare( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, BinaryPredicate _Comp );

# Parameters

## Parameter

_First1

_Last1

_First2

_Last2

_Comp

#### Table 35.3

• The return value is true if the first range is lexicographically less than the second range; otherwise false.

• A lexicographical comparison between sequences compares them element by element until:

1. It finds two corresponding elements unequal, and the result of their comparison is taken as the result of the comparison between sequences.

2. No inequalities are found, but one sequence has more elements than the other, and the shorter sequence is considered less than the longer sequence.

3. No inequalities are found and the sequences have the same number of elements, and so the sequences are equal and the result of the comparison is false.

// algorithm, lexicographical_compare()

#include <vector>

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

// return whether second element is twice the first

bool twice(int elem1, int elem2)

{    return (2*elem1) < elem2;    }

int main()

{

vector <int> vec1, vec2;

list <int> lst;

vector <int>::iterator Iter1, Iter2;

list <int>::iterator lst_Iter, lst_inIter;

int i;

for(i = 0; i <= 5; i++)

vec1.push_back(5*i);

int j;

for(j = 0; j <= 6; j++)

lst.push_back(5*j);

int k;

for(k = 0; k <= 5; k++)

vec2.push_back(10*k);

cout<<"Vector vec1 data: ";

for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl;

cout<<"List lst data: ";

for(lst_Iter = lst.begin(); lst_Iter != lst.end(); lst_Iter++)

cout<<*lst_Iter<<" ";

cout<<endl;

cout<<"Vector vec2 data: ";

for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)

cout<<*Iter2<<" ";

cout<<endl;

// self lexicographical_comparison of vec1 under identity

cout<<"\nOperation: lexicographical_compare(vec1.begin(),\nvec1.end(), vec2.begin(), vec2.end()).\n";

bool result1;

result1 = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());

if(result1)

cout<<"Vector vec1 is lexicographically_less than vec2."<<endl;

else

cout<<"Vector vec1 is not lexicographically_less than vec2."<<endl;

// lexicographical_comparison of vec1 and lst under identity

cout<<"\nOperation: lexicographical_compare(vec1.begin(),\nvec1.end(), lst.begin(), lst.end()).\n";

bool result2;

result2 = lexicographical_compare(vec1.begin(), vec1.end(), lst.begin(), lst.end());

if(result2)

cout<<"Vector vec1 is lexicographically_less than lst."<<endl;

else

cout<<"Vector vec1 is lexicographically_less than lst."<<endl;

cout<<"\nOperation: lexicographical_compare(vec1.begin(),\nvec1.end(), vec2.begin(), vec2.end(), twice).\n";

bool result3;

result3 = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), twice);

if(result3)

cout<<"Vector vec1 is lexicographically_less than\nvec2 based on twice."<<endl;

else

cout<<"Vector vec1 is not lexicographically_less than\nvec2 based on twice."<<endl;

return 0;

}

# Output: # lower_bound()

• Finds the position where the first element in an ordered range is or would be if it had a value that is less than or equivalent to a specified value, where the sense of equivalence may be specified by a binary predicate.

1. template<class ForwardIterator, class Type>ForwardIterator lower_bound( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

2. template<class ForwardIterator, class Type, class BinaryPredicate>ForwardIterator lower_bound( ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp );

# Parameters

#### Table 35.4

• The return value is a forward iterator addressing the position where the first element in an ordered range is or would be if it had a value that is less than or equivalent to a specified value, where the sense of equivalence may be specified by a binary predicate.

• The sorted source range referenced must be valid; all pointers must be de-referenceable and within the sequence the last position must be reachable from the first by incrementation.

• The sorted range must each be arranged as a precondition to the application of the lower_bound() algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined ranges.

• The range is not modified by the algorithm merge().

• The value types of the forward iterators need be less-than comparable to be ordered, so that, given two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements

• The complexity of the algorithm is logarithmic for random-access iterators and linear otherwise, with the number of steps proportional to(_Last1 – _First1).

// algorithm, lower_bound()

#include <vector>

#include <algorithm>

//For greater<int>()

#include <functional>

#include <iostream>

using namespace std;

// return whether modulus of elem1 is less than modulus of elem2

bool mod_lesser(int elem1, int elem2)

{

if(elem1 < 0)

elem1 = - elem1;

if(elem2 < 0)

elem2 = - elem2;

return (elem1 < elem2);

}

int main()

{

vector <int> vec1;

vector <int>::iterator Iter1, Result1;

// constructing vectors vec1a & vec1b with default less than ordering

int i;

for(i = -3; i <= 6; i++)

vec1.push_back(i);

int j;

for(j =-5; j <= 2; j++)

vec1.push_back(j);

cout<<"Operation: sort(vec1.begin(), vec1.end()).\n";

sort(vec1.begin(), vec1.end());

cout<<"vector vec1 data with range sorted by the binary predicate\nless than is: ";

for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)

cout<<*Iter1<<" ";

cout<<endl;

// constructing vectors vec2 with range sorted by greater

vector <int> vec2(vec1);

vector <int>::iterator Iter2, Result2;

cout<<"\nOperation: sort(vec2.begin(), vec2.end(), greater<int>()).\n";

sort(vec2.begin(), vec2.end(), greater<int>());

cout<<"vector vec2 data with range sorted by the binary predicate\ngreater is: ";

for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)

cout<<*Iter2<<" ";

cout<<endl;

// constructing vectors vec3 with range sorted by mod_lesser

vector <int> vec3(vec1);

vector <int>::iterator Iter3, Result3;

cout<<"\nOperation: sort(vec3.begin(), vec3.end(), mod_lesser).\n";

sort(vec3.begin(), vec3.end(), mod_lesser);

cout<<"vector vec3 data with range sorted by the "

<<"binary predicate\nmod_lesser is: ";

for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)

cout<<*Iter3<<" ";

cout<<endl;

// lower_bound of 5 in vec1 with default binary predicate less <int>()

cout<<"\nOperation: lower_bound(vec1.begin(), vec1.end(), 5).\n";

Result1 = lower_bound(vec1.begin(), vec1.end(), 5);

cout<<"The lower_bound in vec2 for the\nelement with a value of 5 is: "<<*Result1<<endl;

// lower_bound of 5 in vec2 with the binary predicate greater<int>()

Result2 = lower_bound(vec2.begin(), vec2.end(), 5, greater<int>());

cout<<"The lower_bound in vec2 for the\nelement with a value of 5 is: "<<*Result2<<endl;

// lower_bound of 5 in vec3 with the binary predicate mod_lesser

cout<<"\nOperation: lower_bound(vec3.begin(), vec3.end(), 5, mod_lesser).\n";

Result3 = lower_bound(vec3.begin(), vec3.end(), 5, mod_lesser);

cout<<"The lower_bound in vec3 for the\nelement with a value of 5 is: "<<*Result3<<endl;

return 0;

}

# Output tenouk C++ STL tutorial

# Further C++ STL algorithm related reading:

1. C++ Templates programming tutorials.

2. The source code for this tutorial is available inC++ STL Algorithm source codes.

3. Acomplete C Standard Library.

4. Acomplete C++ Standard Library documentation that includes STL.

5. Check thebest selling C / C++ and STL books at Amazon.com.