|
 |
 |
[an error occurred while processing this directive]
- 4. Testing the rotate, reverse, and random_shuffle algorithms
Now you are ready to write a small program that uses all the algorithms. To display the result of an algorithm, the program will use the following code:
for (i= VectExample.begin(); i != VectExample.end(); ++i)
cout << *i << endl;
where i is an iterator defined as
vector <int>::iterator i;
Last but not least, include the <algorithm> header file to your program.
// order.cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
// Vector and iterators definition
vector <int> VectExample;
vector <int>::iterator i;
vector <int>::iterator iTemp;
// Creating the container
VectExample.push_back (1);
VectExample.push_back (2);
VectExample.push_back (6);
VectExample.push_back (7);
cout << Original sequence: << endl;
for (i= VectExample.begin(); i != VectExample.end(); ++i)
cout << *i << endl;
// Rotate the sequence: move the first element
// to the end
iTemp = VectExample.begin();
iTemp++;
rotate (VectExample.begin(), iTemp, VectExample.end());
cout << Rotated sequence: << endl;
for (i= VectExample.begin(); i != VectExample.end(); ++i)
cout << *i << endl;
// Reverse the order of the elements
reverse (VectExample.begin(), VectExample.end());
cout << Reversed sequence: << endl;
for (i= VectExample.begin(); i != VectExample.end(); ++i)
cout << *i << endl;
// Randomly shuffle the sequence
random_shuffle (VectExample.begin(), VectExample.end());
cout << Shuffled sequence: << endl;
for (i= VectExample.begin(); i != VectExample.end(); ++i)
cout << *i << endl;
return 0;
}
The random_shuffle algorithm can produce different results depending on the internal random number generator. The rest should show the same lines for all compilers. After I compiled the program with the Microsoft Visual C++ 5 compiler and ran the program, my computer showed the following result:
Original sequence:
1
2
6
7
Rotated sequence:
2
6
7
1
Reversed sequence:
1
7
6
2
Shuffled sequence:
7
2
1
6
- 5. Reordering a sequence according to a predicate
In this example, lets separate odd numbers from even numbers. To see how to move the odd numbers before the even numbers, examine the following program:
// part.cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
int main()
{
// Vector and iterators definition
vector <int> VectExample;
vector <int>::iterator i;
// Creating the container
VectExample.push_back (1);
VectExample.push_back (2);
VectExample.push_back (6);
VectExample.push_back (7);
cout << Original sequence: << endl;
for (i= VectExample.begin(); i != VectExample.end(); ++i)
cout << *i << endl;
partition (VectExample.begin(), VectExample.end(),
bind2nd(modulus<int>(), 2));
cout << Odd numbers first: << endl;
for (i= VectExample.begin(); i != VectExample.end(); ++i)
cout << *i << endl;
return 0;
}
The program creates the same vector as in the previous example. The odd vector elements are separated from the even elements using the partition algorithm. The algorithm takes three arguments. The first and the second arguments specify the sequence range. In this case, you want to apply the algorithm to the whole vector from VectExample.begin() to VectExample.end(). The third argument specifies the predicate. Apply the modulus operation that returns 0 (false) if the element is even and 1 (true) if the element is odd.
My compiler produced the following result:
Original sequence:
1
2
6
7
Odd numbers first:
1
7
6
2
The result might vary for other compilers. However, the important thing is that the partition algorithm does not preserve the relative order of the even and odd elements. In the original sequence, 2 precedes 6. In the result sequence, 2 follows 6.
To preserve the order, you can use the stable_partition algorithm. If you change the statement with the partition algorithm in the example to
stable_partition (VectExample.begin(), VectExample.end(),
bind2nd(modulus<int>(), 2));
the result will be
Original sequence:
1
2
6
7
Odd numbers first:
1
7
2
6
Comments
The mutating algorithms include a few reordering algorithms. This How-To discusses their use with the Microsoft Visual C++ 5 compiler. The Borland C++ 5 compiler uses the same syntax of the algorithms and the same filenames for the header files. However, other compilers might use <algorithm.h> or <algo.h> instead of the <algorithm> header file, and <vector.h> instead of the <vector> file.
|