跳到主要内容

C++ 合并操作

在C++编程中，合并操作是一种常见且强大的算法，用于将两个已排序的序列合并为一个新的已排序序列。STL提供了几种不同的合并函数，帮助我们高效地处理数据合并场景。本文将详细介绍C++ STL中的合并操作，包括merge、inplace_merge等算法的使用方法和实际应用。

合并操作的基本概念​

合并操作的核心思想是将两个已排序的序列组合成一个新的已排序序列。这一操作在许多场景下非常有用，例如：

  • 合并两个已排序的数据集
  • 归并排序算法的实现
  • 数据整合与同步处理

STL提供了不同类型的合并函数来满足不同需求，主要包括：

  1. merge - 将两个已排序范围合并到第三个容器中
  2. inplace_merge - 将同一容器中的两个相邻已排序序列原地合并
备注

合并操作的前提条件是输入序列必须已经排序，否则结果将不符合预期。

merge 函数详解​

merge函数可以将两个已排序范围合并到一个目标范围，保持元素的排序状态。

基本语法​

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

// 使用自定义比较函数的重载版本
template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
                     InputIterator2 first2, InputIterator2 last2,
                     OutputIterator result, Compare comp);

参数说明​

  • first1, last1: 第一个已排序范围的起始和结束迭代器
  • first2, last2: 第二个已排序范围的起始和结束迭代器
  • result: 指向目标范围起始位置的迭代器
  • comp: 可选的比较函数，用于自定义排序规则

使用示例​

下面是一个简单的使用merge函数合并两个已排序向量的例子：

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

