首页 > > 程序设计 > C/C++ >

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

2018-06-17 22:53:48来源：未知阅读 ()

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

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

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

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 void main()
 5 {
 6     std::set<int> mySet;    // 直接定义内置类型set集合
 7     mySet.insert(10);       // 默认比较函数为less
 8     mySet.insert(20);       // 从小到大排序
 9     for(auto it:mySet)    
10     {
11         std::cout<<it<<std::endl;
12     }
13     std::cout<<"end"<<std::endl;
14 
15 }

结果如下：
output：
            10
            20
            end

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

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

　　2.1 重载<操作符

　　　　为甚么要重载<运算符呢？能不能重载"<="或者">="运算符？答案是不可以。几乎所有的方法或容器都需要排序来满足数学意义上的标准严格弱序化，否则这些方法或容器的行为将不可预知。假设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

2.2 重载（）运算符

　　　　　具体代码如下：

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 struct song
 5 {
 6     int m_id;
 7     int m_hot;
 8     song(int id,int hot)
 9     {
10 
11         this->m_id = id;
12         this->m_hot = hot;
13     }
14     /*
15     bool operator<(const struct song & right)const   //重载<运算符
16     {
17         if(this->m_id == right.m_id)     //根据id去重
18             return false;
19         else
20         {
21             if(this->m_hot != right.m_hot)
22             {
23                 return this->m_hot > right.m_hot;      //降序
24             }
25             else
26             {
27                 return this->m_id > right.m_id;     
28             }
29         }
30     }
31     */
32 };
33 struct comp   
34 {
35     bool operator()(struct song left,struct song  right)  //重载（）运算符
36     {
37 
38         if(left.m_id == right.m_id)     //根据id去重
39             return false;
40         else
41         {
42             if(left.m_hot != right.m_hot)
43             {
44                 return left.m_hot > right.m_hot;      //降序
45             }
46             else
47             {
48                 return left.m_id > right.m_id;     
49             }
50 
51         }
52     }
53 
54 };
55 void main()
56 {
57     std::set<song,comp> mySet;      //写法和2.1中的的区别
58     song s1(10,100);
59     song s2(20,200);
60     song s3(20,300);
61     song s4(30,200);
62     mySet.insert(s1);    //插入s1
63     mySet.insert(s2);    //插入s2
64     mySet.insert(s3);    //s3和s2的id相同，不插入
65     mySet.insert(s4);    //插入s4
66     for(auto it:mySet)
67     {
68         std::cout<<"id:"<<it.m_id<<",hot:"<<it.m_hot<<std::endl;
69     }
70     std::cout<<"end"<<std::endl;
71 };

结果如下：
id：30，hot ： 200
id：20，hot ： 200
id：10，hot ： 100
end

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：读书笔记 effective c++ Item 42 理解typename的两种涵义

下一篇：1200 同余方程

IDC资讯：主机资讯注册资讯托管资讯 vps资讯网站建设

网站运营：建站经验策划盈利搜索优化网站推广免费资源

网站联盟：联盟新闻联盟介绍联盟点评网赚技巧

行业资讯：搜索引擎网络游戏电子商务广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器安全防护

软件技巧：其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识：网络协议网络安全网络管理组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条

最新资讯

热门关注

热门标签