STL 中给 vector 去重的三种方法

简述： 对 std::vector 中的元素进行去重，其中元素为自定义结构体类型。提供三种思路，并且附上详细示例和分析。关键词内容：

C++ std::unique 函数去重，却导致的 std::vector 发生改变（遇内存泄漏）
c++ std::vector 利用 std::set 去重（自定义结构体创建 set 对象的方法）
自定义结构体在 sort 和 unique 中 比较 / 等于 函数书写（重载、函数、函数对象；严格弱序、相等）

[TOC]

本文初发于 “偕臧的小站“，同步转载于此。

背景

　　在开发防病毒业务中，需要对传入到 vector 中的样本进行去重 ；本篇全程采用 C++ STL 库，未调用 Qt 接口。业务抽象出一个具体例子如下。

构建环境： 💻 win10 21H2 📎 Visual Studio 2019 📎 C++17

去重思路

　　搜索发现，对 std::vector 共分为两种，一种基础数据类型，另一种自定义结构体类型。

基础数据类型

SO 提供三种解决方案，推荐使用第二种。见 What’s the most efficient way to erase duplicates and sort a vector?
自定义结构体类型

实际项目中，这种我们更常遇到，才是所需。余下全文重点讲解此。

解决方案

对于自定义结构体 类型，使用 STL 的 set、sort、unique 时，都是需要自定义其严格弱序的比较函数 或者相等函数 的（此处用 _Pr 表示）。

其中比较函数 _Pr 的实现有三种（附上的完整源码）：

在自定义结构体中 重载 < 函数，简单，参见代码方式一。略
定义一个比较函数，最为常用；亦有用 Lambda 定义；
使用 函数对象，亦简单，属于 2 的变种，在自定义的函数外面套了一层 class 或者 struct 罢了。

PS: 因实际项目中的结构体，没有和无法重载 operator<，故 1 不可用。然后决定采用 2 方式。

而 2 式推荐使用常规声明和定义函数方式，而不使用 Lambda 方式定义；原因是后者在某些算法中会失效。

其中 3 式对于创建 std::set 对象很方便。

『一』vector, sort + unique

思路： 先利用 sort 进行排序，将重复的项使之相邻，然后利用 unique 的属性进行去重。注意点为 unique 去重特性。

// 核心代码
sort(vec.begin(), vec.end(), cmpSort);
auto ite = std::unique(vec.begin(), vec.end(), cmpUnique);
vec.erase(ite, vec.end());

但其中大有文章，所以举一个完整例子：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

struct MyData {
    wstring name;
    wstring md5;
};

bool cmpSort(const MyData& d1, const MyData& d2) {
    return d1.md5 < d2.md5;
};

bool cmpUnique(const MyData& d1, const MyData& d2) {
    return d1.md5 == d2.md5;
};

int main()
{
    vector<MyData> vec = { { L"a1.exe", L"B9204B6362A65C248950D5A41F341DCC"},
                           { L"a2.exe", L"B9204B6362A65C248950D5A41F341DCC"},
                           { L"b1.exe", L"C96D1AA5D314954417C28A645ED72665"},
                           { L"b2.exe", L"C96D1AA5D314954417C28A645ED72665"} };

    wcout.imbue(locale("", LC_CTYPE));
    wcout << L"----------调整前--------" << endl;
    for (const auto& it : vec) 
        wcout << L"[it.name]" << it.name << L"[it.md5]" << it.md5 << endl;

    sort(vec.begin(), vec.end(), cmpSort);
    auto ite = std::unique(vec.begin(), vec.end(), cmpUnique);
    vec.erase(ite, vec.end());

    wcout << L"----------调整后--------" << endl;
    for (const auto& it : vec)  
        wcout << L"[it.name]" << it.name << L"[it.md5]" << it.md5 << endl;
}

运行查看结果，似乎是完美符合预期的？？？可真的如此？

实际它会产生内存泄漏，原因是由于使用的自定义 cmpUnique() 函数导致的，其并未是真正的两个结构体对象相等，且 stackoverflow.com 亦能够佐证 Ref ^[4]

尝试将 cmpUnique() 修改如下，便不再有内存泄漏了，但此功能函数，却也”失效”了，没有起到去重的效果，可以调试自行查验效果

bool cmpUnique(const MyData& d1, const MyData& d2) {
    //return d1.md5 == d2.md5;                          // 此『不严格相等』会内存泄漏
    return d1.md5 == d2.md5 && d1.name == d2.name;      // 此『严格相等』满足语法，却不满足实际业务需求
};

更新

