Click Here!
home account info subscribe login search FAQ/help site map contact us


 
Brief Full
 Advanced
      Search
 Search Tips
[an error occurred while processing this directive]
Previous Table of Contents Next


Comments

In order to implement a sorting order for a class, you have to do just a few steps:

  Create the class that has random access to its elements.
  Define the < operator on the class data. This provides you with the default sorting order for the sort algorithm.
If you want to use a sorting order other than specified with the < operator:
  Develop a member function that specifies the sorting order in the class.
  In the module that calls the sort algorithm write the code for a function object; that is, a class that defines the function-call operator (operator()).
  Apply the function object to the sort function.
Other amendments to the program could be to use other sort algorithms that provide stable or partial sorting.

9.8 Change the order of the container elements?

Problem

For virtually all large applications with STL containers and even simpler data structures, I want to reorder the sequence of elements. I want to shuffle the data randomly and order the elements according to certain rules. What types of data reordering are implemented in the STL? Which algorithms can I use to reorganize my data?

Technique

STL algorithms that change the data container are called mutating algorithms. A few mutating algorithms can reorder container elements. The algorithms change the sequence of elements in a container or another data structure without changing the element values. This How-To discusses the rotate, reverse, and random_shuffle algorithms.

Two more complicated algorithms are the partition and the stable_partition algorithms. The algorithms apply a predicate to a given sequence. If the predicate returns true for an element, the element goes to the beginning of the sequence. If the predicate returns false, the element goes to the end of the sequence. In other words, the algorithms reorder the sequence in such a way that the elements that satisfy the predicate precede the elements that don’t satisfy the predicate. The stable_partition algorithm also keeps the relative order in both parts of the reordered sequence.

Steps

1.  Rotating a sequence
To rotate a sequence of elements, let’s first create the sequence. This example uses a simple container, a vector of integers. To support the STL container, you have to include the <vector> header file. I used the Microsoft Visual C++ 5 compiler; therefore, you should provide the using namespace std; directive as well.
#include <vector>
using namespace std;

The following code defines the VectExample vector and fills it in with four elements: 1, 2, 6, 7.
    // Vector definition
vector <int> VectExample;
    // Filling in the container
    VectExample.push_back (1);
    VectExample.push_back (2);
    VectExample.push_back (6);
    VectExample.push_back (7);

To rotate the given sequence on integers, use the rotate algorithm. The rotate algorithm takes three iterators as arguments. The first argument specifies the beginning of the sequence. The second argument specifies the starting location of the rotating elements, the last argument specifies the end of the sequence. For example, if the algorithm is specified as
rotate (First_Iterator, Middle_Iterator, Last_Iterator)

the algorithm will move the *Middle_Iterator element to the First_Iterator position, the *(Middle_Iterator + 1) element to the First_Iterator + 1 position, and so on.
In this example, you want to move the first element to the back of the sequence. To do so, you have to move the second element to the first position, the third element to the second position, and so forth. The following code does just that:
// Temporary iterator definition
vector <int>::iterator iTemp;
// Rotate the sequence: move the first element
// to the end
iTemp = VectExample.begin();
iTemp++;
rotate (VectExample.begin(), iTemp, VectExample.end());

This code assigned the iterator to the beginning of the vector to the iTemp temporary iterator, and then moved the iterator to the second element by executing the ++ operator.
2.  Reversing the order of a sequence
The same example will be used to discuss the reverse algorithm. This algorithm reverses a range of elements. The algorithm takes two parameters: the iterator that points to the beginning of the range and the iterator that points the end of the range.
In this example, you want to reverse the order of the whole sequence. Therefore, use the begin() and the end() functions of the vector.
The code looks very simple:
// Reverse the order of the elements
reverse (VectExample.begin(), VectExample.end());

and it certainly is.
3.  Randomly shuffling a sequence
When I read about shuffling the data, the first thing I think about is a gambling application. However, shuffling the data is much more important. It is used in modeling physical processes, in mathematical calculations, and in estimation of missile trajectories, among other things.
The STL uses the random_shuffle algorithm to randomly shuffle the data. The algorithm yields uniformly distributed results; that is, the probability of any particular ordering is 1/N!. The simple version of the algorithm takes two arguments: the iterators that specify the beginning and the end of the range. The more advanced version of the algorithm needs one more argument: the random number generator, a special function object.
This example shows the simple version of the algorithm that uses the internal random number generator:
// Randomly shuffle the sequence
random_shuffle (VectExample.begin(), VectExample.end());

The example shuffles the data in the entire vector.


Previous Table of Contents Next


Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.