Towards understanding nth_element

Question

I am having a difficult time grasping how I should use std::nth_element, since I am little rusty.

The ref says:

Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.

I want to take the n-th element of a subset of a vector, so I thought doing something like this:

std::nth_element (v.begin()+start-0, v.begin()+nTh-1, v.begin()+end);

would mean to take the subset of the vector v, from the start, until the end (exclusive), and then imagining that this subset is sorted, position the nTh element.

It seems that my understanding is off, since this toy example:

#include <iostream>
#include <algorithm>
#include <vector>

int main () {
  std::vector<int> myvector;

  // set some values:
  for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

  std::random_shuffle (myvector.begin(), myvector.end());


  std::nth_element (myvector.begin() + 1 - 0, myvector.begin()+5-1, myvector.begin() + 5);
  std::cout <<  *(myvector.begin()+5-1) << std::endl;

  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

prints 9 as the requested element, while I would be expecting 5. What am I missing please?

Answer 1

Try:

std::nth_element (myvector.begin(), myvector.begin()+ 4, myvector.end());

instead of :

std::nth_element (myvector.begin() + 1, 
                  myvector.begin() + 4, 
                  myvector.begin() + 5);

You are shuffling and then calling nth_element for only a subsequence. This way you cannot what the returned element should be. If you do it for the whole sequence, then the answer is 5.

Answer 2

I want to take the n-th element of a subset of a vector, so I thought doing something like this:

std::nth_element (v.begin()+start-0, v.begin()+nTh-1, v.begin()+end);

would mean to take the subset of the vector v, from the start, until the end (exclusive), and then imagining that this subset is sorted, position the nTh element.

Yes that is true. But in so doing, any elements in the positions v[0] to v[start-1] and v[end] to v[v.size() - 1] will not be part of the nth_element rearrangement, they will stay where they are. Your start and end as part of nth_element() have excluded these elements from being rearranged.

I think you want

std::nth_element (myvector.begin(), myvector.begin()+ 4, myvector.end());

which the whole vector is considered (1st and 3rd arguments to nth_element).

This means regardless as to where random_shuffle has shuffled elements

std::random_shuffle (myvector.begin(), myvector.end());

because nth_element is considerering the whole vector, the 2nd argument to nth_element, the 5th item in myvector if sorted, should be 5. Note, because of the way nth_element works, the previous items will be less than 5 (and in any order) and next items will be more than 5 (and in any order).