C++实现多路归并算法高效合并大文件

1. 问题场景与需求分析

在处理大规模文本数据时，我们经常会遇到需要合并多个有序文件的情况。比如日志分析场景中，多个服务节点各自生成按时间排序的日志文件；又或者分布式计算中，不同计算节点输出的中间结果需要合并。这类场景的核心需求是：在保证结果有序性的前提下，高效完成文件合并。

传统做法是先将所有文件内容读入内存排序，但当文件较大时（比如每个文件几个GB），这种方法会消耗大量内存甚至导致OOM。更专业的解决方案是采用外部排序中的多路归并算法，它只需要维护少量内存缓冲区就能处理任意大小的文件。

2. 技术方案设计

2.1 多路归并算法原理

多路归并是外部排序的核心步骤，其工作原理类似于合并两个有序链表，只是扩展到了N个输入源。算法流程如下：

1. 为每个输入文件打开文件流并读取首批数据到内存缓冲区
2. 在所有缓冲区的当前元素中选取最小的输出到结果文件
3. 从对应缓冲区移除已输出的元素，如果缓冲区空了则从对应文件补充新数据
4. 重复步骤2-3直到所有文件都处理完毕

这种方案的优势在于：

• 内存消耗仅与缓冲区大小和文件数量有关，与文件总大小无关
• 只需要顺序读取文件，磁盘IO效率高
• 时间复杂度为O(NlogK)，其中N是总记录数，K是文件数

2.2 C++实现要点

在C++中实现时需要考虑以下关键点：

1. 文件读取方式：使用ifstream进行按行读取，避免一次性加载大文件
2. 缓冲区管理：每个文件对应一个缓冲区队列，典型大小设置为100-1000行
3. 最小值选择：使用优先队列（堆）来高效获取当前最小元素
4. 异常处理：文件打开失败、读取错误等情况的处理
5. 内存控制：监控内存使用，防止缓冲区设置过大导致问题

3. 完整实现代码

cpp复制#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <vector>

using namespace std;

struct FileBuffer {
    ifstream* file;
    string currentLine;
    bool isEmpty;

    // 自定义比较函数用于优先队列
    bool operator>(const FileBuffer& other) const {
        return currentLine > other.currentLine;
    }
};

void mergeSortedFiles(const vector<string>& inputFiles, const string& outputFile) {
    // 1. 打开所有输入文件
    vector<ifstream> inputStreams(inputFiles.size