std::partial_sort() 算法

自 C++20 起

// (1)
template< class RandomIt >
constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

// (2)
template< class RandomIt, class Compare >
constexpr void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );

自 C++17 起

// (1)
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

// (2)
template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp );

// (3)
template< class ExecutionPolicy, class RandomIt >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last );

// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
void partial_sort( ExecutionPolicy&& policy, RandomIt first, RandomIt middle, RandomIt last, Compare comp );

C++17 之前

// (1)
template< class RandomIt >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last );

// (2)
template< class RandomIt, class Compare >
void partial_sort( RandomIt first, RandomIt middle, RandomIt last,
                   Compare comp );

按升序对范围 [first; last) 中的部分元素进行排序，并将结果存储在范围 [d_first; d_last) 中。

给定 N 为 min(last - first, d_last - d_first) (要排序的元素数量)

最多有 d_last - d_first 个元素被排序并放置在范围 [d_first; d_first + n) 中。

注意

不保证相等元素的顺序得到保留。

• (1) 元素使用 operator< 进行比较。

• (2) 元素使用给定的二元比较函数 comp 进行比较。

• (3, 4) 与 (1) 和 (2) 相同，但根据策略执行。

  重载决议

  这些重载只有在 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> 为 true 时才参与重载决议。  (C++20 之前) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> 为 true 时才参与重载决议。  (C++20 起)

参数

first last	要部分排序的元素范围。
d_first d_last	目标范围。
policy	要使用的执行策略。有关详细信息，请参阅执行策略。
cmp	比较函数对象（即满足 Compare 要求的对象）。比较函数的签名应等同于以下内容： bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受 (可能是 const) Type 和 Type2 类型的所有值，而不管值类别如何 (因此不允许 Type1&，也不允许 Type1，除非对于 Type1 移动等同于复制 (C++11 起)) `Type1` 和 `Type2` 类型必须是 `RandomIt` 类型的对象可以隐式转换为它们两者的类型。

类型要求

InputIt	LegacyInputIterator
ForwardIt	LegacyForwardIterator
RandomIt	ValueSwappable LegacyRandomAccessIterator
解引用RandomIt的类型	MoveAssignable MoveConstructible
Compare	Compare

返回值

指向定义已排序范围上限的元素的迭代器，即 d_first + min(last - first, d_last - d_first)。

复杂度

comp 的 O(N * log(min(D, N)) 次应用。

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果作为算法一部分调用的函数执行时抛出异常，并且 ExecutionPolicy 是标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

示例

Main.cpp

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

void println(std::string_view rem, auto const& v)
{
    std::cout << rem;
    if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
        std::cout << v;
    else
        for (int e : v)
            std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    const auto 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());
    println("Writing to the smaller vector in ascending order gives: ", v1);

    if (it == v1.end())
        println("The return value is the end iterator", ' ');

    it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
                                std::greater<int>());

    println("Writing to the larger vector in descending order gives: ", v2);
    println("The return value is the iterator to ", *it);
}

输出

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