c++ - inplace_merge：是什么导致 N*log(N) 与 N-1 的复杂性？

Question

从关于 inplace_merge 的 C++ 文档中，算法的复杂性是“如果使用内部缓冲区，则比较线性 (N-1)，否则为 NlogN（其中 N 是 [first,last) 范围内的数字元素）”。内部缓冲区是什么意思，是什么导致了 O(N-1) 与 O(NlogN) 的复杂性？

Answer 1

内部缓冲区只是由库分配的足够大小的缓冲区，以在合并发生时保存合并的输出（合并完成后它被复制回原始范围）。如果使用了这个额外的空间，则可以在线性时间内完成合并。如果它不能或不使用单独的缓冲区来存储输出，则操作会降级为使用 runtime 的通用排序O(n log n)。

Answer 2

要扩展其他答案：

• 至少在 libstdc++ 和 libc++ 中，“内部缓冲区”是通过调用std::get_temporary_bufferSTL 中一个晦涩但标准的例程来提供的。该例程在 C++17 中已被弃用，主要是因为它令人困惑且有点愚蠢。有关详细信息，请参阅此问题，或阅读Stephan T. Lavavej 的原始弃用提案。

• 在 libstdc++ 中，get_temporary_buffer实现为对operator new. （资源）

• 在 libc++ 中，get_temporary_buffer被实现为对operator new. （资源）

• 我不知道是否在 MSVC 的标准库中inplace_merge使用get_temporary_buffer，但我敢打赌它确实如此。

• 据报道，在 MSVC 中，它get_temporary_buffer是作为对operator new.

您可以编写一个程序，通过在全局命名空间中重写来直接观察此调用：operator newoperator new

#include <algorithm>
#include <cstdio>
#include <cstdlib>

void *operator new(size_t nbytes, const std::nothrow_t&) noexcept
{
    puts("hello from operator new!");
    return malloc(nbytes);
}

int main()
{
    int a[32] = {
        1,1,1,2,3,4,4,5,5,5,5,6,6,8,9,9,
        1,1,2,3,3,3,4,4,5,5,7,8,9,9,9,9,
    };
    std::inplace_merge(&a[0], &a[16], &a[32]);  // "hello from operator new!"
    (void)a;
}

TL;DR：通过调用在堆上分配“内部缓冲区” operator new。实现不需要调用operator new，但实际上它们都需要。inplace_merge如果你重视你的堆，请远离，远离。