|< C++ STL Algorithm 2 | Main | C++ STL Algorithm 4 >|Site Index |Download |
MODULE 34_1
THE C++ STL ALGORITHM PART 3
My Training Period: hours
Continue from the previous Module, more algorithm member functions program examples. Compiled using MicrosoftVisual C++/.Net, win32 empty console mode application. g++ compilation on Fedora Core 3 examples given at the end of this Module. Source code in text is available inC++ Algorithm source code sample.
The C++ STL algorithm knowledge that supposed to be acquired:
-
Able to understand and use the member functions of the algorithm class.
-
Appreciate the usage of the template classes and functions.
-
Able to use containers, iterators and algorithm all together.
What do we have in this session?
Algorithm, copy_backward() program example
Algorithm, count() program example
Algorithm, count_if() program example
Algorithm, the countif() program example
Algorithm, equal() program example
Algorithm, equal_range() program example
| copy_backward()
template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward( BidirectionalIterator1 _First, BidirectionalIterator1 _Last, BidirectionalIterator2 _DestEnd );
Parameters
| ||||||||||
// algorithm, copy_backward()
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
vector <int> vec1, vec2;
vector <int>::iterator Iter1, Iter2;
int i;
for(i = 10; i <= 15; i++)
vec1.push_back(i);
int j;
for(j = 0; j <= 10; j++)
vec2.push_back(j);
cout<<"vec1 data: ";
for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
cout<<"vec2 data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
// to copy_backward the first 4 elements of vec1 into the middle of vec2
copy_backward(vec1.begin(), vec1.begin() + 4, vec2.begin() + 8);
cout<<"vec2 with vec1 insert data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
// to shift the elements inserted into vec2 two positions to the right
copy_backward(vec2.begin()+4, vec2.begin()+7, vec2.begin()+9);
cout<<"vec2 with shifted insert data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
return 0;
}
Output:
count()
Returns the number of elements in a range whose values match a specified value.
template<class InputIterator, class Type>typename iterator_traits<InputIterator>::difference_type count( InputIterator _First,
InputIterator _Last, const Type& _Val );
Parameters
Parameter | Description |
_First | An input iterator addressing the position of the first element in the range to be traversed. |
_Last | An input iterator addressing the position one past the final element in the range to be traversed. |
_Val | The value of the elements to be counted. |
Table 34.6 | |
The return value is the difference type of the InputIterator that counts the number of elements in the range [_First, _Last) that have value _Val.
Theoperator== used to determine the match between an element and the specified value must impose an equivalence relation between its operands.
This algorithm is generalized to count elements that satisfy any predicate with the template function count_if().
// algorithm, count()
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
vector <int> vec;
vector <int>::iterator Iter;
vec.push_back(12);
vec.push_back(22);
vec.push_back(12);
vec.push_back(31);
vec.push_back(12);
vec.push_back(33);
cout<<"vec data: ";
for(Iter = vec.begin(); Iter != vec.end(); Iter++)
cout<<*Iter<<" ";
cout<<endl;
int result;
cout<<"\nOperation: count(vec.begin(), vec.end(), 12)\n";
result = count(vec.begin(), vec.end(), 12);
cout<<"The number of 12s in vec is: "<<result<<endl;
return 0;
}
Output:
count_if()
Returns the number of elements in a range whose values satisfy a specified condition.
template<class InputIterator, class Predicate>typename iterator_traits<InputIterator>::difference_typecount_if(
InputIterator _First, InputIterator _Last, Predicate _Pred );
Parameters
Parameter | Description |
_First | An input iterator addressing the position of the first element in the range to be searched. |
_Last | An input iterator addressing the position one past the final element in the range to be searched. |
_Pred | User-defined predicate function object that defines the condition to be satisfied if an element is to be counted. A predicate takes single argument and returns true or false. |
Table 34.7 | |
The return value is the number of elements that satisfy the condition specified by the predicate.
This template function is a generalization of the algorithmcount(), replacing the predicate "equals a specific value" with any predicate.
// algorithm, count_if()
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool isgreat(int value)
{ return value >8; }
int main()
{
vector <int> vec;
vector <int>::iterator Iter;
vec.push_back(13);
vec.push_back(21);
vec.push_back(9);
vec.push_back(31);
vec.push_back(8);
vec.push_back(10);
cout<<"vec data: ";
for(Iter = vec.begin(); Iter != vec.end(); Iter++)
cout<<*Iter<<" ";
cout<<endl;
int result1;
cout<<"\nOperation: count_if(vec.begin(), vec.end(), isgreat)\n";
result1 = count_if(vec.begin(), vec.end(), isgreat);
cout<<"The number of elements in vec greater than 8 is: "<<result1<<endl;
return 0;
}
Output:
count_if()
template<class InputIterator, class Predicate> inline size_t count_if(InputIterator First, InputIterator Last, Predicate P );
// algorithm, the countif() // functions: // count_if() - Count items in a range that satisfy a predicate. // begin() - Returns an iterator that points to the first element in a sequence. // end() - Returns an iterator that points one past the end of a sequence. #include <iostream> #include <algorithm> #include <functional> #include <string> #include <vector> using namespace std; |
// return true if string str starts with letter 'C'
int MatchFirstChar(const string& str)
{
string s("C");
return s == str.substr(0, 1);
}
int main()
{
const int VECTOR_SIZE = 110;
// define a template class vector of strings
typedef vector<string > StringVector;
// define an iterator for template class vector of strings
typedef StringVector::iterator StringVectorIt;
// vector containing names
StringVector NamesVect(VECTOR_SIZE);
StringVectorIt start, end, it;
// stores count of elements that match value.
ptrdiff_t result = 0;
// initialize vector NamesVect
NamesVect[0] = "Learn";
NamesVect[1] = "C";
NamesVect[2] = "and";
NamesVect[3] = "C++";
NamesVect[4] = "also";
NamesVect[5] = "Visual";
NamesVect[6] = "C++";
NamesVect[7] = "and";
NamesVect[8] = "C++";
NamesVect[9] = ".Net";
// location of first element of NamesVect
start = NamesVect.begin();
// one past the location last element of NamesVect
end = NamesVect.end();
// print content of NamesVect
cout<<"NamesVect: ";
for(it = start; it != end; it++)
cout<<*it<<" ";
cout<<endl;
// count the number of elements in the range [first, last +1) that start with letter 'C'
result = count_if(start, end, MatchFirstChar);
// print the count of elements that start with letter 'S'
cout<<"Number of elements that start with letter \"C\" = "<<result<<endl;
}
Output:
equal()
Compares two ranges element by element either for equality or equivalence in a sense specified by a binary predicate.
template<class InputIterator1, class InputIterator2>bool equal( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2 );
template<class InputIterator1, class InputIterator2, class BinaryPredicate>bool equal( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, BinaryPredicate _Comp );
Parameters
Parameter | Description |
_First1 | An input iterator addressing the position of the first element in the first range to be tested. |
_Last1 | An input iterator addressing the position one past the final element in the first range to be tested. |
_First2 | An input iterator addressing the position of the first element in the second range to be tested. |
_Comp | User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. |
Table 34.8 | |
The return value is true if and only if the ranges are identical or equivalent under the binary predicate when compared element by element; otherwise, false.
The range to be searched must be valid; all pointers must be de-referenceable and the last position is reachable from the first by incrementation.
The time complexity of the algorithm is linear in the number of elements contained in the range.
Theoperator== used to determine the equality between elements must impose an equivalence relation between its operands.
// algorithm, equal()
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// return whether second element is twice of the first
bool twice(int elem1, int elem2)
{ return elem1 * 2 == elem2; }
int main()
{
vector <int> vec1, vec2, vec3;
vector <int>::iterator Iter1, Iter2, Iter3;
int i;
for(i = 10; i <= 15; i++)
vec1.push_back(i);
int j;
for(j = 0; j <= 5; j++)
vec2.push_back(j);
int k;
for(k = 10; k <= 15; k++)
vec3.push_back(k);
cout<<"vec1 data: ";
for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
cout<<"vec2 data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
cout<<"vec3 data: ";
for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)
cout<<*Iter3<<" ";
cout<<endl;
// testing vec1 and vec2 for equality based on equality
bool b;
b = equal(vec1.begin(), vec1.end(), vec2.begin());
if(b)
cout<<"The vectors vec1 and vec2 are equal based on equality."<<endl;
else
cout<<"The vectors vec1 and vec2 are not equal based on equality."<<endl;
// testing vec1 and vec3 for equality based on equality
bool c;
c = equal(vec1.begin(), vec1.end(), vec3.begin());
if(c)
cout<<"The vectors vec1 and vec3 are equal based on equality."<<endl;
else
cout<<"The vectors vec1 and vec3 are not equal based on equality."<<endl;
// testing vec1 and vec3 for equality based on twice
bool d;
d = equal(vec1.begin(), vec1.end(), vec3.begin(), twice);
if(d)
cout<<"The vectors vec1 and vec3 are equal based on twice."<<endl;
else
cout<<"The vectors vec1 and vec3 are not equal based on twice."<<endl;
return 0;
}
Output:
equal_range()
Finds a pair of positions in an ordered range, the first less than or equivalent to the position of a specified element and the second greater than the element's position, where the sense of equivalence or ordering used to establish the positions in the sequence may be specified by a binary predicate.
template<class ForwardIterator, class Type>pair<ForwardIterator, ForwardIterator> equal_range( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );
template<class ForwardIterator, class Type, class Pr>pair<ForwardIterator, ForwardIterator> equal_range( ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp );
Parameters
Parameter | Description |
_First | A forward iterator addressing the position of the first element in the range to be searched. |
_Last | A forward iterator addressing the position one past the final element in the range to be searched. |
_Val | The value in the ordered range that needs to be equivalent to the value of the element addressed by the first component of the pair returned and that needs to be less than the value of the element addressed by the second component of that pair returns. |
_Comp | User-defined predicate function object that is true when the left-hand argument is less than the right-hand argument. The user-defined predicate function should return false when its arguments are equivalent. |
Table 34.9 | |
The return value is a pair of forward iterators addressing two positions in an ordered range in which the first component of the pair refers to the position where an element is or would be if it had a value that is less than or equivalent to a specified value and the second component of the pair refers to the first position where an element has a value that is greater than the value specified, where the sense of equivalence or ordering may be specified by a binary predicate.
Alternatively, the pair of forward iterators may be described as specify a sub range, contained within the range searched, in which all of the elements are equivalent to the specified value in the sense defined by the binary predicate used.
The first component of the pair of the algorithm returnslower_bound(), and the second component returnsupper_bound().
The sub range defined by the pair of iterators returned by theequal_range() algorithm contains the equivalence class, in the standard set-theoretic sense, of the element whose value is specified as a parameter.
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 equal_range() 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, equal_range()
#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;
pair < vector <int>::iterator, vector <int>::iterator > Result1, Result2, Result3;
// constructing vectors vec1 with default less than ordering
int i;
for(i = -2; i <= 4; i++)
vec1.push_back(i);
int j;
for(j =1; j <= 5; j++)
vec1.push_back(j);
sort(vec1.begin(), vec1.end());
cout<<"vec1 data with range sorted by the binary predicate less than is:\n";
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;
sort(vec2.begin(), vec2.end(), greater<int>());
cout<<"\nvec2 data with range sorted by the binary predicate greater than is:\n";
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;
sort(vec3.begin(), vec3.end(), mod_lesser);
cout<<"\nvec3 data with range sorted by the binary predicate mod_lesser is:\n";
for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)
cout<<*Iter3<<" ";
cout<<"\n\n";
// equal_range of 4 in vec1 with default binary predicate less <int>()
Result1 = equal_range(vec1.begin(), vec1.end(), 4);
cout<<"lower_bound in vec1 for the element with a value of 4 is: "<<*Result1.first<<endl;
cout<<"upper_bound in vec1 for the element with a value of 4 is: "<<*Result1.second<<endl;
cout<<"The equivalence class for the element with a value of 4 in \nvec1 includes the elements: ";
for(Iter1 = Result1.first; Iter1 != Result1.second; Iter1++)
cout<<*Iter1<<" ";
cout<<endl<<endl;
// equal_range of 4 in vec2 with the binary predicate greater <int>()
Result2 = equal_range(vec2.begin(), vec2.end(), 4, greater <int>());
cout<<"lower_bound in vec2 for the element with a value of 4 is: "<<*Result2.first<<endl;
cout<<"upper_bound in vec2 for the element with a value of 4 is: "<<*Result2.second<<endl;
cout<<"The equivalence class for the element with a value of 4 in\n vec2 includes the elements: ";
for(Iter2 = Result2.first; Iter2 != Result2.second; Iter2++)
cout<<*Iter2<<" ";
cout<<endl<<endl;
// equal_range of 4 in vec3 with the binary predicate mod_lesser
Result3 = equal_range(vec3.begin(), vec3.end(), 4, mod_lesser);
cout<<"lower_bound in vec3 for the element with a value of 4 is: "<<*Result3.first<<endl;
cout<<"upper_bound in vec3 for the element with a value of 4 is: "<<*Result3.second<<endl;
cout<<"equivalence class for the element with a value of 4 in \nvec3 includes the elements: ";
for(Iter3 = Result3.first; Iter3 != Result3.second; Iter3++)
cout<<*Iter3<<" ";
cout<<endl<<endl;
return 0;
}
Output:
Further C++ STL algorithm related reading:
Acomplete C++ Standard Library documentation that includes STL.
Source code in text is available inC++ Algorithm source code sample.