• STL 中给 vector 去重的三种方法

    文章目录

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

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

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


    背景

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

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


    去重思路

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

    1. 基础数据类型

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

    2. 自定义结构体类型

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


    解决方案

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

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

    1. 在自定义结构体中 重载 < 函数，简单，参见代码方式一。略
    2. 定义一个比较函数，最为常用；亦有用 Lambda 定义；
    3. 使用 函数对象，亦简单，属于 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());

    • 1
    • 2
    • 3
    • 4

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

    #include 
#include 
#include 
#include 
#include 
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

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

    实际它会产生内存泄漏，原因是由于使用的自定义 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;      // 此『严格相等』满足语法，却不满足实际业务需求
};

    • 1
    • 2
    • 3
    • 4

    更新

    本想后面有时间再继续研究下方式一，看看自定义 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());

    • 1
    • 2
    • 3
    • 4
    • 5

    注： 若偷懒采用 set 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());

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

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

    #include 
#include 
#include 
#include 
#include 
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"} };
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    若是普通类型，会导致 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]" matches the argument list	DeDuplication

    • 1

    『三』vector + set（构造函数）

    其性能不如『方式二』，略，可参见 Ref[1] 种的第三种。


    总结

    最后结合实际，采用方式二的　class 内定义 static 此方式最合宜解决此问题。且附上完整源码。

    1. 方式一和方式二的类外定义，见完整源码的项目 Unique

    2. 方式二的类内定义，见完整源码的项目 DeDuplication

    3. 对于给 std::set 创建自定义结构体对象，可见 STL 的 std::set 创建自定义结构体的对象，定义严格弱序的比较函数


    系列地址

    QtExamples 【DeDuplication】

    欢迎 star ⭐ 和 fork 🍴这个系列的 C++ / QT / DTK 学习，附学习由浅入深的目录。


    Ref

    [1]: What’s the most efficient way to erase duplicates and sort a vector?

    [2]: C++ set自定义排序

    [3]: Error C3867: non-standard syntax; use ‘&’ to create a pointer to member: What it means and how to fix it

    [4]: eliminating duplicates from vector of custom object - std:unique causes crash on free

  • 相关阅读:
    云原生 | kubernetes - Ingress
    解码华胜天成战略升级，如何从“做大”到“做强”、“做优”
    Breakpad Windows 集成概述
    Visual Studio自定义模板参数、备注
    【1++的Linux】之文件（一）
    【Linux】基本的指令(终章)
    Linux：firewalld防火墙-(实验2)-IP伪装与端口转发（4）
    二维数组练习
    基于SpringBoot和Leaflet的地震台网信息预警可视化
    c++初始之二
  • 原文地址：https://blog.csdn.net/qq_33154343/article/details/126322011