set自定义去重函数

如何在set中存储自定义对象?

set是什么

假设你已经在C++中使用过set,那么你应该知道,set中存储的元素是去重的。比如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//来源:公众号:编程珠玑
//作者守望先生
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> a;
a.insert(123);
a.insert(111);
a.insert(111);
a.insert(2);
//遍历set
for(auto &it:a)
{
cout<<it<<endl;
}
return 0;
}

输出结果:

1
2
3
2
111
123

虽然插入了两次111,但是最终只会存储一个,也就是最后set中只有三个元素。

如何在set中存储自定义对象

有时候,我们可能想通过set做一下去重的事情,对于基本数据类型,set都能很好地处理。我们看看对于自定义的对象,它的结果如何呢?

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
//来源:公众号【编程珠玑】
//作者:守望先生
#include <iostream>
#include <set>
using namespace std;
class MyObject
{
//方便起见,暂时设置为public
public:
int id;
string data;
public:
MyObject(int i,string d):id(i),data(d){}
};
int main()
{
set<MyObject> a;
a.insert(MyObject(123,"123"));
a.insert(MyObject(111,"111"));
a.insert(MyObject(111,"111"));
a.insert(MyObject(2,"2"));
for(auto &it:a)
{
cout<<it.id<<endl;
}
return 0;
}

很不幸,还没来得及运行,先报错了。

1
error: no match for ‘operator<’ (operand types are ‘const MyObject’ and ‘const MyObject’)

从报错信息我们可以推断出,它是需要调用‘operator<’,也就是说,我们需要重载操作符<,让它可以用来判断元素是否重复。那么重载它有什么原则呢?
关于操作符的重载,可以参考《》。

重载原则

注意,这里是仅仅介绍去重时的原则,这里暂时未涉及排序。
准则细看有很多,这里总结起来就是:
两个元素如果没有任何一个小于另外一个,则他们视为重复。
假设比较函数是f(x,y),那么当f(x,y)和f(y,x)都返回false的时候,认为他们是重复的。

调用原则

其实,set容器在判定已有元素a和新插入元素b是否相等时,是这么做的:

  • 将x作为左操作数,y作为右操作数,调用比较函数,并返回比较值
  • 将x作为左操作数,y作为右操作数,再调用一次比较函数,并返回比较值。
    如果他们两个都返回false,则认为重复,重复的元素不会被插入到容器中。当然需要注意的是,如果xy应为false,所以这里应该避免两个都返回true,否则将会出现未知行为。

参考实现

对于我们前面的例子来说,假设id重复,则认为对象是相同的,那么重载的<参考实现如下:

1
2
3
4
5
6
7
8
9
10
11
bool operator<(const MyObject &a) const
{
if(this->id == a.id)
{
return false;
}
else
{
return this->id > a.id;
}
}

添加之后,重新运行,就符合预期,可以对自定义对象去重啦!

总结

对于自定义对象存储在set中,如果我们希望它按照我们指定的规则去重,就可能需要重载operator<了,那么是不是只有这一种方法呢?

守望 wechat
关注公众号[编程珠玑]获取更多原创技术文章
出入相友,守望相助!