我们可以使用 std::sort std::unique 和 std::lower_bound 配合使用来实现离散化. 首先复制一份待离散化的数据到另一个数组, 然后对该数组进行排序并去重, 然后可以选择 $O(nlog(n))$ 预处理至一个数组保存并在 $O(1)$ 时间内相应查询, 或者不预处理每次直接 $O(log(n))$ 查询. 查询与预处理的过程都是拿数据在排序并去重后的数组中二分查找, 然后将返回的指针减去数组起始位置的指针来获得下标. 这个下标的值即为离散化后的值.
3.2 快速清空容器适配器如上文所述, 容器适配器都**丧病地不支持清空操作, 这时很多OIer为了清空就会写出酱婶的袋马:
while(!q.empty()){ q.pop(); }
看起来就很低效的样子(虽然对于栈和队列来说时间复杂度达到了理论下界, 但是常数显然比直接清空要大, 至于优先队列就直接从 $O(n)$ 挂成 $O(nlog(n))$ 了...)
这种时候就应该上我们的万能STL容器清空函数(雾)
template<class T> void Clear(T& x){ T tmp; std::swap(tmp,x); }
简洁, 清晰(大雾)
可以看到我们在函数内声明了一个局部对象 $tmp$, 该对象类型与参数相同. 这个新建的容器必定为空, 所以我们交换了两个对象的值. (注:由于STL容器都特化了 std::swap 的实现所以不用担心时间复杂度问题) 然后巧妙的地方在于, $tmp$ 在函数执行结束后自动析构, 也就是带着 $x$ 原来的值自动析构了...
然后由于我们传的是引用所以我们华丽丽地获得了一个新的空的容器 $x$
3.3 快速删除堆/优先队列队中的元素有时候我们会使用堆或者优先队列来进行一些扫描/贪心/优化等过程, 然而有时候我们可能会需要删除堆中的元素而非堆顶. 然而STL的堆并不提供这些函数, 而手写堆似乎也不好实现. 这时我们可以采取一些奇怪的思路: 建立一个 "垃圾堆" , 每次要删除堆中的某个元素时直接压入垃圾堆顶, 而从原堆堆顶取元素时判断一下:
1.如果两堆堆顶相等则直接同时弹出;
2.如果原堆堆顶小于垃圾堆堆顶则说明曾经有一个试图删除的值在原堆中不存在, 弹掉垃圾堆堆顶;
3.如果原堆堆顶大于垃圾堆堆顶, 原堆堆顶保证存在, 该值即为真正的堆顶.
以上算法正确性应该不难理解. 此处不再给出详细证明(其实就是懒)
3.4 STL性能相关可能许多OIer都有一个错误的观念: STL慢出翔, 除了一个 std::sort 可以吊打手写之外经常被卡常
卡常出题人本就该被挂起来裱, 神特么有理有据的底层优化(大雾)
然而真实结果是: 不.
为什么STL平常看起来那么慢?
STL容器，只要会给你迭代器用的，都会在debug模式下内置一个线程安全的链表，对内置一个链表，用来保存送出去的迭代器，每次你的迭代器操作都会进这个链表里线性扫描一遍，检查下你的迭代器是否合法，线程安全的哦，有锁的哦，这个链表还自带allocator的哦
STL算法，只要用了比较器的，debug运行时，每次调用之前，都会对你的比较器进行几次余先验证，验证比较器对于这一组数据是不是真满足偏序关系/等价关系
STL容器本身用了各种traits技术和函数重载进行转发，高度依赖编译内联优化作者：匿名用户
链接：https://www.zhihu.com/question/51650118/answer/126855487
来源：知乎
(摊手)
关掉Debug并开-O2之后基本不可能有谁的手写代码能做到STL的速度.
还好, 现在各路OI比赛都开始向前看并滋磁O2优化了而且优化之后跑得比港记快到不知哪里去了
配合HE省超神评测姬基本无敌的存在233333 ( $10^{10}$ 循环只跑 $4s$ 的六代i5就问你怂不怂....)
以及一些必定吊打手写的库函数:
std::sort std::swap std::min std::max
上面几个简单函数不要想着手写, 直接调库...
对于 std::swap , 可能有的OIer学习 lrj dalao使用这样的写法:
void Swap(int& a,int& b){ a^=b^=a^=b; }
然后你发现你UB了...非常容易炸的写法.
就算你拆开每一行让它不UB:
void Swap(int& a,int& b){ a^=b; b^=a; a^=b; }
然而只是凭空拖慢速度罢了...
为啥呢? 正是因为多了那三次看起来很奇技淫巧的位运算...因为库函数优化后直接在寄存器里mov然后扔RAM完事w
而且还会存在一个严重的问题: Swap同一个变量的时候会把它Swap成 $0$ ......(突然滑稽.png)
4.结语
STL是个非常有用的C++特性, 只要正确使用, 不仅可以提高代码精简程度, 还可以将你的精力聚焦到核心算法而不是一些其他的细节, 并由此提高做题速度与算法能力. 本文仅仅做了很简单的介绍就已经长到了这样的地步, 可想而知STL还有更深的水. 比如库函数的多个重载/自定义内存分配器/自定义执行模式/迭代器和容器的高级用法与嵌套等等. 如果想要深入了解STL的用法与高级特性, 可以参考 cplusplus.com zh.cppreference.com wikipedia 或者直接参考标准文档. 如果为了防止版权争议可以查阅C++14标准发布前的最后一个Working Draft (n4140.pdf)
本文依然不定期更新.
相关文章
精彩导读
热门资讯
关注我们
