|< C++ STL Iterator 7 | Main | C++ STL Algorithm 2 >| Site Index | Download |


 

 

 

 

 

 

MODULE 33

THE C++ STL ALGORITHM PART 1

 

 

 

 

 

My Training Period: xx hours

 

More class templates member function program examples compiled using Microsoft Visual C++ .Net, win32 empty console mode application. g++ compilation examples given at the end of this Module. Source code in text is available in C++ Algorithm source code sample.

 

The C++ STL algorithm knowledge that supposed to be acquired:

 

 

What do we have in this session?

  1. Algorithms

  2. Introduction

  3. A simple algorithm program example

  4. Ranges

  5. Multiple Ranges

  6. Algorithm, program example

  7. Algorithm, program example

  8. Algorithms versus Member Functions

  9. User Defined Generic Functions

  10. Functions as Algorithm Arguments

  11. Predicates

  12. Unary Predicates

  13. Algorithm, a simple program example, finding prime numbers

  14. Binary Predicates

  15. Algorithm, predicate program example

  16. Complexity and the Big-O Notation

  17. Algorithm, program example - g++

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

33.1  Algorithms

 

33.1.1  Introduction

  • We have covered containers and iterators, now we are going to complete our discussion by introducing algorithms.

  • We create data structure by using containers, and then we use iterators to traverse, iterate or explore the data structure.  During the iteration we will use algorithm, a set of rules that actually defined what to do to the data structure: sorting, searching, re-ordering etc.

  • The STL provides several standard algorithms for the processing of elements of collections.

  • These algorithms offer general fundamental services, such as searching, sorting, copying, reordering, modifying, and numerical processing, so that no need for us to start developing program portions or routines from scratch.  Furthermore they have been tested and your task is to learn how to use these ‘creatures’ effectively.

  • Algorithms are global functions that operate with iterators; hence, all algorithms can be implemented once for any container type. The algorithm might even operate on elements of different container types. Furthermore you can also use the algorithms for user-defined container types.

  • Keep in mind that in the previous tutorials on containers and iterators, there are many standard algorithms have been introduced.

  • Let's start with a simple example on the use of STL algorithms. Consider the following program:

// a simple algorithm example

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int main()

{

    // declare a vector and the iterator

    vector<int> vec;

    vector<int>::iterator pos;

    // insert elements from 1 to 6 in arbitrary order

    vec.push_back(7);

    vec.push_back(4);

    vec.push_back(8);

    vec.push_back(0);

    vec.push_back(12);

    vec.push_back(9);

    // print the vector...

    cout<<"The original vector: ";

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

        cout<<*pos<< " ";

    cout<<endl;

    // find and print minimum and maximum elements

    pos = min_element(vec.begin(), vec.end());

    cout<<"\nThe minimum element's value: "<<*pos<<endl;

    pos = max_element(vec.begin(), vec.end());

    cout<<"\nThe maximum element's value: "<<*pos<<endl<<endl;

    // sort algorithm, sort all elements

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

    // print the vector...

    cout<<"The sorted vector: ";

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

        cout<<*pos<< " ";

    cout<<endl<<endl;

    cout<<"Find value of 8, then reverse the order: ";

    // find algorithm, find the first element with value 8

    pos = find(vec.begin(), vec.end(), 8);

    // reverse algorithm, reverse the order of the found element with value 8 and all the following elements

    reverse(pos, vec.end());

    // print all elements

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

        cout<<*pos<<' ';

    cout << endl;

}

 

Output:

 

C++ STL Algorithm very simple general program example

#include <algorithm>

pos = min_element(vec.begin(), vec.end());

cout<<"\nThe minimum element's value: "<<*pos<<endl;

cout<<"\nThe maximum element's value: "<<*pos<<endl<<endl;

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

0 4 7 8 9 12

pos = find(vec.begin(), vec.end(), 8);

reverse(pos, vec.end());

33.1.2  Ranges

33.1.3  Multiple Ranges

if(equal(vec1.begin(), vec2.end(), vec2.begin()))

{...}

// algorithms, example

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

using namespace std;

 

int main()

{

list<int> lst1;

vector<int> vec1;

// insert elements from 1 to 9

for(int i=1; i<=9; ++i)

lst1.push_back(i);

// RUNTIME ERROR:

// - overwrites nonexistence elements in the destination

copy (lst1.begin(), lst1.end(), //the source

vec1.begin()); //the destination

......

}

  1. Ensure that the destination has enough elements on entry, or

  2. Uses insert iterators.

// algorithm, example

#include <iostream>

#include <vector>

#include <list>

#include <deque>

#include <algorithm>

using namespace std;

 

int main()

{

    list<int> lst1;

    list<int>::iterator pos;

    vector<int> vec1;

    vector<int>::iterator pos1;

    // insert elements from 1 to 10

    for(int i=1; i<=10; ++i)

        lst1.push_back(i);

    // display data

    cout<<"The list lst1 data: ";

    for(pos=lst1.begin(); pos!=lst1.end(); pos++)

        cout<<*pos<<" ";

    cout<<endl;

    //resize destination to have enough room for the overwriting algorithm

    vec1.resize(lst1.size());

    // copy elements from first into second collection overwrites existing elements in destination

    copy(lst1.begin(), lst1.end(), // source

    vec1.begin()); //destination

    

    cout<<"\nThe vector vec1 data: ";

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

    cout<<*pos1<<" ";

    cout<<endl;

    // create third collection with enough allocation initial size is passed as parameter

    deque<int> deq1(lst1.size());

    deque<int>::iterator pos2;

    // copy elements from first into third collection

    copy(lst1.begin(), lst1.end(), //source

    deq1.begin()); //destination

    cout<<"\nThe deque deq1 data: ";

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

        cout<<*pos2<<" ";

    cout<<endl;

}

 

