std::merge

定义于头文件 `<algorithm>`
template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );	(1)	(从 C++20 起为 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first );	(2)	(C++17 起)
template< class InputIt1, class InputIt2, class OutputIt, class Compare > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Compare comp );	(3)	(从 C++20 起为 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3, class Compare > ForwardIt3 merge( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, ForwardIt3 d_first, Compare comp );	(4)	(C++17 起)

将两个已排序范围 [first1, last1) 和 [first2, last2) 合并为一个始于 d_first 的已排序范围。

1) 如果 [first1, last1) 或 [first2, last2) 没有按照排序（(C++20 前)operator<(C++20 起)std::less{}），则行为未定义。3)

如果或 [first1, last1) 没有按照 [first2, last2) 排序，则行为未定义。comp2,4)

同 (1,3)，但按照执行。policy 这些重载只有在下列表达式的值为

时才参与重载决议： true(C++20 前)

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(C++20 起)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	此合并函数是稳定的，这意味着对于原两个范围中等价的元素，来自第一个范围的元素（保持其原始顺序）排在来自第二个范围的元素（保持其原始顺序）之前。

如果输出范围与

或 [first1, last1) 重叠，则行为未定义。 [first2, last2)内容

first1, last1

-	定义要合并的第一个	范围的迭代器对 first2, last2
-	定义要合并的第二个	范围的迭代器对 d_first
-	目标范围起始	policy
-	要使用的	执行策略 comp
-	比较函数对象（即满足	Compare 要求的对象），如果第一个参数小于`true`（即排在前）第二个，则返回。比较函数的签名应等价于以下内容：虽然签名不需要有 `bool cmp(const Type1& a, const Type2& b);` ，但函数不能修改传递给它的对象，且必须能接受 (const) `const&` 和 `Type1` 类型的所有值，无论 `Type2`值类别如何（因此不允许`Type1&`，也不允许`Type1`，除非 `Type1`移动等价于复制(C++11 起)）。类型 `Type1` 和 `Type2` 必须使得 `InputIt1` 和 `InputIt2` 类型的对象可以被解引用并隐式转换到 `Type1` 和 `Type2`。
类型要求
- `InputIt1, InputIt2` 必须满足 LegacyInputIterator 的要求。
- `ForwardIt1, ForwardIt2, ForwardIt3` 必须满足 LegacyForwardIterator 的要求。
- `OutputIt` 必须满足 LegacyOutputIterator 的要求。
- `Compare` 必须满足 Compare 的要求。

返回值

指向最后一个复制元素之后位置的输出迭代器。

复杂度

令 $\scriptsize N_1$ $N 1$ 为 std::distance(first1, last1)，$\scriptsize N_2$ $N 2$ 为 std::distance(first2, last2)：

1) 最多

N 1 +N 2 -1

次比较，使用 operator<(C++20 前)std::less{}(C++20 起)。

2)

O(N 1 +N 2)

次比较，使用 operator<(C++20 前)std::less{}(C++20 起)。

3) 最多

N 1 +N 2 -1

次比较函数 comp 调用。

4)

O(N 1 +N 2)

次比较函数 comp 调用。

异常

带有模板参数名为 ExecutionPolicy 的重载按如下方式报告错误：

如果作为算法一部分调用的函数抛出异常，且 ExecutionPolicy 是标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为由实现定义。
如果算法无法分配内存，则会抛出 std::bad_alloc。

可能的实现

另请参阅 libstdc++ 和 libc++ 中的实现。

merge (1)

template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        
        if (*first2 < *first1)
        {
            *d_first = *first2;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

merge (3)

template<class InputIt1, class InputIt2,
         class OutputIt, class Compare>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first, Compare comp)
{
    for (; first1 != last1; ++d_first)
    {
        if (first2 == last2)
            return std::copy(first1, last1, d_first);
        
        if (comp(*first2, *first1))
        {
            *d_first = *first2;
            ++first2;
        }
        else
        {
            *d_first = *first1;
            ++first1;
        }
    }
    return std::copy(first2, last2, d_first);
}

