首先谈谈set,以下是来自cppreference的内容:
std::set 是关联容器,含有 Key 类型对象的已排序集。用比较函数 比较 (Compare) 进行排序。搜索、移除和插入拥有对数复杂度。 set 通常以红黑树实现。
在每个标准库使用比较 (Compare) 概念的场所,用等价关系确定唯一性。不精确地说,若二个对象 a 与 b 相互间既不比较大于亦不比较小于: !comp(a, b) && !comp(b, a) ,则认为它们等价。
复杂度
insert( value_type&& value )以及迭代器访问 与容器大小成对数 O(log(size()))
出人意料(情理之中)的是,如果我们只重载布尔运算符==,是无法通过编译的。stl_function.h [Error] no match for 'operator<' (operand types are 'const edge' and 'const edge')
也就是说我们需要重载<运算符。
C++ 具名要求:比较 (Compare)
要求:
- comp(a, b) 可隐式转换为 bool
- 建立具有下列性质的严格弱序关系:
对于所有 a,comp(a,a)==false
若 comp(a,b)==true 则 comp(b,a)==false
若 comp(a,b)==true 且 comp(b,c)==true 则 comp(a,c)==true
根据网上的一段引用
有了a<b的定义,我们就可以用b<a来判a>b,然后!(a<b)就是a>=b,!(a>b)就是a<=b,!(b<a)&&!(a<b)就是a==b,!(a==b)就是a!=b
以上前四种不等关系,知一推剩下的,至于为什么要重载小于
hyv 2020/9/20 21:37:11
为什么要用小于,大概是个规定吧
或许rbtree需要一个<
struct edge{
int u,v,w;
bool operator <(const edge& b)const{
if(this->u==b.u&&this->v==b.v&&this->w==b.w)return 0;
return 1;
}
};
set<edge>g;
set<edge>::iterator pt;
int n,m,x,y,z;
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
g.insert(edge{x,y,z});
}
for(pt=g.begin();pt!=g.end();pt++)
cout<<pt->u<<" "<<pt->v<<" "<<pt->w<<endl;
return 0;
}

No responses yet