Пространства имён
Варианты
Действия

std::partial_sort_copy

Материал из cppreference.com
< cpp‎ | algorithm

 
 
Алгоритмы
Функции
Немодифицирующие линейные операции
Модифицирующие линейные операции
Разделение
Сортировка (на отсортированных промежутках)
Бинарный поиск (на отсортированных промежутках)
Множества (на отсортированных промежутках)
Куча
Минимум/максимум
Числовые операции
Библиотека C
 
Определено в заголовочном файле <algorithm>
template< class InputIt, class RandomIt >

RandomIt partial_sort_copy( InputIt first, InputIt last,

                            RandomIt d_first, RandomIt d_last );
(1)
template< class InputIt, class RandomIt, class Compare >

RandomIt partial_sort_copy( InputIt first, InputIt last,
                            RandomIt d_first, RandomIt d_last,

                            Compare comp );
(2)
Сорта некоторые элементы в диапазоне [first, last) в порядке возрастания. В большинстве d_first - d_last элементы перемещаются в диапазоне [d_first, d_first + n), а затем сортируются. n это число элементов для сортировки (n = min(last - first, d_last - d_first)). Порядок равных элементов не гарантируется быть сохранены. Первый вариант используется operator< для сравнения элементов, вторая версия использует данную функцию сравнения comp.
Оригинал:
Sorts some of the elements in the range [first, last) in ascending order. At most d_first - d_last of the elements are moved to the range [d_first, d_first + n) and then sorted. n is the number of elements to sort (n = min(last - first, d_last - d_first)). The order of equal elements is not guaranteed to be preserved. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

Содержание

[править] Параметры

first, last -
диапазон элементов для сортировки
Оригинал:
the range of elements to sort
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.
d_first, d_last -
итераторы произвольного доступа определение целевой диапазон
Оригинал:
random access iterators defining the destination range
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.
comp - comparison function which returns ​true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:

 bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.
Типы Type1 и Type2 должны быть таковы, что объект типа RandomIt может быть разыменован и затем неявно преобразован в оба из них. ​

Требования к типам
-
InputIt должен соответствовать требованиям InputIterator.
-
RandomIt должен соответствовать требованиям ValueSwappable and RandomAccessIterator.
-
The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.

[править] Возвращаемое значение

итератор на элемент, определяющий верхнюю границу диапазона отсортированы, т.е. d_first + min(last - first, d_last - d_first).
Оригинал:
an iterator to the element defining the upper boundary of the sorted range, i.e. d_first + min(last - first, d_last - d_first).
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

[править] Сложность

O(N·log(min(D,N)), где N = std::distance(first, last), D = std::distance(d_first, d_last) применения cmp.
Оригинал:
O(N·log(min(D,N)), where N = std::distance(first, last), D = std::distance(d_first, d_last) applications of cmp.
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

[править] Пример

Следующие виды Код вектор целых чисел и копирует их в меньших и больших вектор .
Оригинал:
The following code sorts an vector of integers and copies them into a smaller and a larger vector.
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

#include <algorithm>
#include <vector>
#include <functional>
#include <iostream>
 
int main()
{
    std::vector<int> v0{4, 2, 5, 1, 3};
    std::vector<int> v1{10, 11, 12};
    std::vector<int> v2{10, 11, 12, 13, 14, 15, 16};
    std::vector<int>::iterator it;
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
 
    std::cout << "Writing to the smaller vector in ascending order gives: ";
    for (int a : v1) {
        std::cout << a << " ";
    }
    std::cout << '\n';
    if(it == v1.end())
        std::cout << "The return value is the end iterator\n";
 
    it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
                                std::greater<int>());
 
    std::cout << "Writing to the larger vector in descending order gives: ";
    for (int a : v2) {
        std::cout << a << " ";
    }
    std::cout << '\n' << "The return value is the iterator to " << *it << '\n';
}

Вывод:

Writing to the smaller vector in ascending order gives: 1 2 3
The return value is the end iterator
Writing to the larger vector in descending order gives: 5 4 3 2 1 15 16
The return value is the iterator to 15

[править] См. также

виды первых элементов N диапазона
Оригинал:
sorts the first N elements of a range
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]
виды диапазон в порядке возрастания
Оригинал:
sorts a range into ascending order
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]
виды диапазон элементов при сохранении порядка между равными элементами
Оригинал:
sorts a range of elements while preserving order between equal elements
Текст был переведён автоматически через Google Translate.
Вы можете проверить и исправить перевод. Для инструкций кликните сюда.

(шаблон функции) [edit]