|< C++ STL algorithm 3 | Main | C++ STL Algorithm 5 >|Site Index |Download |

---

 

 

 

 

 

 

MODULE 34a

THE C++ STL ALGORITHM PART 4

 

 

 

 

 

My Training Period: xx hours

 

A continuation from previous Module, more examples, code samples compiled usingMicrosoft Visual 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 skills that supposed to be acquired:   Able to understand and use the member functions of the algorithm. Learn how to use the template classes and functions. Able to use containers, iterators and algorithm all together.   What do we have in this page? Algorithm, equal_range() program example Algorithm, fill() program example Algorithm, fill_n() program example Algorithm, find() program example Algorithm, find_end() program example Algorithm, find_first_of() program example     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:

 

fill()

• Assigns the same new value to every element in a specified range.

template<class ForwardIterator, class Type> void fill( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

Parameters

 

• The destination range must be valid; all pointers must be de-referenceable, and the last position is reachable from the first by incrementation. The complexity is linear with the size of the range.

// algorithm, fill()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int> vec;

    vector <int>::iterator Iter1;

    int i;

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

        vec.push_back(i);

    cout<<"Vector vec data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // fill the last 4 positions with a value of 9

    cout<<"\nOperation: fill(vec.begin() + 4, vec.end(), 9)\n";

    fill(vec.begin() + 4, vec.end(), 9);

    cout<<"Modified vec data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

 

fill_n()

• Assigns a new value to a specified number of elements in a range beginning with a particular element.

template<class OutputIterator, class Size, class Type> void fill_n( OutputIterator _First, Size _Count, const Type& _Val );

Parameters

 

• The destination range must be valid; all pointers must be de-referenceable, and the last position is reachable from the first by incrementation. The complexity is linear with the size of the range.

// algorithm, fill_n() #include <vector> #include <algorithm> #include <iostream> using namespace std;   int main() {     vector <int> vec;     vector <int>::iterator Iter1;     int i;     for(i = 10; i <= 20; i++)         vec.push_back(i);     cout<<"Vector vec data: ";     for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)         cout<<*Iter1<<" ";     cout<<endl;     // fill the last 3 positions for 6 position with a value of 9     cout<<"\nOperation: fill_n(vec.begin() + 3, 6, 9)\n";     fill_n(vec.begin() + 3, 6, 9);     cout<<"Modified vec data: ";     for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)         cout<<*Iter1<<" ";     cout<<endl;     return 0; }

Output:

 

 

find()

• Locates the position of the first occurrence of an element in a range that has a specified value.

template<class InputIterator, class Type> InputIterator find( InputIterator _First, InputIterator _Last, const Type& _Val );

Parameters

 

• The return value is an input iterator addressing the first occurrence of the specified value in the range being searched. If no such value exists in the range, the iterator returned addresses the last position of the range, one past the final element.

• Theoperator== used to determine the match between an element and the specified value must impose an equivalence relation between its operands.

// algorithm, find()

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

    list <int> lst;

    list <int>::iterator Iter;

    list <int>::iterator result;

    lst.push_back(9);

    lst.push_back(21);

    lst.push_back(14);

    lst.push_back(10);

    lst.push_back(16);

    lst.push_back(31);

    cout<<"List lst data: ";

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

        cout<<*Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: find(lst.begin(), lst.end(), 14)\n";

    result = find(lst.begin(), lst.end(), 14);

    if(result == lst.end())

        cout<<"There is no 14 in list lst."<<endl;

    else

        result++;

    cout<<"There is a 14 in list lst and it is"<<" followed by a "<<*(result)<<endl;

    return 0;

}

 

Output:

 

 

find_end()

• Looks in a range for the last subsequence that is identical to a specified sequence or that is equivalent in a sense specified by a binary predicate.

1. template<class ForwardIterator1, class ForwardIterator2>ForwardIterator1 find_end( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2 );

2. template<class ForwardIterator1, class ForwardIterator2, class Pr>ForwardIterator1 find_end( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2, BinaryPredicate _Comp );

Parameters

 

• The return value is a forward iterator addressing the position of the first element of the last subsequence that matches the specified sequence or that is equivalent in a sense specified by a binary predicate.

• Theoperator== used to determine the match between an element and the specified value must impose an equivalence relation between its operands.

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

// algorithm, find_end()

//some type conversion warning

#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 = 10; i <= 15; i++)

        vec1.push_back(i);

    int j;

    for(j = 11; j <= 14; j++)

        lst.push_back(j);

    int k;

    for(k = 12; k <= 14; k++)

        vec2.push_back(2*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<<endl;

    // searching vec1 for a match to lst under identity

    vector <int>::iterator result1;

    result1 = find_end(vec1.begin(), vec1.end(), lst.begin(), lst.end());

    if(result1 == vec1.end())

        cout<<"There is no match of lst in vec1."<<endl;

    else

        cout<<"There is a match of lst in vec1 that begins at position "<<result1 - vec1.begin()<<endl;

    // searching vec1 for a match to lst under the binary predicate twice

    vector <int>::iterator result2;

    result2 = find_end(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), twice);

    if(result2 == vec1.end())

        cout<<"\nThere is no match of lst in vec1."<<endl;

    else

        cout<<"\nThere is a sequence of elements in vec1 that are\nequivalent to those in vec2 under the binary "

                <<"predicate\ntwice and that begins at position "<<result2 - vec1.begin()<<endl;

    return 0;

}

 

Output:

 

 

find_first_of()

• Searches for the first occurrence of any of several values within a target range or for the first occurrence of any of several elements that are equivalent in a sense specified by a binary predicate to a specified set of the elements.

1. template<class ForwardIterator1, class ForwardIterator2>ForwardIterator1 find_first_of( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2 );

2. template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>ForwardIterator1 find_first_of( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2, BinaryPredicate _Comp );

Parameters

 

• The return value is a forward iterator addressing the position of the first element of the first subsequence that matches the specified sequence or that is equivalent in a sense specified by a binary predicate.

• Theoperator== used to determine the match between an element and the specified value must impose an equivalence relation between its operands.

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

// algorithm, find_first_of()

#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 = 3; j <= 4; j++)

        lst.push_back(5*j);

    int k;

    for(k = 2; k <= 4; 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;

    // searching vec1 for first match to lst under identity

    vector <int>::iterator result1;

    result1 = find_first_of(vec1.begin(), vec1.end(), lst.begin(), lst.end());

    if(result1 == vec1.end())

        cout<<"\nThere is no match of lst in vec1."<<endl;

    else

        cout<<"\nThere is at least one match of lst in vec1\nand the first one begins at position "<<result1 - vec1.begin()<<endl;

    // searching vec1 for a match to lst under the binary predicate twice

    vector <int>::iterator result2;

    result2 = find_first_of(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), twice);

    if(result2 == vec1.end())

        cout<<"\nThere is no match of lst in vec1."<<endl;

    else

        cout<<"\nThere is a sequence of elements in vec1 that are\nequivalent to those in vec2 under the binary\n"

                <<"predicate twice and the first one begins at position "<<result2 - vec1.begin()<<endl;

    return 0;

}

 

Output:

 

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

Further C++ STL algorithm reading:

 

1. Source code in text is available inC++ Algorithm source code sample.

2. Acomplete C Standard Library.

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

4. C++ Templates programming tutorials.

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

 

 

 

 

 

|< C++ STL algorithm 3 | Main | C++ STL Algorithm 5 >|Site Index |Download |

---

C++ STL Algorithm Classes:  Part 1 | Part 2 |Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 |Part 9 | Part 10 |Part 11 | Part 12 | Part 13 | Part 14 | Part 15