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

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

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

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

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

#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, чтобы все значения были разными?


c++ algorithm c++11 c++-standard-library
person Martin Drozdik    schedule 22.08.2013    source источник

Ответы (3)


arrow_upward
13
arrow_downward

Я думаю, 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).

person awesoon    schedule 22.08.2013
comment
Конечно, !(*i > *j) означает, что элементы в [nth,last) не будут меньше, чем элементы в [first,nth)? - person Useless; 22.08.2013
comment
Спасибо за смелость и редактирование cppreference: я еще больше отредактировал его, чтобы применить выпуск LWG 2162 - person Cubbi; 22.08.2013
comment
@Cubbi, да, это выглядит лучше :) - person awesoon; 22.08.2013

arrow_upward
5
arrow_downward

Вот лучшее определение std::nth_element:

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

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

person cpp    schedule 22.08.2013
comment
+1 за обнаружение случая, когда cplusplus.com является более правильным, чем cppreference.com! - person Yakk - Adam Nevraumont; 22.08.2013

arrow_upward
0
arrow_downward

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

person aces    schedule 21.05.2015