Определяется ли std:: nth_element для диапазонов, содержащих одни и те же значения?

Из документации std:: nth_element мы имеем:

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

Частично сортирует диапазон [первый, последний] в порядке возрастания, так что все элементы в диапазоне [first, nth] меньше, чем в диапазоне [nth, last).

Вещь, которая меня беспокоит, - это слово less. Разве это не должно быть меньше или равно? Если диапазон, например:

#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;
}

Алгоритм не может сделать оба числа до middlePosition меньше, чем 2, потому что есть только одно такое число. Алгоритм делает все возможное, и выход по желанию:

1
2
2
3
2

Могу ли я полагаться на такое приятное поведение?

В моей реализации (gcc 4.7) используется алгоритм introselect. К сожалению, я не смог найти требования по вводу алгоритма. Требуется ли introselect для разных значений?

Ответы

Ответ 1

Я думаю, cppreference здесь неверно. Возьмите добычу в стандарте (N3337 25.4.2):

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

... Для любого итератора i в диапазоне [first,nth) и любого итератора j в диапазон [nth,last) он содержит: !(*j < *i) или comp(*j, *i) == false.

Итак, элементы в диапазоне [first,nth) будут меньше или равны элементам в диапазоне [nth,last).

Ответ 2

Здесь - лучшее определение std:: nth_element:

Переупорядочивает элементы в диапазоне [первый, последний], таким образом, чтобы элемент в n-й позиции - это элемент, который был бы в этом позиции в отсортированной последовательности.

Остальные элементы остаются без какого-либо определенного порядка, за исключением того, что ни один из элементов, предшествующих n-м, больше, чем один, и ни один из элементы, следующие за ним, меньше.

Ответ 3

Нет, он не сортируется одинаково или меньше! nth_element случайным образом выбирает одно из значений, которое может находиться в n-й позиции в отсортированном массиве. Поскольку это будет n-я позиция, нет способа, она может поместить все равные с левой стороны, так как тогда это не будет n-ый элемент больше. Попробуй это! Значения равны на обеих сторонах n-й позиции.