4

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?

gsamaras
  • 71,951
  • 46
  • 188
  • 305
  • The example at cplusplus.com isn't quite concise, use [Cppreference](http://en.cppreference.com/w/cpp/algorithm/nth_element) – WhiZTiM May 05 '18 at 17:01
  • 2
    In my experience so far, cppreference has been the better reference in general. – Baum mit Augen May 05 '18 at 17:17
  • @Rakete1111 and WhiZTim, thanks for the tip! Baum mit Augen, it's scholastic, but not as friendly and direct for simple things (but as it seems I paid that price). – gsamaras May 05 '18 at 17:18
  • How can you possibly "expect 5" (or any other specific value), if you can't even be sure that after `random_shuffle` value `5` is in the subrange covered by your `nth_element` call? – AnT stands with Russia May 05 '18 at 17:19
  • @gsamaras Am i missing something stupid with my answer? I am actually very confused atm. – Kostas May 05 '18 at 17:19
  • You told it to take a subset of the entire vector, and find the 5th largest element in that subset. That value is unlikely to be 5. (Also, you seem to be having difficulty distinguishing between 1-based and 0-based indexing.) – Raymond Chen May 05 '18 at 17:23
  • @AnT I was misguided by the ref, sorry! Gill Bates, I liked the previous state of your answer. Raymond, more likely trying different stuff around, which gave you that impression, sorry. :/ All clear now. – gsamaras May 05 '18 at 17:23

2 Answers2

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.

gsamaras
  • 71,951
  • 46
  • 188
  • 305
Kostas
  • 4,061
  • 1
  • 14
  • 32
  • 1
    This is not an answer. – Pete Becker May 05 '18 at 17:14
  • 2
    @PeteBecker I am pointing out that the example he uses has a mistake. This solves the whole question problem, as `nth-element` works as he expects it to. How is this not an answer? – Kostas May 05 '18 at 17:18
  • @PeteBecker It's funny because the *edited version* is literally the original version I posted, before myself editing it. Yes, I am confused too. Also, this is as close to an answer as it can get, as there is something wrong with the question itself. – Kostas May 05 '18 at 18:05
  • You replaced your original answer with a snarky non-answer, and that's what I commented on. – Pete Becker May 05 '18 at 18:07
  • @PeteBecker Because I realized it was his intention to call `nth_element` on a subsequence, and not the whole sequence. The current answer is just weird. No idea why the rollback... No need for unnecessary code. It doesn't make any points. – Kostas May 05 '18 at 18:09
0

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).

SJHowe
  • 756
  • 5
  • 11