如何定义类的operator<以保证set去重、有序
STL 自定义比较器的要求是必须为严格弱序，因为STL内部就是这样做的。
- x<x 为假 (反自反)
- x<y 为真则y<x 为假 (反对称)
- x<y 且y<z 则x<z (传递性)
- x<y 为假且y<x 为假，y<z 为假且z<y 为假，则x<z 为假且z<x 为假 (不可比的传递性)
如果两个关键字都不严格弱序于另一个，则这两个关键字相等。
如果!(a<b)&&!(b<a)，就认为a和b相等，这样就可以保证去重。
在使用set存储自定义类时，重载的operator<兼具了排序和去重的功能，然而使用不当很容易带来错误。
先说结论：
operator<中去重的关键字和排序的关键字必须是相同的(可以是一个或者多个)，否则会出现错误。因为红黑树的插入并不会遍历容器中所有的元素，而是根据operator<的返回值来判断插入的位置，关键字相同的元素也许在插入时并不会比较，而是位于不同分支上，导致并未去重。
一个反例
#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;
}
}
if(this->m_id==right.m_id)
return this->m_hot<right.m_hot;
else
return this->m_id<right.m_id;
}
};
int main()
{
std::set<song> mySet;
song s1(10,100);
song s2(20,200);
song s3(20,50);
song s4(30,200);
mySet.insert(s1);
mySet.insert(s2);
mySet.insert(s3);
mySet.insert(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
id:20,hot:50
end
*/
出错的原因就是
s1(10,100) < s2(20,200)，s4(20,50) < s1(10,100)
但s2(20,200) < s4(20,50)不成立，即不满足传递性，导致二者位于二叉树不同分支，插入时并未遍历到等价的元素，因此看起来与期望的去重不符。