HP Integrity NonStop H-Series - Manual (Page 186)

Click on the banner to return to the user guide home page.
©Copyright 1996 Rogue Wave Software
nth Element
Imagine we have the sequence 2 5 3 4 7, and we want to discover the median, or middle
element. We could do this with the function nth_element(). One result might be the following
sequence:
3 2 | 4 | 7 5
The vertical bars are used to describe the separation of the result into three parts; the elements
before the requested value, the requested value, and the values after the requested value. Note
that the values in the first and third sequences are unordered; in fact, they can appear in the
result in any order. The only requirement is that the values in the first part are no larger than the
value we are seeking, and the elements in the third part are no smaller than this value.
The three iterators provided as arguments to the algorithm nth_element() divide the argument
sequence into the three sections we just described. These are the section prior to the middle
iterator, the single value denoted by the middle iterator, and the region between the middle
iterator and the end. Either the first or third of these may be empty.
The arguments to the algorithm can be described as follows:
void nth_element (RandomAccessIterator first,
RandomAccessIterator nth,
RandomAccessIterator last [, Compare ] );
Following the call on nth_element(), the nth largest value will be copied into the position
denoted by the middle iterator. The region between the first iterator and the middle iterator will
have values no larger than the nth element, while the region between the middle iterator and the
end will hold values no smaller than the nth element.
The example program illustrates finding the fifth largest value in a vector of random numbers.
void nth_element_example ()
// illustrate the use of the nth_element algorithm
{
// make a vector of random integers
vector<int> aVec(10);
generate (aVec.begin(), aVec.end(), randomValue);
// now find the 5th largest