CODEWITHSUNDEEP
c++
kingwales
kingwales

Reputation: 139

the n should be inclusive or exclusive when using std::nth_element?

Hi I have a question on the usage of std::nth_element.

If I want to obtain the k-th largest element from a vector, should it inclusive or exclusive?

int k = 3;
vector<int> nums{1,2,3,4,5,6,7};
std::nth_element(nums.begin(), nums.begin()+k-1, nums.end(), [](int& a, int& b){return a > b;});
int result = nums[k-1]

or

int k = 3
vector<int> nums{1,2,3,4,5,6,7};
std::nth_element(nums.begin(), nums.begin()+k, nums.end(), [](int& a, int& b){return a > b;});
int result = nums[k-1]

It reminds me that when we get a subarray using iterator, it should be exclusive? for example,

vector<int> sub(nums.begin(), nums.begin()+k);

So, the n for nth_element is also exclusive?

Upvotes: 1

Views: 355

Answers (1)

jdaz
jdaz

Reputation: 6043

This is the type of question that is best to figure out and understand by playing around with a bunch of examples on your own.

However, I'll try to explain why you're getting the same answer in both of your examples. As explained in cppreference, std::nth_element is a partial sorting algorithm. It only guarantees that, given an iterator to an element n as its second argument:

All of the elements before this new nth element are less than or equal to the elements after the new nth element.

("Less than or equal to" is the default behavior if you don't pass a special comparison function.)

That means if you use nums.begin()+k-1 in one case and nums.begin()+k in another case as the second argument to std::nth_element, then in the latter case the partial sorting algorithm will include one additional item in the sort. In that case, you are dividing the vector between larger and smaller items at a spot one index higher than in the first case. However, the (default) algorithm only guarantees that each of the items in the "small half" of the vector will be smaller than each of the items in the "large half," not that the two halves are sorted within themselves.

In other words, if you've done a partial sort through nums.begin()+k, there is no guarantee that nums[k-1] will be the next-smallest (or in your case, the next-largest) number in the entire vector.

With certain inputs, like your {1, 2, 3, 4, 5, 6, 7}, or {9, 4, 1, 8, 5}, you do happen to get the same answers.

However, with many others, like {1, 4, 9, 8, 5}, the results do not match:

int k = 3;
vector<int> nums{1,4,9,8,5};
auto numsCopy = nums;

// First with +k - 1
std::nth_element(nums.begin(), nums.begin()+k-1, nums.end(), [](int& a, int& b){return a > b;});

// Then with only +k
std::nth_element(numsCopy.begin(), numsCopy.begin()+k, numsCopy.end(), [](int& a, int& b){return a > b;});

cout << nums[k-1]; // 5
cout << numsCopy[k-1]; // 9

Demo

Can you figure out why that is?

Also, to clearly answer your question about inclusive vs exclusive, as @Daniel Junglas pointed out in the comments, the second argument to std::nth_element is meant to point directly to the item you wish to be changed. So if it helps you, you can think of that as "inclusive." This is different from the third argument to std::nth_element, the end iterator, which is always exclusive since .end() points beyond the last item in the vector.

Upvotes: 4

Related Questions