c++ - std::merge 和 std::inplace_merge 之间的区别？

Question

std::merge 和 std::inplace_merge 在复杂度和结果方面有什么区别？不同的 ？ (我不是以英语为母语的人，我不确定是否清楚地理解“就地”是什么意思)

Answer 1

查看 std::merge 的引用资料和 std::inplace_merge您会看到以下复杂性:
对于 std::merge:

At most std::distance(first1, last1) + std::distance(first2, last2) - 1 comparisons.

对于std::inplace_merge:

Exactly N-1 comparisons if enough additional memory is available, otherwise N·log(N) where N = std::distance(first, last).

如果有足够的额外内存可用具有非常具体的含义，来自该页面上的注释:

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 动态分配内存(如果您想在紧密循环中使用 std::inplace_merge 或限制内存需求，这一点很重要)。

最后，引用页面没有提到这一点(edit:cppreference 已根据下面的评论更新)，但在 std::merge 我没有t 认为 d_first 可以重叠 [first1, last1) 或 [first2, last2)。这意味着 std::merge 必须输出到与任一输入范围不同的范围。
这也意味着以下调用(对于某些 RandomAccessContainer a):

    std::inplace_merge(a.begin(), a.begin() + n, a.end());

不等于:

    std::merge(a.begin(), a.begin() + n,
               a.begin() + n, a.end(), a.begin());

因为如果你正在读取它，你就不能输出到 a 中。你需要:

    decltype(a) b;
    std::merge(a.begin(), a.begin() + n,
               a.begin() + n, a.end(),
               std::back_inserter(b));

例如。

有趣的是，this reference声明范围不应重叠(仅在返回值部分上方)，这似乎比必要的更严格，因为这意味着两个输入范围也不应重叠。此外，在数据竞争部分中，它非常清楚地说明了两个输入范围只能访问，所以这个稍微做作(人为)的例子:

    std::merge(a.begin(), a.end(), a.begin(), a.end(), b.begin());

据此将是非法的，但我不相信。这些引用资料都不是标准，不幸的是我自己没有引用资料的拷贝，但也许有访问权限的人可以验证这些要求。

编辑:
借助 TemplateRex 对标准草案的有用指针，我现在可以说

N3797 25.4.4 [alg.merge]

2 Requires: [...] The resulting range shall not overlap with either of the original ranges.

这完全证实了我所说的。