　　本想后面有时间再继续研究下方式一，看看自定义 cmpUnique（） 修改达到严格弱序的要求，能够不会有内存泄漏，亦能够完美符合要求。但心里痒痒，总是还有一点困惑，两天后，半夜睡不着，又起来研究了下。

　　翻了下 std::unique() 的默认第三个参数的默认实现，如图，发现就是直接 == 比较。那就是严格的对象相等，满足语法和编译，但不满足业务的需要，故这个点也没有疑问了。

实际情况复杂得多： 实际的 MyData 结构体是微软的 COM 组件中的 Bundle 结构，每一个**Bundle 对象** 的属性项目的数量和内容都可能不同，仅有少部分重叠。需求为仅只需比较的两三个属性内容是否完全一致，来判断两个对象是否为同重复文件。亦没有提供直接判断两个 Bundle 对象 相等的接口。简直是要要命， Help，Help，Help！！！

综上： 决定弃用此方式，改用下面『方式二』，且最终完成目的。

『二』vector + set（手动赋值）

思路： 很简单，先将 vector 数据导入 set，利用其单一性去重，然后再数据赋值给 vector，完美的思路，亦不会有方式一的内存泄漏。其中难点为给创建 std::set 的对象进行自定义类型排序和赋值。其难点解决方式可参考 Ref^[2]的方式三

其中 std::set 的自定义排序函数 cmpSort()，又分为定义在类外还是类内，若是前者则甚至简单，若是后者，则必须定义为静态成员函数。

cmpSort() 定义在 Class 外

// 核心代码
set<MyData, decltype(cmpSort)*>  s(&cmpSort);   // 此种方式比较少见，且第二个 & 若想省略亦可，则编译器亦会自动添加
for (unsigned i = 0; i < vec.size(); ++i)
	s.insert(vec[i]);
vec.assign(s.begin(), s.end());

注：若偷懒采用 set<MyData, decltype(cmpSort)*> s; 此方式定义对象，则会导致调用 s.insert(vec[i]); 时崩溃，坑。

cmpSort() 定义为 Class 成员变量

这种大概是实际业务中最常遇到的场景，亦是这几种最复杂的一种。

// 核心代码
set<MyData, decltype(DeDuplication::cmpSort)*>  s(&DeDuplication::cmpSort);  // 本行定义为重点
for (unsigned i = 0; i < m_vec.size(); ++i)
    s.insert(m_vec[i]);

m_vec.assign(s.begin(), s.end());

其中 Class DeDuplication 种 cmpSort() 必须为 static 类型，定义如下。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

struct MyData
{
    wstring name;
    wstring md5;
};

class DeDuplication
{
private:
    static bool cmpSort(const MyData& d1, const MyData& d2) {  // ***** 注意，必须是静态 *****
        // Simple example
        return d1.md5 < d2.md5;

        // Complex sample
        //if (d1.md5 != d2.md5)
        //    return d1.md5 < d2.md5;
        //else
        //    return d1.name < d2.name;
    };

public:
    void finally()
    {
        wcout.imbue(locale("", LC_CTYPE));
        wcout << L"----------调整前--------" << endl;
        for (const auto& it : m_vec)
            wcout << L"[it.name]" << it.name << L"[it.md5]" << it.md5 << endl;


        set<MyData, decltype(DeDuplication::cmpSort)*>  s(&DeDuplication::cmpSort);
        for (unsigned i = 0; i < m_vec.size(); ++i)
            s.insert(m_vec[i]);

        m_vec.assign(s.begin(), s.end());

        wcout << L"----------调整后--------" << endl;
        for (const auto& it : m_vec)
            wcout << L"[it.name]" << it.name << L"[it.md5]" << it.md5 << endl;
    };

private:
    vector<MyData>  m_vec = { { L"a1.exe", L"B9204B6362A65C248950D5A41F341DCC"},
                              { L"a2.exe", L"B9204B6362A65C248950D5A41F341DCC"},
                              { L"b1.exe", L"C96D1AA5D314954417C28A645ED72665"},
                              { L"b2.exe", L"C96D1AA5D314954417C28A645ED72665"} };
};

若是普通类型，会导致 std::set 对象编译不过，报错如下，其解释参考 devblogs.microsoft.com Ref^[3]。

Error (active)	E0289	no instance of constructor "std::set<_Kty, _Pr, _Alloc>::set [with _Kty=MyData, _Pr=bool (DeDuplication::**)(const MyData &d1, const MyData &d2), _Alloc=std::allocator<MyData>]" matches the argument list	DeDuplication