Output:

 

C++ STL Algorithm very simple general program example

 

  • Here, resize() is used to change the number of elements in the existing container vec1:

vec1.resize(vec1.size());

  • deq1 is initialized with a special initial size so that it has enough room for all elements of lst1:

deque<int> deq1(vec1.size());

  • Note that both resizing and initializing the size create new elements. These elements are initialized by their default constructor because no arguments are passed to them.

  • You can pass an additional argument both for the constructor and for resize() to initialize the new elements.

 

33.2  Algorithms versus Member Functions

33.3  User Defined Generic Functions

33.4  Functions as Algorithm Arguments

33.5  Predicates

33.5.1  Unary Predicates

// algorithm, a simple example, finding prime numbers

#include <iostream>

#include <list>

#include <algorithm>

// for abs()

#include <cstdlib>

using namespace std;

 

// a predicate, which returns whether an integer is a prime number

bool isPrimeNum(int number)

{

    // ignore negative sign

    number = abs(number);

    // 0 and 1 are prime numbers

    if(number == 0 || number == 1)

    {

return true;

    }

    // find divisor that divides without a remainder

    int divisor;

    for(divisor = (number/2); (number%divisor) != 0; --divisor)

    {;}

    

    // if no divisor greater than 1 is found, it is a prime number

    return divisor == 1;

}

 

int main()

{

    list<int> lst1;

    // insert elements from 24 to 30

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

    lst1.push_back(i);

    // search for prime number

    list<int>::iterator pos;

    cout<<"The list lst1 data:\n";

    for(pos=lst1.begin(); pos!=lst1.end(); pos++)

        cout<<*pos<<" ";

    cout<<endl<<endl;

    pos = find_if(lst1.begin(), lst1.end(), //range

    isPrimeNum); //predicate

    if(pos != lst1.end())

    {

        // found

        cout<<*pos<<" is the first prime number found"<<endl;

    }

    else {

    // not found

    cout<<"no prime number found"<<endl;

}

}

 

Output:

 

C++ STL Algorithm very simple general program example

33.5.2  Binary Predicates

// algorithm, predicate

#include <iostream>

#include <string>

#include <deque>

#include <algorithm>

using namespace std;

 

class Person

{

    public:

        string firstname() const;

        string lastname() const;

        ...

};

 

// binary function predicate: returns whether a person is less than another person

bool SortCriterion(const Person& p1, const Person& p2)

{

    // a person is less than another person, if the last name is less, if the last name is equal and the first name is less

    return p1.lastname()<p2.1astname() || (!(p2.1astname()<p1.lastname()) &&

    p1.firstname()<p2.firstname());

}

 

int main()

{

    deque<Person> deq1;

    ...

    sort(deq1.begin(), deq1.end(), SortCriterion);

    ...

}

33.6  Complexity and the Big-O Notation

Type

Notation

Description

Constant

O(1)

The runtime is independent of the number of elements.

Logarithmic

O(log(n))

The runtime grows logarithmically with respect to the number of elements.

Linear

O(n)

The runtime grows linearly (with the same factor) as the number of elements grows.

n-log-n

O(n *log(n))

The runtime grows as a product of linear and logarithmic complexity.

Quadratic

O(n2)

The runtime grows quadratically with respect to the number of elements.

 

Table 33.1:  The O-Notation

// ********algo.cpp*********

// algorithm, example - g++

#include <iostream>

#include <vector>

#include <list>

#include <deque>

#include <algorithm>

using namespace std;

 

int main()

{

    list<int> lst1;

    list<int>::iterator pos;

    vector<int> vec1;

    vector<int>::iterator pos1;

    // insert elements from 1 to 10

    for(int i=1; i<=10; ++i)

    lst1.push_back(i);

    // display data

    cout<<"The list lst1 data: ";

    for(pos=lst1.begin(); pos!=lst1.end(); pos++)

        cout<<*pos<<" ";

    cout<<endl;

    // resize destination to have enough room for the overwriting algorithm

    vec1.resize(lst1.size());

    //copy elements from first into second collection

    //overwrites existing elements in destination

    copy(lst1.begin(), lst1.end(), // source

    vec1.begin()); //destination

    cout<<"\nThe vector vec1 data: ";

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

    cout<<*pos1<<" ";

        cout<<endl;

    // create third collection with enough allocation initial size is passed as parameter

    deque<int> deq1(lst1.size());

    deque<int>::iterator pos2;

    // copy elements from first into third collection

    copy(lst1.begin(), lst1.end(), //source

    deq1.begin()); //destination

    cout<<"\nThe deque deq1 data: ";

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

        cout<<*pos2<<" ";

    cout<<endl;

}

 

[bodo@bakawali ~]$ g++ algo.cpp -o algo

[bodo@bakawali ~]$ ./algo

 

The list lst1 data: 1 2 3 4 5 6 7 8 9 10

 

The vector vec1 data: 1 2 3 4 5 6 7 8 9 10

 

The deque deq1 data: 1 2 3 4 5 6 7 8 9 10

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

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

  2. C++ Templates programming tutorials.

  3. A complete C & C++ Standard Library documentation that includes STL.

  4. Check the best selling C / C++ and STL books at Amazon.com.

 

 

 

 

 

 

 

|< C++ STL Iterator 7 | Main | C++ STL Algorithm 2 >| 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