如何合并有序无重复vector并保留元素类型与原位置信息？

一、基础需求：合并去重+类型标记 #

已知两个已排序且无重复元素的std::vector<double> v1、v2，v1元素类型标记为1，v2标记为2，要生成合并排序去重后的v3，以及对应的类型向量v3types（元素同时属于两者时标记为3），可借助STL工具实现：

1. 打包元素与类型
   用std::vector<std::pair<double, int>>存储所有元素和对应类型，遍历v1将每个元素存为{val, 1}，遍历v2存为{val, 2}。
2. 排序打包容器
   调用std::sort，默认按pair的第一个元素（即double值）升序排列。
3. 遍历去重生成结果
   遍历排序后的容器，逐个处理元素：
   • 若当前元素值与v3最后一个元素值相同，将v3types的最后一项改为3；
   • 若不同，将当前值加入v3，类型加入v3types。

代码示例 #

#include <vector>
#include <algorithm>

void merge_with_type(const std::vector<double>& v1, const std::vector<double>& v2,
                     std::vector<double>& v3, std::vector<int>& v3types) {
    std::vector<std::pair<double, int>> temp;
    temp.reserve(v1.size() + v2.size());

    // 打包v1元素
    for (double val : v1) {
        temp.emplace_back(val, 1);
    }
    // 打包v2元素
    for (double val : v2) {
        temp.emplace_back(val, 2);
    }

    // 按值排序
    std::sort(temp.begin(), temp.end());

    // 去重并生成结果
    v3.clear();
    v3types.clear();
    for (const auto& elem : temp) {
        if (!v3.empty() && v3.back() == elem.first) {
            // 元素重复，修改类型为3
            v3types.back() = 3;
        } else {
            v3.push_back(elem.first);
            v3types.push_back(elem.second);
        }
    }
}

二、进阶需求：保留原向量的位置信息 #

要保留元素在原向量中的索引（类型3元素需记录两个原索引），需扩展存储结构以记录更多信息：

1. 定义元素详情结构体
   结构体包含值、类型、v1中的索引（仅类型1/3有效）、v2中的索引（仅类型2/3有效）：

   struct ElementDetail {
       double val;
       int type;
       size_t idx_v1;
       size_t idx_v2;
   };
   

2. 打包元素与索引
   遍历v1时，给每个元素赋值type=1，idx_v1为当前循环索引，idx_v2设为无效值（比如std::numeric_limits<size_t>::max()）；遍历v2时，type=2，idx_v2为当前索引，idx_v1设为无效值。
3. 排序后遍历去重，合并索引信息
   排序后遍历，遇到相同值的元素时，将类型改为3，并记录两个向量中的索引。

代码示例 #

#include <vector>
#include <algorithm>
#include <limits>

struct ElementDetail {
    double val;
    int type;
    size_t idx_v1;
    size_t idx_v2;
};

void merge_with_index(const std::vector<double>& v1, const std::vector<double>& v2,
                      std::vector<double>& v3, std::vector<int>& v3types,
                      std::vector<std::pair<size_t, size_t>>& v3_indices) {
    std::vector<ElementDetail> temp;
    temp.reserve(v1.size() + v2.size());

    // 打包v1元素及索引
    for (size_t i = 0; i < v1.size(); ++i) {
        temp.push_back({v1[i], 1, i, std::numeric_limits<size_t>::max()});
    }
    // 打包v2元素及索引
    for (size_t i = 0; i < v2.size(); ++i) {
        temp.push_back({v2[i], 2, std::numeric_limits<size_t>::max(), i});
    }

    // 按值排序
    std::sort(temp.begin(), temp.end(), [](const ElementDetail& a, const ElementDetail& b) {
        return a.val < b.val;
    });

    // 去重并生成结果
    v3.clear();
    v3types.clear();
    v3_indices.clear();
    for (const auto& elem : temp) {
        if (!v3.empty() && v3.back() == elem.val) {
            // 合并类型与索引
            v3types.back() = 3;
            if (elem.idx_v1 != std::numeric_limits<size_t>::max()) {
                v3_indices.back().first = elem.idx_v1;
            }
            if (elem.idx_v2 != std::numeric_limits<size_t>::max()) {
                v3_indices.back().second = elem.idx_v2;
            }
        } else {
            v3.push_back(elem.val);
            v3types.push_back(elem.type);
            v3_indices.emplace_back(elem.idx_v1, elem.idx_v2);
        }
    }
}

说明 #

• 原向量已排序且无重复，相同值的元素最多出现两次（v1和v2各一次），无需处理多次重复场景；
• 用std::numeric_limits<size_t>::max()标记无效索引，后续使用时可通过判断该值确定索引有效性；
• 全程依赖STL容器与算法，实现简单易读，满足性能要求不高的场景。

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