std::nth_element — cppreference.com

Материал из cppreference.com

Определено в заголовочном файле `<algorithm>`
`template< class RandomIt > void nth_element( RandomIt first, RandomIt nth, RandomIt last );`	(1)
`template< class RandomIt, class Compare > void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp );`	(2)

Частично виды диапазоне [first, last) в порядке возрастания так, чтобы все элементы в диапазоне [first, nth) являются' меньше, чем в диапазоне [nth, last). Первый вариант используется operator< для сравнения элементов, вторая версия использует данную comp функцию сравнения. Элемент, помещенный в nth позиции именно элемент, что будет происходить в этом положении, если диапазон был полностью отсортированный.

Оригинал:

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 first version uses operator< to compare the elements, the second version uses the given comparison function comp. The element placed in the nth position is exactly the element that would occur in this position if the range was fully sorted.

Текст был переведён автоматически используя Переводчик Google.
Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.

Параметры

first, last	—	итераторы произвольного доступа определении диапазона рода Оригинал: random access iterators defining the range sort Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
nth	—	итератор произвольного доступа, определяющей точкой рода разделов Оригинал: random access iterator defining the sort partition point Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
comp	—	объект функции сравнения (т.е. объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент "меньше", чем второй. Определение сравнения должно быть эквивалентно: `bool cmp(const Type1 &a, const Type2 &b);` Использование `noexcept` (начиная с C++11) желательно но не обязательно. Параметры не обязаны передаваться по `const&`, но не должны модифицироваться. Они должны быть способны принимать все значения типа (даже `const`) `Type1` и `Type2` независимо от категории значений (таким образом, `Type1&` не допускается, равно как и `Type1`, если только для `Type1` перемещение не эквивалентно копированию (начиная с C++11)). Типы `Type1` и `Type2` должны быть таковы, что объект типа `RandomIt` может быть разыменован и затем неявно преобразован в оба из них.
Требования к типам
-`RandomIt` должен соответствовать требованиям `ValueSwappable` и `RandomAccessIterator`.
-The type of dereferenced `RandomIt` must meet the requirements of `MoveAssignable` and `MoveConstructible`.

Возвращаемое значение

(Нет)

Сложность

Линейный в std::distance(first, last) в среднем.

Оригинал:

Linear in std::distance(first, last) on average.

Пример

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

int main()
{
    std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

    std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    std::cout << "The median is " << v[v.size()/2] << '\n';

    std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());
    std::cout << "The second largest element is " << v[1] << '\n';
}

Вывод:

The median is 5
The second largest element is 7

См. также

Категории: