C++杂谈：STL

五一快乐。终于有时间整理一点东西了，笔者这个五一过得是相当初生。大部分人都玩去了，只有我还在赶ddl的世界达成了qwq。不过我觉得还是做了自己想做的事情的。

稍微记录一些前段时间OOP遇到的STL里面乱七八糟的东西。

STL的一些底层实现

• vector 这个谁都知道，是一个堆上分配的数组，容量不够时进行倍增。均摊\(O(1)\).
• list 双向链表。
• map && set 一般认为是红黑树。区别在于，map的节点有两个键值，是关于键的红黑树。
• unorder系列 一般认为所有无序容器都是hash表实现的，用散列表解决冲突（就是一堆链表那种）
• deque 与vector不同，双端队列需要支持两侧的操作，它是堆上的分段连续内存构成的；也就是说，当前面/后面内存不够的时候，在堆中的其他位置申请一块定长的内存，另外有一个指针数组来维护这些定长内存的位置，使它看上去像是连续的。

find && find_if

find和find_if是完全不同的两个东西。find是STL里面很多容器都实现了的方法，是考虑了相应的数据结构的。比如在set上进行的查找就是\(O(logN)\)的复杂度。find_if则是STL标准算法库里面的东西，它是一个泛型算法，也就是不会考虑所作用的数据结构的特征。它的使用方式是

auto iterator = find_if(begin_iterator, end_iterator, condition);

其中condition是判定条件，大部分情况下是一个lambda函数。所执行的操作实际上是遍历\([begin\_iterator,end\_iterator)\)之间的元素，遇到第一个满足condition的元素就返回指向该元素的迭代器。也就是说，它永远是\(O(N)\)的。

另外find_if还有一个很隐蔽的问题，它返回的是const_iterator。即使显式声明

set<int>::iterator it = find_if(s.begin(), s.end(), condition);

迭代器也会被隐式地改成const_iterator，无法使用find_if的返回值进行元素的修改。

总而言之一句话，少用find_if。如果有非用不可的场景，十有八九是没有用到正确的容器。

STL的性能

STL的性能是一个谜一样的话题，我现在听到的说法是STL的性能一般，主要是由于STL有很多的安全检查；但我也没找到安全检查的开关。从个人在数据结构的实验中来看，STL确实不如手写的快，但是一般用vector这样的容器只要没有很多的resize操作都是不会死的。