int main() {
    // 创建两个已排序的向量
    std::vector<int> vec1 = {1, 3, 5, 7, 9};
    std::vector<int> vec2 = {2, 4, 6, 8, 10};
    
    // 创建目标向量，需要预先分配足够空间
    std::vector<int> result(vec1.size() + vec2.size());
    
    // 合并两个向量
    std::merge(vec1.begin(), vec1.end(), 
               vec2.begin(), vec2.end(), 
               result.begin());
    
    // 显示合并后的结果
    std::cout << "合并后的结果: ";
    for (const auto& num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

合并后的结果: 1 2 3 4 5 6 7 8 9 10

使用自定义比较函数​

如果你想按照降序而非默认的升序合并序列，可以提供自定义比较函数：

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

int main() {
    std::vector<int> vec1 = {9, 7, 5, 3, 1};
    std::vector<int> vec2 = {10, 8, 6, 4, 2};
    std::vector<int> result(vec1.size() + vec2.size());
    
    // 使用自定义比较函数合并两个向量（降序）
    std::merge(vec1.begin(), vec1.end(), 
               vec2.begin(), vec2.end(), 
               result.begin(), 
               [](int a, int b) { return a > b; });
    
    std::cout << "降序合并结果: ";
    for (const auto& num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

降序合并结果: 10 9 8 7 6 5 4 3 2 1

inplace_merge 函数详解​

inplace_merge函数用于将同一容器中的两个连续的已排序序列原地合并为一个排序序列，不需要额外的存储空间。

基本语法​

cpp
template <class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
                   BidirectionalIterator middle,
                   BidirectionalIterator last);

// 使用自定义比较函数的重载版本
template <class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
                   BidirectionalIterator middle,
                   BidirectionalIterator last,
                   Compare comp);

参数说明​

  • first: 序列起始位置迭代器
  • middle: 分隔两个已排序子序列的中间迭代器
  • last: 序列结束位置迭代器
  • comp: 可选的比较函数，用于自定义排序规则

使用示例​

下面演示如何使用inplace_merge合并同一容器中的两个已排序子序列：

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

int main() {
    // 创建一个向量，包含两个已排序的子序列
    std::vector<int> vec = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    
    // 找到中间点，分隔两个已排序子序列
    auto middle = vec.begin() + 5; // 指向值2的位置
    
    // 原地合并两个子序列
    std::inplace_merge(vec.begin(), middle, vec.end());
    
    // 显示合并后的结果
    std::cout << "原地合并后的结果: ";
    for (const auto& num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

原地合并后的结果: 1 2 3 4 5 6 7 8 9 10

合并操作的应用场景​

1. 实现归并排序​

合并操作是归并排序的核心，下面是一个简单的归并排序实现：

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

void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // 递归排序左半部分和右半部分
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // 合并已排序的子数组
        std::inplace_merge(arr.begin() + left, arr.begin() + mid + 1, arr.begin() + right + 1);
    }
}

int main() {
    std::vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    
    std::cout << "排序前: ";
    for (const auto& num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    mergeSort(arr, 0, arr.size() - 1);
    
    std::cout << "排序后: ";
    for (const auto& num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

排序前: 38 27 43 3 9 82 10 
排序后: 3 9 10 27 38 43 82

2. 数据库结果合并​

在处理数据库查询结果时，我们经常需要合并多个有序结果集：

cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

// 表示数据库记录的简单结构
struct Record {
    int id;
    std::string name;
    
    // 重载比较运算符，按ID排序
    bool operator<(const Record& other) const {
        return id < other.id;
    }
};

// 打印记录
void printRecords(const std::vector<Record>& records, const std::string& title) {
    std::cout << title << ":\n";
    for (const auto& record : records) {
        std::cout << "ID: " << record.id << ", Name: " << record.name << "\n";
    }
    std::cout << std::endl;
}

int main() {
    // 模拟从两个不同数据源获取的已排序记录
    std::vector<Record> records1 = {
        {1, "Alice"}, {3, "Charlie"}, {5, "Eve"}
    };
    
    std::vector<Record> records2 = {
        {2, "Bob"}, {4, "Dave"}, {6, "Frank"}
    };
    
    // 合并记录
    std::vector<Record> mergedRecords(records1.size() + records2.size());
    std::merge(records1.begin(), records1.end(),
               records2.begin(), records2.end(),
               mergedRecords.begin());
    
    // 打印合并后的记录
    printRecords(records1, "第一组记录");
    printRecords(records2, "第二组记录");
    printRecords(mergedRecords, "合并后的记录");
    
    return 0;
}

输出结果：

第一组记录:
ID: 1, Name: Alice
ID: 3, Name: Charlie
ID: 5, Name: Eve

第二组记录:
ID: 2, Name: Bob
ID: 4, Name: Dave
ID: 6, Name: Frank

合并后的记录:
ID: 1, Name: Alice
ID: 2, Name: Bob
ID: 3, Name: Charlie
ID: 4, Name: Dave
ID: 5, Name: Eve
ID: 6, Name: Frank

3. 增量数据处理​

在处理增量数据时，我们可以使用合并操作高效地将新数据整合到现有数据中：

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

int main() {
    // 已有的排序数据
    std::vector<int> existingData = {1, 3, 5, 7, 9, 11, 13};
    
    // 新的排序数据（增量）
    std::vector<int> newData = {2, 4, 6, 8, 10};
    
    std::cout << "已有数据: ";
    for (const auto& num : existingData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    std::cout << "新增数据: ";
    for (const auto& num : newData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 保存原始大小并扩展容器以容纳新数据
    size_t originalSize = existingData.size();
    existingData.resize(originalSize + newData.size());
    
    // 将新数据复制到现有数据的末尾
    std::copy(newData.begin(), newData.end(), existingData.begin() + originalSize);
    
    // 对整个数据集进行合并
    std::inplace_merge(existingData.begin(), existingData.begin() + originalSize, existingData.end());
    
    std::cout << "合并后的数据: ";
    for (const auto& num : existingData) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

已有数据: 1 3 5 7 9 11 13 
新增数据: 2 4 6 8 10 
合并后的数据: 1 2 3 4 5 6 7 8 9 10 11 13

合并操作的性能考虑​

使用STL合并操作时，需要考虑以下性能因素：

  1. 时间复杂度：

    • merge: O(n)，其中n是两个输入范围的总元素数
    • inplace_merge: 最坏情况下O(n log n)，但如果有足够辅助内存则为O(n)

  2. 空间复杂度：

    • merge: 需要O(n)的额外空间来存储结果
    • inplace_merge: 在最佳情况下，如果有足够的辅助内存，需要O(n)的额外空间；否则只使用O(1)的额外空间，但时间复杂度会增加
提示

对于大型数据集，如果内存允许，使用merge可能比inplace_merge更快，因为它不需要进行元素的移动和重排。

注意事项与最佳实践​

  1. 确保输入序列已排序：合并操作的前提是输入序列已经排序，否则结果将不可预期。

  2. 预先分配目标容器空间：使用merge时，确保目标容器已分配足够空间，这可以通过resize()或reserve()实现。

  3. 考虑使用并行算法：C++17引入了并行版本的算法，可以通过执行策略加速合并操作：

    cpp
    #include <execution> // C++17

    std::merge(std::execution::par, // 并行执行
               vec1.begin(), vec1.end(),
               vec2.begin(), vec2.end(),
               result.begin());

  4. 避免不必要的复制：如果可能，考虑使用移动语义或引用来减少不必要的对象复制。

总结​

本文详细介绍了C++ STL中的合并操作，包括merge和inplace_merge函数的用法和应用场景。合并操作是处理有序数据的强大工具，特别适用于以下场景：

  • 实现归并排序等高效排序算法
  • 合并来自多个来源的有序数据
  • 高效处理增量数据更新
  • 数据库操作和结果集合并

通过合理使用这些合并操作，可以编写更高效、更优雅的代码来处理各种数据合并需求。

练习与拓展​

  1. 实现一个函数，合并两个按字母顺序排序的名称列表，去除重复项。
  2. 修改归并排序示例，使其支持对自定义类型的排序。
  3. 实现一个程序，从多个排序文件中读取整数，并将它们合并到一个文件中。
  4. 尝试比较merge和inplace_merge在不同数据大小下的性能差异。

相关资源​

  • C++标准库中的其他算法，如set_union、set_intersection、set_difference等也可以用于处理已排序序列的集合操作。
  • 对于多路合并（合并超过两个序列），可以考虑使用优先队列或重复应用二路合并。
警告

记得在使用合并操作前引入相应的头文件：#include <algorithm>