分析stable_sort

Question

此页面告诉每当内存不足时,stable_sort缩减为具有运行时间O(n(log n)(log n))的就地算法:

_复杂

如果有足够的额外内存可用,则第一个和最后一个之间的距离为线性:执行N*log ₂(N)个元素比较(其中N是此距离),最多可执行多个元素移动.否则,该距离中的多线性:执行N*log ₂ ²(N)个元素比较,最多可执行多个元素交换.

我想将它与另一个具有相同运行时间的就地算法进行分析,因此我的问题简化为:我如何模拟"内存不足"以便执行较慢的算法stable_sort？

Answer 1

cplusplus.com非常糟糕......在这里查看cppreference.com的描述

此函数尝试通常通过调用std :: get_temporary_buffer来分配与要排序的序列大小相等的临时缓冲区.如果分配失败,则选择效率较低的算法.

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}; }
}