std::merge

来自cppreference.com

This page has been machine-translated from the English version of the wiki using Google Translate.

The translation may contain errors and awkward wording. Hover over text to see the original version. You can help to fix errors and improve the translation. For instructions click here.

Click here for the English version of this page

算法库

功能

修改序列操作

all_of
any_of
none_of

（C++11）
（C++11）
（C++11）

find
find_if
find_if_not

（C++11）

修改序列操作

（C++11）

（C++11）

（C++11）

（C++11）

remove_copy
remove_copy_if

replace
replace_if

replace_copy
replace_copy_if

random_shuffle
shuffle

（C++11）

分区操作

（C++11）

（C++11）

（C++11）

排序操作（排序的区间）

（C++11）

（C++11）

二进制搜索操作（排序的区间）

设置操作（排序的区间）

merge

set_symmetric_difference

堆的操作

（C++11）

最小/最大操作

（C++11）

（C++11）

lexicographical_compare

（C++11）

数字操作

（C++11）

C库

Defined in header `<algorithm>`

template< class InputIt1, class InputIt2, class OutputIt > OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 OutputIt d_first );	(1)

template< class InputIt1, class InputIt2, class OutputIt, class Compare> OutputIt merge( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 OutputIt d_first, Compare comp );	(2)

合并两个已排序的范围[first1, last1)，[first2, last2)成一个有序区间开始在d_first。 operator<的第一个版本使用比较的元素，第二个版本使用给定的比较函数comp。等效的元件的相对顺序被保留.

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);
}

Second version

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);
}

[编辑] 为例

#include <iostream>
#include <iterator>
#include <cstdlib>
#include <algorithm>
#include <vector>
 
int main() 
{
    const std::size_t items = 10;
 
    std::vector<int> v1, v2, dst;
 
    // fill the vectors
    for (std::size_t idx = 0; idx < items; ++idx) {
        v1.push_back(std::rand()%items);
        v2.push_back(std::rand()%items);
    }
 
    // sort
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
 
    // output v1
    std::cout << "v1 : ";
    std::copy(v1.begin(), v1.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // output v2
    std::cout << "v2 : ";
    std::copy(v2.begin(), v2.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
 
    // merge
    std::merge(v1.begin(), v1.end(),
               v2.begin(), v2.end(),
               std::back_inserter(dst));
 
    // output
    std::cout << "dst: ";
    std::copy(dst.begin(), dst.end(),
             std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}

Output:

v1 : 0 0 2 2 3 3 3 6 7 9 
v2 : 1 2 5 5 6 6 6 6 7 9 
dst: 0 0 1 2 2 2 3 3 3 5 5 6 6 6 6 6 7 7 9 9

[编辑] 另请参阅


inplace_merge	合并两个有序的范围内的地方 Original: merges two ordered ranges in-place The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. （函数模板） [edit]

sort	为升序排序范围 Original: sorts a range into ascending order The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. （函数模板） [edit]

stable_sort	排序范围内的元素，同时保持相等的元素之间的顺序 Original: sorts a range of elements while preserving order between equal elements The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. （函数模板） [edit]

语言
概念
实用工具库
字符串库
集装箱库
算法库
迭代器库
Numerics库
输入/输出库
本地化库
正则表达式库（C++11）
原子操作库（C++11）
线程的支持库（C++11）

cppreference.com

搜索

名字空间

变换

查看

操作

std::merge

目录

[编辑] 参数

[编辑] 返回值

[编辑] 复杂性

[编辑] 可能的实现

[编辑] 为例

[编辑] 另请参阅

导航

工具箱