c++中std::set自定义去重和排序函数

你的名字 2024-04-18 08:57 69阅读 0赞

c++中的std::set，是基于红黑树的平衡二叉树的数据结构实现的一种容器，因为其中所包含的元素的值是唯一的，因此主要用于去重和排序。这篇文章的目的在于探讨和分享如何正确使用std::set实现去重和排序功能。

方法一：使用std::set内置的less比较函数（直接定义内置类型的set对象）

这种方法适用于：1）比较int、char等内置类型。2）只能针对某一个内置类型去重和排序：如果想通过id（int）去重，并通过hot(int)排序，该种方法就束手无策了。代码如下：

#include <iostream>
    #include <set>
    using namespace std;
    void main()
    {
        std::set<int> mySet;    // 直接定义内置类型set集合
        mySet.insert(10);       // 默认比较函数为less
        mySet.insert(20);       // 从小到大排序
        for(auto it:mySet)    
        {
            std::cout<<it<<std::endl;
        }
        std::cout<<"end"<<std::endl;
    
    }
    
    结果如下：
    output：
        10
        20
        end

方法二：自定义类（结构体）比较函数

前文提到：直接定义内置类型的set对象，即使用std::set内置的默认的less比较函数，可能不能满足我们的实际需求。例如：现在有一批结构体对象，需要将其插入set集合，并按照id去重，按照热度hot进行排序。这个时候，就需要重新自定义比较函数了。有两种方法可以自定义比较函数：

重载<操作符

为甚么要重载<运算符呢？能不能重载”<=”或者”>=”运算符？答案是不可以。几乎所有的方法或容器都需要排序来满足数学意义上的标准严格弱序化，否则这些方法或容器的行为将不可预知。假设f(x,y)是一个比较函数。 如果该函数满足如下条件则它是严格弱序化的。

1. f(x,x) = false; 
    2. if f(x,y) then !f(y,x)
    3. if f(x,y) and f(y,z) then f(x,z)
    4. if !f(x,y)&&!f(y,x) then x==y; if x==y and y==z then x==z;

看上去有点晕乎，不过不用担心，只要你的比较方法能够满足对相等元素永远返回false（记住一个准则：永远让比较函数对相同元素返回false），那你的方法就满足要求了。

其实，set容器在判定已有元素a和新插入元素b是否相等时，是这么做的：   
1）将a作为左操作数，b作为有操作数，调用比较函数，并返回比较值   
2）将b作为左操作数，a作为有操作数，再调用一次比较函数，并返回比较值。

如果1、2两步的返回值都是false，则认为a、b是相等的，则b不会被插入set容器中

如果1、2两步的返回值都是true，则可能发生未知行为

因此，记住一个准则：永远让比较函数对相同元素返回false。

#include <iostream>
    #include <set>
    using namespace std;
    struct song
    {
        int m_id;
        int m_hot;
        song(int id,int hot)
        {
    
            this->m_id = id;
            this->m_hot = hot;
        }
        bool operator<(const struct song & right)const   //重载<运算符
        {
            if(this->m_id == right.m_id)     //根据id去重
                return false;
            else
            {
                if(this->m_hot != right.m_hot)
                {
                    return this->m_hot > right.m_hot;      //降序
                }
                else
                {
                    return this->m_id > right.m_id;     
                }
            }
        }
    };
    void main()
    {
        std::set<song> mySet;
        song s1(10,100);
        song s2(20,200);
        song s3(20,300);
        song s4(30,200);
        mySet.insert(s1);    //插入s1
        mySet.insert(s2);    //插入s2
        mySet.insert(s3);    //s3和s2的id相同，不插入
        mySet.insert(s4);    //插入s4
        for(auto it:mySet)
        {
            std::cout<<"id:"<<it.m_id<<",hot:"<<it.m_hot<<std::endl;
        }
        std::cout<<"end"<<std::endl;
    };
    
    
    结果如下：
    id：30，hot ： 200
    id：20，hot ： 200
    id：10，hot ： 100
    end

重载（）运算符

具体代码如下：

#include <iostream>
    #include <set>
    using namespace std;
    struct song
    {
        int m_id;
        int m_hot;
        song(int id,int hot)
        {
    
            this->m_id = id;
            this->m_hot = hot;
        }
        /*
        bool operator<(const struct song & right)const   //重载<运算符
        {
            if(this->m_id == right.m_id)     //根据id去重
                return false;
            else
            {
                if(this->m_hot != right.m_hot)
                {
                    return this->m_hot > right.m_hot;      //降序
                }
                else
                {
                    return this->m_id > right.m_id;     
                }
            }
        }
        */
    };
    struct comp   
    {
        bool operator()(struct song left,struct song  right)  //重载（）运算符
        {
    
            if(left.m_id == right.m_id)     //根据id去重
                return false;
            else
            {
                if(left.m_hot != right.m_hot)
                {
                    return left.m_hot > right.m_hot;      //降序
                }
                else
                {
                    return left.m_id > right.m_id;     
                }
    
            }
        }
    
    };
    void main()
    {
        std::set<song,comp> mySet;      //写法和2.1中的的区别
        song s1(10,100);
        song s2(20,200);
        song s3(20,300);
        song s4(30,200);
        mySet.insert(s1);    //插入s1
        mySet.insert(s2);    //插入s2
        mySet.insert(s3);    //s3和s2的id相同，不插入
        mySet.insert(s4);    //插入s4
        for(auto it:mySet)
        {
            std::cout<<"id:"<<it.m_id<<",hot:"<<it.m_hot<<std::endl;
        }
        std::cout<<"end"<<std::endl;
    };
    复制代码
    结果如下：
    id：30，hot ： 200
    id：20，hot ： 200
    id：10，hot ： 100
    end

[原文链接][Link 1]

[Link 1]: http://www.cnblogs.com/litaozijin/p/6665595.html