std::partial_sort — cppreference.com

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

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

Сортирует часть элементов в диапазоне [first, last) в порядке возрастания. Первые middle - first отсортированные элементы находятся в диапазоне [first, middle). Не гарантируется сохранение порядка равных элементов. Порядок элементов в диапазоне [middle, last) не определен. Первый вариант использует operator< для сравнения элементов, вторая версия использует переданную функцию сравнения comp.

Параметры

first, last	—	диапазон элементов для сортировки Оригинал: the range of elements to sort Текст был переведён автоматически используя Переводчик 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`.

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

(Нет)

Сложность

O(N·log²(N)), где N = std::distance(first, last) применения cmp. Если дополнительная память недоступна, то сложность O(N·log(N))

Оригинал:

O(N·log²(N)), where N = std::distance(first, last) applications of cmp. If additional memory is available, then the complexity is O(N·log(N))

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

Пример

#include <algorithm>
#include <functional>
#include <array>
#include <iostream>

int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    for (int a : s) {
        std::cout << a << " ";
    }
}

Вывод:

См. также

Категории: