分析 stable_sort

Question

这个 page 告诉我们，每当没有足够的内存时，stable_sort 会减少到运行时间 O(n(log n)(log n) 的就地算法):

_Complexity

If enough extra memory is available, linearithmic in the distance between first and last: Performs up to N*log₂(N) element comparisons (where N is this distance), and up to that many element moves. Otherwise, polyloglinear in that distance: Performs up to N*log₂²(N) element comparisons, and up to that many element swaps.

我想针对另一个具有相同运行时间的就地算法对其进行分析，所以我的问题简化为：如何模拟 "lack of memory" 以便在中执行较慢的算法stable_sort?

Answer 1

cplusplus.com 是出了名的糟糕...查看 cppreference.com 的描述 here

This function attempts to allocate a temporary buffer equal in size to the sequence to be sorted, typically by calling std::get_temporary_buffer. If the allocation fails, the less efficient algorithm is chosen.

get_temporary_buffer 是：

template< class T >
std::pair< T*, std::ptrdiff_t > get_temporary_buffer( std::ptrdiff_t count )

因此，虽然在 std 命名空间中为您自己的 class 专门化它在技术上是不完善的行为，但您可能不会为生产代码执行此操作，并且在实践中它极有可能可靠地工作并让您拦截内存请求和 return 失败。

namespace std
{
    template <>
    std::pair<My_Class*, std::ptrdiff_t>
    get_temporary_buffer(std::ptrdiff_t)
    { return {0, 0}; }
}

分析 stable_sort

Profiling stable_sort

c++

memory

sorting

in-place

_Complexity