如何合并已排序的vector<vector<string>>并生成有序结果？

我有一个vector<vector<string>>类型的容器vecData，其中每个子vector内的元素已经完成排序，示例数据如下：

vecData[0] == {"1","5"}
vecData[1] == {"2","7"}
vecData[2] == {"6","9"}
vecData[3] == {"4"}

希望得到一个合并后的有序vector<string> resVec，预期结果为：

resVec[0] == "1" 
resVec[1] == "2" 
resVec[2] == "4" 
……
resVec[6] == "9"

我尝试了如下代码，但知道这是错误的：

vector<vector<string>> separateFileData;
// 省略初始化代码
vector<string> temp = separateFileData[0];
temp.reserve(1024);
for (auto iter = separateFileData.begin(); iter<separateFileData.end() - 1; iter++)
{
    merge(iter->begin(), iter->end(), (iter+1)->begin(), (iter + 1)->end(), temp.begin());
}

现有代码的问题 #

1. 输出迭代器错误：merge要求输出迭代器指向的空间足够容纳合并后的元素，直接用temp.begin()会覆盖temp原有数据，且temp初始大小仅为第一个子vector的长度，后续合并时空间不足会导致越界。reserve只是预留内存，不会改变容器的实际可用元素数量。
2. 合并逻辑错误：每次循环合并当前vector与下一个vector时，结果直接写入temp会覆盖前一次的合并结果，无法累积所有子vector的元素。

正确解决方案 #

方案一：逐步合并（适合子vector数量不多的场景）

每次将当前合并结果与下一个子vector合并到临时容器，再替换结果容器，避免空间越界问题：

vector<vector<string>> vecData = {{"1","5"}, {"2","7"}, {"6","9"}, {"4"}};
vector<string> resVec;

if (vecData.empty()) {
    return;
}

// 初始化结果为第一个子vector
resVec = vecData[0];

for (size_t i = 1; i < vecData.size(); ++i) {
    vector<string> temp;
    // 用back_inserter自动扩展临时容器空间
    merge(resVec.begin(), resVec.end(),
          vecData[i].begin(), vecData[i].end(),
          back_inserter(temp));
    resVec.swap(temp); // 交换容器避免大量拷贝
}

// 此时resVec即为合并后的有序vector

方案二：优先级队列（多路归并，适合子vector数量多的场景）

如果子vector数量较多，逐步合并的时间复杂度较高，可用最小堆实现高效多路归并：

#include <queue>

// 堆元素结构体：存储值、所在子vector索引、元素在子vector内的索引
struct HeapNode {
    string val;
    size_t vec_idx;
    size_t elem_idx;

    // 重载小于运算符，让优先级队列成为最小堆
    bool operator>(const HeapNode& other) const {
        return val > other.val;
    }
};

vector<string> mergeSortedVectors(const vector<vector<string>>& vecData) {
    vector<string> resVec;
    priority_queue<HeapNode, vector<HeapNode>, greater<HeapNode>> min_heap;

    // 初始化堆：将每个非空子vector的第一个元素加入堆
    for (size_t i = 0; i < vecData.size(); ++i) {
        if (!vecData[i].empty()) {
            min_heap.push({vecData[i][0], i, 0});
        }
    }

    while (!min_heap.empty()) {
        auto node = min_heap.top();
        min_heap.pop();

        resVec.push_back(node.val);

        // 如果当前子vector还有下一个元素，加入堆
        if (node.elem_idx + 1 < vecData[node.vec_idx].size()) {
            size_t next_idx = node.elem_idx + 1;
            min_heap.push({vecData[node.vec_idx][next_idx], node.vec_idx, next_idx});
        }
    }

    return resVec;
}

// 使用示例
vector<vector<string>> vecData = {{"1","5"}, {"2","7"}, {"6","9"}, {"4"}};
vector<string> resVec = mergeSortedVectors(vecData);

内容的提问来源于stack exchange，提问作者Alex