std::partial_sort

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

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

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

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

重新排列元素，使得范围 [first, middle) 包含范围 middle − first 中排序后的 [first, last) 个最小元素。

相等元素的顺序不予保证。范围 [middle, last) 中剩余元素的顺序未指定。

如果满足以下任一条件，则行为未定义：

• [first, middle)或 [middle, last) 不是有效范围。

参数

复杂度

给定 \(\scriptsize M\) M 为 middle - first ， \(\scriptsize N\) N 为 last - first ：

异常

带有名为 ExecutionPolicy 模板参数的重载按以下方式报告错误：

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

可能的实现

另请参阅 libstdc++ 与 libc++ 中的实现。

template<typename RandomIt>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::value_type VT;
    std::partial_sort(first, middle, last, std::less<VT>());
}

namespace impl
{
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void sift_down(RandomIt first, RandomIt last, const Compare& comp)
    {
        // 下沉位于“first”的元素
        const auto length = static_cast<std::size_t>(last - first);
        std::size_t current = 0;
        std::size_t next = 2;
        while (next < length)
        {
            if (comp(*(first + next), *(first + (next - 1))))
                --next;
            if (!comp(*(first + current), *(first + next)))
                return;
            std::iter_swap(first + current, first + next);
            current = next;
            next = 2 * current + 2;
        }
        --next;
        if (next < length && comp(*(first + current), *(first + next)))
            std::iter_swap(first + current, first + next);
    }
    template<typename RandomIt, typename Compare>
    constexpr //< since C++20
    void heap_select(RandomIt first, RandomIt middle, RandomIt last, const Compare& comp)
    {
        std::make_heap(first, middle, comp);
        for (auto i = middle; i != last; ++i)
        {
            if (comp(*i, *first))
            {
                std::iter_swap(first, i);
                sift_down(first, middle, comp);
            }
        }
    }
} // namespace impl
template<typename RandomIt, typename Compare>
constexpr //< since C++20
void partial_sort(RandomIt first, RandomIt middle, RandomIt last, Compare comp)
{
    impl::heap_select(first, middle, last, comp);
    std::sort_heap(first, middle, comp);
}

注释

算法

采用的算法通常使用 堆选择 来选取最小元素，并使用 堆排序 对堆中已选元素进行升序排序。

为了选择元素，使用堆结构（参见 堆 ）。例如，当使用 operator < 作为比较函数时，采用 最大堆 来选取 middle − first 个最小元素。

堆排序 在选择操作后用于对 [ first , middle ) 范围内的选定元素进行排序（参见 std::sort_heap ）。

用途说明

std::partial_sort 算法旨在用于处理 [ first , middle ) 范围内 较小常量数量 的选定元素。

示例

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
void print(const auto& s, int middle)
{
    for (int a : s)
        std::cout << a << ' ';
    std::cout << '\n';
    if (middle > 0)
    {
        while (middle-- > 0)
            std::cout << "--";
        std::cout << '^';
    }
    else if (middle < 0)
    {
        for (auto i = s.size() + middle; --i; std::cout << "  ")
        {}
        for (std::cout << '^'; middle++ < 0; std::cout << "--")
        {}
    }
    std::cout << '\n';
};
int main()
{
    std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    print(s, 0);
    std::partial_sort(s.begin(), s.begin() + 3, s.end());
    print(s, 3);
    std::partial_sort(s.rbegin(), s.rbegin() + 4, s.rend());
    print(s, -4);
    std::partial_sort(s.rbegin(), s.rbegin() + 5, s.rend(), std::greater{});
    print(s, -5);
}

5 7 4 2 8 6 1 9 0 3
0 1 2 7 8 6 5 9 4 3
------^
4 5 6 7 8 9 3 2 1 0
          ^--------
4 3 2 1 0 5 6 7 8 9
        ^----------

缺陷报告

下列行为变更缺陷报告被追溯应用于先前发布的C++标准。

参见