c++ - 分析 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.

我想针对另一个具有相同运行时间的就地算法对其进行分析，所以我的问题简化为:如何模拟“内存不足”，以便在 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 命名空间中为您自己的类专门化它在技术上是不完善的行为，但您可能不会为生产代码执行此操作，并且在实践中它极有可能可靠地工作并且会让你拦截内存请求并返回失败。

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