Профилирование 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_teilitary_buffer. Если распределение не удается, выбирается менее эффективный алгоритм.

get_temporary_buffer является:

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

Таким образом, в то время как это технически будет недостаточно определенным поведением, специализировать его для своего собственного класса в std namespace, вы, вероятно, не делаете этого для производственного кода, и на практике это очень вероятно, будет работать надежно и позволит вам перехватить запрос памяти и вернуть ошибку.

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