inplace_merge:是什么导致N * log(N)与N-1的复杂度? [英] inplace_merge: What causes a complexity of N*log(N) vs. N-1?

问题描述

根据inplace_merge上的C ++文档，该算法的复杂度为如果使用内部缓冲区，则比较为线性(N-1)，否则为NlogN(其中N为[first，last)范围内的数字元素)" .内部缓冲区是什么意思?什么导致O(N-1)与O(NlogN)的复杂性?

解决方案

展开其他答案:

• 至少在libstdc ++和libc ++中，通过调用此问题，或阅读(源)

• 在libc ++中，get_temporary_buffer被实现为对operator new的调用. (源)

• 我不知道inplace_merge是否在MSVC的标准库中使用get_temporary_buffer，但是我敢打赌它会这样做.

• 在MSVC中，已已报告 get_temporary_buffer被实现为对operator new的调用.

您可以编写程序到通过覆盖operator new来直接查看对operator 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.

From C++ documentation on inplace_merge, the complexity of the algorithm is "Linear in comparisons (N-1) if an internal buffer was used, NlogN otherwise (where N is the number elements in the range [first,last))". What do they mean by an internal buffer and what causes a complexity of O(N-1) vs. O(NlogN)?

解决方案

To expand on the other answer(s):

• At least in libstdc++ and libc++, the "internal buffer" is provided by calling std::get_temporary_buffer, an obscure yet standard routine in the STL. This routine has been deprecated in C++17, basically because it's confusing and kind of dumb. See this question for details, or read Stephan T. Lavavej's original deprecation proposal.

• In libstdc++, get_temporary_buffer is implemented as a call to operator new. (Source)

• In libc++, the get_temporary_buffer is implemented as a call to operator new. (Source)

• I don't know whether inplace_merge uses get_temporary_buffer in MSVC's standard library, but I would bet money that it does.

• In MSVC, it has been reported that get_temporary_buffer is implemented as a call to operator new.

You can write a program to observe this call to operator new firsthand by overriding operator new in the global namespace:

#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: The "internal buffer" is allocated on the heap by calling operator new. Implementations are not required to call operator new, but in practice they all do. Stay far, far away from inplace_merge if you value your heap.

这篇关于inplace_merge:是什么导致N * log(N)与N-1的复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！