CODEWITHSUNDEEP
c++algorithmc++11std
Martin Drozdik
Martin Drozdik

Reputation: 13303

Is std::nth_element defined for ranges containing same values?

From the documentation of std::nth_element we have:

template< class RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last );

Partially sorts the range [first, last) in ascending order so that all elements in the range [first, nth) are less than those in the range [nth, last).

The thing that bothers me is the less word. Shouldn't it be less or equal? If the range is for example:

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

int main()
{
    std::vector<int> numbers = {3, 2, 2, 2, 1};
    auto middlePosition = numbers.begin() + 2;
    std::nth_element(numbers.begin(), middlePosition, numbers.end());

    for (int x : numbers)
        std::cout << x << std::endl;
    return 0;
}

The algorithm cannot make both numbers before the middlePosition less than 2, because there is only one such number. The algorithm does its best and the output is as desired:

1
2
2
3
2

Can I rely on such nice behavior?

My implementation (gcc 4.7) uses the introselect algorithm. Unfortunately I couldn't find the requirements on input of the algorithm. Does introselect need all values to be different?

Upvotes: 13

Views: 951

Answers (3)

aces
aces

Reputation: 305

No, it does not sort equal or less! nth_element randomly picks one of the values, that could be at the nth position in the sorted array. Since this would be the nth position there is no way, it can put all equal on the left side, since then it would not be the nth element anymore. Test it! The values equal appear on both sides of the nth position.

Upvotes: 0

awesoon
awesoon

Reputation: 33651

I think, cppreference is incorrect here. Take loot at the Standard(N3337 25.4.2):

template<class RandomAccessIterator>
void nth_element
(
    RandomAccessIterator first,
    RandomAccessIterator nth,
    RandomAccessIterator last
);

... For any iterator i in the range [first,nth) and any iterator j in the range [nth,last) it holds that: !(*j < *i) or comp(*j, *i) == false.

So, elements in range [first,nth) will be less or equal than elements in range [nth,last).

Upvotes: 14

cpp
cpp

Reputation: 3801

Here is a better definition of std::nth_element:

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.

The other elements are left without any specific order, except that none of the elements preceding nth are greater than it, and none of the elements following it are less.

Upvotes: 6

Related Questions