注解

此算法的任务与 std::set_union 类似。两者都消耗两个已排序的输入范围，并生成一个包含两个输入元素的已排序输出。这两个算法的区别在于处理来自两个输入范围中比较等价的元素（参见关于 LessThanComparable 的注解）。如果任何等价值在第一个范围中出现 n 次，在第二个范围中出现 m 次，则 std::merge 将输出全部 n + m 次，而 std::set_union 只输出 std::max(n, m) 次。因此 std::merge 输出恰好 std::distance(first1, last1) + std::distance(first2, last2) 个值，而 std::set_union 可能产生更少。

示例

运行此代码

#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

auto print = [](const auto rem, const auto& v)
{
    std::cout << rem;
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
};

int main()
{
    // fill the vectors with random numbers
    std::random_device rd;
    std::mt19937 mt(rd());
    std::uniform_int_distribution<> dis(0, 9);
    
    std::vector<int> v1(10), v2(10);
    std::generate(v1.begin(), v1.end(), std::bind(dis, std::ref(mt)));
    std::generate(v2.begin(), v2.end(), std::bind(dis, std::ref(mt)));
    
    print("Originally:\nv1: ", v1);
    print("v2: ", v2);
    
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    
    print("After sorting:\nv1: ", v1);
    print("v2: ", v2);
    
    // merge
    std::vector<int> dst;
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(dst));
    
    print("After merging:\ndst: ", dst);
}

可能的输出：

Originally:
v1: 2 6 5 7 4 2 2 6 7 0
v2: 8 3 2 5 0 1 9 6 5 0
After sorting:
v1: 0 2 2 2 4 5 6 6 7 7
v2: 0 0 1 2 3 5 5 6 8 9
After merging:
dst: 0 0 0 1 2 2 2 2 3 4 5 5 5 6 6 6 7 7 8 9

缺陷报告

以下行为变更的缺陷报告已追溯应用于之前发布的 C++ 标准。

DR	应用于	发布时的行为	正确行为
LWG 780	C++98	未定义合并操作	已定义

参阅

inplace_merge	原地合并两个已排序范围 (函数模板 & 算法函数对象)
ranges::inplace_merge (C++20)	原地合并两个已排序范围 (函数模板 & 算法函数对象)
is_sorted (C++11)	检查范围是否已排序 (函数模板 & 算法函数对象)
ranges::is_sorted (C++20)	检查范围是否已排序 (函数模板 & 算法函数对象)
set_union	计算两个集合的并集 (函数模板 & 算法函数对象)
ranges::set_union (C++20)	计算两个集合的并集 (函数模板 & 算法函数对象)
sort	对范围中的元素进行排序 (函数模板 & 算法函数对象)
ranges::sort (C++20)	对范围中的元素进行排序 (函数模板 & 算法函数对象)
stable_sort	对范围中的元素进行排序，同时保持等价元素之间的相对顺序 (函数模板 & 算法函数对象)
ranges::stable_sort (C++20)	对范围中的元素进行排序，同时保持等价元素之间的相对顺序 (函数模板 & 算法函数对象)
ranges::merge (C++20)	合并两个已排序范围 (算法函数对象)

编译器支持
独立与托管实现
语言
标准库
标准库头文件
具名要求
功能特性测试宏 (C++20)
语言支持库
概念库 (C++20)
诊断库
内存管理库
元编程库 (C++11)
通用工具库
容器库
迭代器库
范围库 (C++20)
算法库
字符串库
文本处理库
数值库
日期时间库
输入/输出库
文件系统库 (C++17)
并发支持库 (C++11)
执行控制库 (C++26)
技术规范
符号索引
外部库

zh.cppreference.net

Namespaces

Variants

std::merge

1

first1, last1

返回值

复杂度

异常

可能的实现

注解

示例

缺陷报告

参阅