$\textbf{STL}$大法好!
虽然说$STL$速度不如手写快,但是当不想码一些比较初级的数据结构的时候就可以用它来偷懒。更重要的是,$STL$所提供的一些容器,以及它们对应的迭代器,它们可以完成手写结构所难以完成的许多对于数据的维护操作。
$\textbf{set}$
$set$就是有序集合容器,可以用来维护一个单调序列,并且保证序列中没有重复元素,这个样子对于去重之类的操作也就太方便了吧!
操作
语句 | 解释 |
---|---|
$s.begin()$ | 返回头迭代器 |
$s.end()$ | 返回尾迭代器 |
$s.insert()$ | 插入元素 |
$s.erase()$ | 删除迭代器指向的元素 |
$s.find()$ | 返回查找元素对应的迭代器,若不存在则返回$s.end()$ |
$s.size()$ | 返回元素个数 |
例题 P2161
这道题乍一看还是比较懵逼的,题解中提到可以用平衡树维护,简单一些的可以用树状数组。但是这些都不及$set$来得快方便。
考虑建立一个结构体$PLAN$,包含$l$和$r$两个元素,并且以骚方式重载小于号:
struct PLAN {
int l, r;
bool operator < (const PLAN &rhs) const {
return r < rhs.l;
}
};
如题解所说,这样定义之后,对于两个结构体$a$、$b$来说:
- 若$a<b$,就代表$b$的开始时间在$a$的结束时间之后,不会发生冲突;
- 若$a>b$,就代表$a$的开始时间在$b$的结束时间之后,也不会发生冲突;
- 若$a=b$,就代表$a$与$b$的会议时间发成了冲突。