Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Difference between std::merge and std::inplace_merge?

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)

like image 587
Vincent Avatar asked Feb 07 '14 09:02

Vincent


1 Answers

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.

like image 155
SirGuy Avatar answered Oct 23 '22 09:10

SirGuy