Geek Answers Handbook

Inplace_merge: What causes the complexity of N * log (N) compared to N-1?

From the C ++ documentation in inplace_merge, the complexity of the algorithm is "Linear in comparison (N-1) if an internal buffer is used, NlogN otherwise (where N are numeric elements in the range [first, last])", What do they mean by the internal buffer and what causes the complexity of O (N-1) compared to O (NlogN)?

+4
source share
2 answers

An internal buffer is simply a buffer allocated by a library of sufficient size to store merge output during merging (it is copied back to the original range after the merge is completed). If this extra space is used, the merge can be performed in linear time. If it cannot or does not use a separate buffer for storing output, then the operation worsens to general purpose with O(n log n) runtime.

+1
source

To expand other answers:

  • At least in libstdC ++ and libC ++, an "internal buffer" is provided by calling std::get_temporary_buffer , which is obscure but standard in STL. This procedure is deprecated in C ++ 17, mainly because it is confusing and looks dumb. See this question for details or read the original Stephan T. Lavavej styling proposal .

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

  • In lib ++, get_temporary_buffer is implemented as a call to operator new . (A source)

  • I don’t know if inplace_merge get_temporary_buffer in the MSVC standard library, but I would put money into it.

  • MSVC 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 first-hand 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, 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 bunch.

+1
source

More articles:


All Articles