// <algorithm> 
// 默认(1)    
template <class InputIterator1,
    class InputIterator2, class OutputIterator>
    OutputIterator merge (
        InputIterator1 first1,
        InputIterator1 last1,
        InputIterator2 first2,
        InputIterator2 last2,
        OutputIterator result);
// 自定义(2)    
template <class InputIterator1, class InputIterator2,
    class OutputIterator, class Compare>
    OutputIterator merge (InputIterator1 first1, 
        InputIterator1 last1,
        InputIterator2 first2, 
        InputIterator2 last2,
        OutputIterator result, 
        Compare comp);

合并两个已排序序列,并将结果输出到 result 指向的序列中,且保证结果序列也是按指定方式排序。

该函数等价于:

template<class _InIt1,
class _InIt2,
class _OutIt,
class _Pr> inline
_OutIt _Merge0(_InIt1 _First1, _InIt1 _Last1,
    _InIt2 _First2, _InIt2 _Last2,
    _OutIt _Dest, _Pr _Pred)
{    // copy merging ranges, both using _Pred
    if (_First1 != _Last1 && _First2 != _Last2)
        for (; ; )
        {    // merge either first or second
            if (_DEBUG_LT_PRED(_Pred, *_First2, *_First1))
            {    // merge first
                *_Dest++ = *_First2++;
                if (_First2 == _Last2)
                    break;
            }
            else
            {    // merge second
                *_Dest++ = *_First1++;
                if (_First1 == _Last1)
                    break;
            }
        }
    _Dest = _Copy_impl(_First1, _Last1, _Dest);    // copy any tail
    return (_Copy_impl(_First2, _Last2, _Dest));
}
  • first1last1

    分别指向一个序列中初始及末尾位置的输入迭代器(Input iterators)。这个范围即 [first1,last1) ,包括 first1 到 last1 之间的所有元素,包括 first1 指向的元素,但不包括 last1 指向的元素。

    first2last2

    分别指向一个序列中初始及末尾位置的输入迭代器。这个范围即 [first2,last2) ,包括 first2 到 last2 之间的所有元素,包括 first2 指向的元素,但不包括 last2 指向的元素。

    result

    指向目标序列初始位置的输出迭代器(Output iterators)。该范围长度必须大于或等于  [first1,last1) 、 [first2,last2) 两个范围长度的和。

    所有序列不能有重合。

    comp

    二元谓词(Binary)函数,以两个元素为参数,然后返回一个可转换成 bool 类型的值。

    其返回值表明按所指定的严格弱序排序(Strict weak ordering)时,第一个参数所传进来的元素是否在第二个参数所传进来的元素前面。

    该函数不能修改其参数。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

  • 返回指向目标范围末尾(End,即最后一个元素之后位置的输出迭代器。

  • 如果希望获得与自定义函数谓词、函数对象谓词、对象数组、lambda C++11 表达式、初始化列表 std::initializer_list 等相关的例子,请同时参照 std::sort

    例 1

    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <vector>
    
    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))
    
    namespace ClassFoo{
    
        void Merge_1() {
            // 构造 vector 对象
            CLASSFOO_VECTOR(int, foo, { 8, 23, -5, 7, 29, 0, 7, 7, -7, 1, -1 });
            CLASSFOO_VECTOR(int, bar, { -23, 19, -3, 16, 44  });
            std::vector<int> foobar(foo.size() + bar.size());
    
            // 先排序
            std::sort(foo.begin(), foo.end());
            std::sort(bar.begin(), bar.end());
            // 合并
            std::vector<int>::iterator it = std::merge(
                foo.begin(),
                foo.end(),
                bar.begin(),
                bar.end(),
                foobar.begin()
                );
    
            // 打印 foobar
            std::copy(
                foobar.begin(),
                it,
                std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }
    }
    int main()
    {
        ClassFoo::Merge_1();
        return 0;
    }

    -23 -7 -5 -3 -1 0 1 7 7 7 8 16 19 23 29 44 

  • 复杂度

    O(m - n + 1)m 等值于 std::distance(first1,last1)n 等值于 std::distance(first2,last2)

    数据争用相关

    访问在范围 [first1,last1) 、 [first2,last2) 中的所有元素。

    修改在范围 result 及返回值之间的所有元素。

    异常安全性相关

    如果元素比较、元素赋值或操作某个迭代器抛异常,该函数才会抛异常。

    注意 无效参数将导致未定义行为(Undefined behavior)