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

Question

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?

Answer 1

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

Answer 2

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.