高效移除两个已排序vector重复元素并实现文件校验对比

嗨，针对你这个处理两个有序vector<pair<string, string>>重复项的问题，我给你两种解决方案——一种是效率最优的双指针法（完全贴合你说的10万级数据量的高性能需求），另一种是代码更简洁的std::set实现，都能完美达成你的目标：

方法一：双指针法（时间O(n+m)，空间O(1)，最优选择） #

因为你的两个vector已经按文件路径（pair的第一个元素）排好序了，我们可以直接利用这个有序性，用双指针遍历两个容器，在原vector上直接修改，完全不需要额外的大内存开销：

核心逻辑 #

• 用两个指针分别遍历a和b，同时对比当前元素的路径：
  • 若a的元素路径更小：说明这个元素只在a中，保留它，移动a的遍历指针和写入指针
  • 若b的元素路径更小：说明这个元素只在b中，保留它，移动b的遍历指针和写入指针
  • 若路径相同，再对比校验和：
    • 校验和不同：两个元素都保留，各自移动指针
    • 校验和相同：这是要移除的重复项，直接跳过两个元素

代码实现 #

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

void removeDuplicates(std::vector<std::pair<std::string, std::string>>& a, 
                      std::vector<std::pair<std::string, std::string>>& b) {
    int i = 0, j = 0;
    int write_idx_a = 0, write_idx_b = 0;

    while (i < a.size() && j < b.size()) {
        const auto& elem_a = a[i];
        const auto& elem_b = b[j];

        int path_cmp = elem_a.first.compare(elem_b.first);
        if (path_cmp < 0) {
            // a中的元素仅存在于a，保留
            a[write_idx_a++] = elem_a;
            ++i;
        } else if (path_cmp > 0) {
            // b中的元素仅存在于b，保留
            b[write_idx_b++] = elem_b;
            ++j;
        } else {
            // 路径相同，校验和不同则都保留，相同则跳过
            if (elem_a.second != elem_b.second) {
                a[write_idx_a++] = elem_a;
                b[write_idx_b++] = elem_b;
            }
            ++i;
            ++j;
        }
    }

    // 处理a中剩余的元素（这些元素都不在b里）
    while (i < a.size()) {
        a[write_idx_a++] = a[i++];
    }
    // 处理b中剩余的元素
    while (j < b.size()) {
        b[write_idx_b++] = b[j++];
    }

    // 截断vector到实际保留的长度
    a.resize(write_idx_a);
    b.resize(write_idx_b);
}

int main() {
    std::vector<std::pair<std::string, std::string>> a = { {"A","1"}, {"B","2"}, {"C","3"}, {"D","3"}, {"E","5"} };
    std::vector<std::pair<std::string, std::string>> b = { {"A","1"}, {"B","3"}, {"D","3"}, {"E","4"}, {"Z","5"} };

    removeDuplicates(a, b);

    std::cout << "处理后的vector a:\n";
    for (const auto& p : a) {
        std::cout << "{" << p.first << ", " << p.second << "}\n";
    }
    std::cout << "\n处理后的vector b:\n";
    for (const auto& p : b) {
        std::cout << "{" << p.first << ", " << p.second << "}\n";
    }

    return 0;
}

这个方法对于10万级别的数据来说，速度是最快的，因为它只需要一次遍历，而且直接在原容器上操作，没有额外的内存分配。

方法二：std::set简化实现（代码简洁，易维护） #

如果你觉得双指针的逻辑稍显繁琐，也可以用std::set来简化实现。虽然时间复杂度略高（O(n log n + m log n)），但代码逻辑更直观，对于10万级数据来说也完全够用：

核心逻辑 #

• 把其中一个vector的所有元素存入set（pair默认的比较规则正好符合我们的需求：先比路径，再比校验和）
• 用std::remove_if筛选出另一个vector中不在set里的元素，然后截断容器
• 重复这个过程，处理另一个vector

代码实现 #

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

void removeDuplicatesWithSet(std::vector<std::pair<std::string, std::string>>& a, 
                             std::vector<std::pair<std::string, std::string>>& b) {
    // 把a的元素存入set
    std::set<std::pair<std::string, std::string>> set_a(a.begin(), a.end());
    // 移除b中存在于a的重复元素
    auto b_end = std::remove_if(b.begin(), b.end(), [&set_a](const auto& elem) {
        return set_a.count(elem);
    });
    b.erase(b_end, b.end());

    // 再把处理后的b存入set，移除a中的重复元素
    std::set<std::pair<std::string, std::string>> set_b(b.begin(), b.end());
    auto a_end = std::remove_if(a.begin(), a.end(), [&set_b](const auto& elem) {
        return set_b.count(elem);
    });
    a.erase(a_end, a.end());
}

int main() {
    std::vector<std::pair<std::string, std::string>> a = { {"A","1"}, {"B","2"}, {"C","3"}, {"D","3"}, {"E","5"} };
    std::vector<std::pair<std::string, std::string>> b = { {"A","1"}, {"B","3"}, {"D","3"}, {"E","4"}, {"Z","5"} };

    removeDuplicatesWithSet(a, b);

    std::cout << "处理后的vector a:\n";
    for (const auto& p : a) {
        std::cout << "{" << p.first << ", " << p.second << "}\n";
    }
    std::cout << "\n处理后的vector b:\n";
    for (const auto& p : b) {
        std::cout << "{" << p.first << ", " << p.second << "}\n";
    }

    return 0;
}

这个方法的优势是代码逻辑简单，不需要手动处理指针移动，适合快速开发和维护。

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