C++ Algorithm merge()

2024年8月30日 | 阅读4分钟

C++算法merge()函数用于将两个已排序的范围[first1, last1)和[first2, last2)合并为一个从result开始的已排序范围。

对于第一个版本，使用运算符 < 比较元素，或者对于第二个版本，使用给定的二元比较函数 comp 比较元素。

语法

default(1)       template <class InputIterator1, class InputIterator2, class OutputIterator>
                         OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
                             InputIterator2 first2, InputIterator2 last2, OutputIterator result);

custom (2)     template <class InputIterator1, class InputIterator2,
                       class OutputIterator, class Compare>
                   OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
               InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

参数

first1：一个输入迭代器，指向第一个已排序源序列中要合并的第一个元素。

last：一个输入迭代器，指向第一个已排序源序列中要合并的最后一个元素之后的位置。

first2：一个输入迭代器，指向第二个已排序源序列中要合并的第一个元素。

last2：一个输入迭代器，指向第二个已排序源序列中要合并的最后一个元素之后的位置。

comp：一个用户定义的二元谓词函数，接受两个参数，如果这两个参数有序则返回true，否则返回false。它遵循严格的弱排序来对元素进行排序。

val: 用于比较范围内元素的上界值。

result：一个输出迭代器，指向目标范围中的第一个元素，两个源范围将合并成一个单一的已排序范围。

返回值

它返回一个迭代器，指向结果序列中最后一个元素之后的位置。

复杂度

复杂度是线性的：最多执行(last1-first1) + (last2 - first2)次比较并赋值所有元素。

数据竞争

访问范围[first1, last1)和[first2, last2)中的对象。

result和返回值之间的范围内的对象将被更改。

异常

如果元素比较或迭代器操作抛出异常，此函数会抛出异常。

请注意，无效参数会导致未定义行为。

示例 1

让我们看一个简单的例子来演示merge()的使用

#include <iostream>    
#include <algorithm>   
#include <vector>       
using namespace std;
 
void printVector(vector<int>& v)
{
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
        cout << ' ' << *it;
    cout << '\n';
}
 
int main () {
    vector<int> v1 = {5,1,4,2,6}, v2 = {50,40,30,20,10}, v3(10);
 
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
 
    cout << "Vector v1 : ";
    printVector(v1);
    cout << "Vector v2 : ";
    printVector(v2);
    cout << "Vector v3 : ";
    printVector(v3);
    
    return 0;
}

输出

Vector v1 :  1 2 4 5 6
Vector v2 :  10 20 30 40 50
Vector v3 :  1 2 4 5 6 10 20 30 40 50

示例 2

让我们看另一个简单的例子，使用运算符<实现merge()函数

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 
  
int main() 
{ 
    // initializing 1st container 
    vector<int> arr1 = { 1, 4, 6, 3, 2 }; 
  
    // initializing 2nd container 
    vector<int> arr2 = { 60, 20, 50, 70, 10 }; 
  
    // declaring resultant container 
    vector<int> arr3(10); 
  
    // sorting initial containers 
    sort(arr1.begin(), arr1.end()); 
    sort(arr2.begin(), arr2.end()); 
  
    // using merge() to merge the initial containers 
    merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin()); 
  
    // printing the resultant merged container 
    cout << "The container after merging initial containers is: "; 
  
    for (int i = 0; i < arr3.size(); i++) 
        cout << arr3[i] << " "; 
    return 0; 
}

输出

The container after merging initial containers is: 1 2 3 4 6 10 20 50 60 70

示例 3

让我们看另一个简单的例子，使用比较函数演示merge()

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std; 
  
// comparator function to reverse merge sort 
struct greaters { 
    bool operator()(const long& a, const long& b) const
    { 
        return a > b; 
    } 
}; 
  
int main() 
{ 
    // initializing 1st container 
    vector<int> arr1 = { 1, 4, 6, 3, 2 }; 
  
    // initializing 2nd container 
    vector<int> arr2 = { 60, 20, 50, 70, 10 }; 
  
    // declaring resultant container 
    vector<int> arr3(10); 
  
    // sorting initial containers 
    // in descending order 
    sort(arr1.rbegin(), arr1.rend()); 
    sort(arr2.rbegin(), arr2.rend()); 
  
    // using merge() to merge the initial containers 
    // returns descended merged container 
    merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), arr3.begin(), greaters()); 
  
    // printing the resultant merged container 
    cout << "The container after reverse merging initial containers is : "; 
  
    for (int i = 0; i < arr3.size(); i++) 
        cout << arr3[i] << " "; 
    return 0; 
}

输出

The container after reverse merging initial containers is : 70 60 50 20 10 6 4 3 2 1

示例 4

让我们看另一个简单的例子

#include <iostream>    
#include <algorithm>   
#include <vector>       
using namespace std;
 
int main() 
{ 
    // initializing 1st container 
    // containing denominations 
    vector<int> stack1 = { 50, 20, 10, 100, 200 }; 
  
    // initializing 2nd container 
    // containing demonitions 
    vector<int> stack2 = { 500, 2000, 5000, 1000, 10000 }; 
  
    // declaring resultant stack 
    vector<int> stack3(10); 
  
    cout << "The original 1st stack: "; 
    for (int i = 0; i < 5; i++) 
        cout << stack1[i] << " "; 
  
    cout << endl; 
  
    cout << "The original 2nd stack: "; 
    for (int i = 0; i < 5; i++) 
        cout << stack2[i] << " "; 
  
    cout << endl; 
  
    // sorting initial stacks of notes 
    // in descending order 
    sort(stack1.begin(), stack1.end()); 
    sort(stack2.begin(), stack2.end()); 
  
    // using merge() to merge the initial stacks 
    // of notes 
    merge(stack1.begin(), stack1.end(), stack2.begin(), stack2.end(), stack3.begin()); 
  
    // printing the resultant stack 
    cout << "The resultant stack of notes is: "; 
  
    for (int i = 0; i < stack3.size(); i++) 
        cout << stack3[i] << " "; 
    return 0; 
}

输出

The original 1st stack: 50 20 10 100 200 
The original 2nd stack: 500 2000 5000 1000 10000 
The resultant stack of notes is: 10 20 50 100 200 500 1000 2000 5000 10000

下一主题C++ 算法

C++ Algorithm merge()

语法

参数

返回值

复杂度

数据竞争

异常

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Algorithm merge()

语法

参数

返回值

复杂度

数据竞争

异常

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm partial_sort() 函数

algorithm adjacent_find() 函数

algorithm shuffle() 函数

algorithm iter_swap() 函数

algorithm find_if() 函数

algorithm generate() 函数

C++ Thread hardware_concurrency() 函数

algorithm remove_copy_if() 函数

algorithm unique() 函数

algorithm transform() 函数