To boldly go where no one has gone before.

【学习笔记】STLの骚操作

2019-03-26 23:34:23


$\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$来说:

  1. 若$a<b$,就代表$b$的开始时间在$a$的结束时间之后,不会发生冲突;
  2. 若$a>b$,就代表$a$的开始时间在$b$的结束时间之后,也不会发生冲突;
  3. 若$a=b$,就代表$a$与$b$的会议时间发成了冲突。

未完待续