Boost logo

Boost :

From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2007-03-16 17:11:45

On 3/16/07, Hans Larsen <hans_at_[hidden]> wrote:
> On 16-Mar-07, at 4:42 PM, Michael Fawcett wrote:
> > On 3/16/07, Hans Larsen <hans_at_[hidden]> wrote:
> >> Maybe finding the nth element of an array, without actually sorting
> >> the array. This could be useful for finding 2nd min/max and median
> >> of an array reusing the same algorithm.
> >>
> >> This is actually quite easy, and may have already been implemented in
> >> boost or stl (but i haven't found it yet).
> >
> > std::nth_element perhaps?
> Not exactly. nth_element merely takes the pivot that you give and
> put it into place.
> What I'm looking at is a function that, given a position, returns the
> element that correspond to that position when array is sorted.
> Hans
> Exemple:
> template< class V >
> V::value_type& get_median( V& vec )
> {
> return boost::sorting::__func__( vec.begin(), vec.end(), vec.size
> () / 2 );
> }

Sorry, I guess I'm having trouble understanding how that is different.
 From MSDN article on nth_element:

"Partitions a range of elements, correctly locating the nth element of
the sequence in the range so that all the elements in front of it are
less than or equal to it and all the elements that follow it in the
sequence are greater than or equal to it."

In your example, nth_element would return the median value. In other
words, the value that would be located at vec.size() / 2 if vec were
completely sorted.

--Michael Fawcett

Boost list run by bdawes at, gregod at, cpdaniel at, john at