What is the difference between std::merge
and std::inplace_merge
in terms of complexity and result when it is executed on two consecutive ranges with elements that are all different ? (I am not a native english speaker and I am not sure to clearly understand what "inplace" means)
Looking at the references for std::merge and std::inplace_merge you see the following complexities:
For std::merge
:
At most std::distance(first1, last1) + std::distance(first2, last2) - 1 comparisons.
And for std::inplace_merge
:
Exactly N-1 comparisons if enough additional memory is available, otherwise N·log(N) where N = std::distance(first, last).
The if enough additional memory is available
has a very specific meaning, from the notes on that page:
This function attempts to allocate a temporary buffer, typically by calling std::get_temporary_buffer. If the allocation fails, the less efficient algorithm is chosen.
std::get_temporary_buffer
allocates memory dynamically (this is important to know if you wanted to use std::inplace_merge
in a tight loop or have constrained memory requirements).
Lastly, the reference pages don't mention this (edit: cppreference has been updated as per the comment below), but in std::merge
I don't think d_first
can can overlap either of [first1, last1)
or [first2, last2)
. This means that std::merge
must output into a different range than either input ranges.
It also means the following call (for some RandomAccessContainer
a
):
std::inplace_merge(a.begin(), a.begin() + n, a.end());
is not equivalent to:
std::merge(a.begin(), a.begin() + n,
a.begin() + n, a.end(), a.begin());
because you can't output into a
if you're reading from it. You would need:
decltype(a) b;
std::merge(a.begin(), a.begin() + n,
a.begin() + n, a.end(),
std::back_inserter(b));
for example.
Interestingly, this reference states that the ranges shall not overlap (just above the return value section) which seems more strict than necessary because it means that the two input ranges also shall not overlap. Furthermore, in the data races section it quite clearly states that the two input ranges are only accessed, so this slightly contrived (artificial) example:
std::merge(a.begin(), a.end(), a.begin(), a.end(), b.begin());
would be illegal according to that, but I'm not convinced. Neither of these references are the standard, and unfortunately I don't have a copy of it to reference myself, but perhaps someone with access can verify these requirements.
EDIT:
With the helpful pointer from TemplateRex to a draft of the standard, I can now say
N3797 25.4.4 [alg.merge]
2 Requires: [...] The resulting range shall not overlap with either of the original ranges.
Which confirms exactly what I was saying.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With