Previous fileTop of DocumentContentsIndex pageNext file
Apache C++ Standard Library User's Guide

14.3 nth Element

Imagine we have the sequence 2 5 3 4 7, and we want to discover the median or middle element. If we do this with the function std::nth_element(), one result might be the following sequence:

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 std::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:

Following the call on std::nth_element(), the nth largest value is 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.



Previous fileTop of DocumentContentsIndex pageNext file