Learning a Part of C++(for ACM/ICPC) (5) STL概览

Finally，花了这么多时间，做足了有的没的的铺垫以后，我们可以开始看看，ACM中有点泛滥的STL了。

这年头，如果没有STL，做题体验会是什么样的呢？

• 排序你得背一个，至少快速排序要来一个（不然忍受C语言那个要指针的qsort()也行），二分查找不能偷懒，去重不能偷懒，
• 栈和队列要手写（BFS的时候，多写写循环队列吧）

• 刘汝佳的图论模板里存图的方法得重写了（因为没那么省力的vector<>了）

  上面都是小事，下面的就很头疼了

• 你需要掌握至少一个平衡树，还得会准确写出来（没有map和set，意味着，STL帮你搞定的，logn复杂度的动态插入、查询、删除的数据结构，没了……）于是，一种水题变得很不友好了……

扯了那么多，接下来让我们开始吧。

1、 STL的组成部分

说了这么半天，我都忘了仔细说明STL是什么了……
STL，英文全称Standard Template Library，标准模板库，是一组模板类和模板函数（所以要花时间讲模板……）。

这个模板库提供了：

• 用于存储信息的 容器
• 用于操作（查询、修改）容器内容的 算法
• 用于自己写的代码，和 STL 提供的算法去访问容器内信息的 迭代器

我们接下来慢慢介绍（只介绍ACM常用的）。

2、STL容器

首先，是顺序容器，这些容器的元素，都是按顺序，线性存储的：

• vector——你可以把它看做，动态数组。可以高效地，在最后插入数据，然后会一定保证数组内元素的地址连续性。
  
  • 但是请注意，正是因为内部是数组，所以：在开头/中间插入或者删除元素的时候，可是会老老实实地移动后面受影响的元素的（在开头/中间插入/删除元素的时间复杂度为O(n)）
• deque——说是与vector类似，但实际上，你可以考虑把deque看做块状数组。就是说，内存空间在内部不一定连续，分小块是连续的，然后块前后之间的地址再用数组维护。这样使得deque在处理从前面插入和删除的表现，相较vector来说，很好。但是在连续访问的时候，性能表现就会比vector差一些了。
• list——是一个双向链表。这个就不多说了，数据结构都学过。

然后是一类可快速查找的容器：

• 先介绍set。set可以在O(logn)的时间内，插入元素、查找元素、删除元素。一般set的实现是基于红黑树的，所以你的元素需要支持小于比较（实现过小于号）。还有就是，set里不允许元素重复。
• 再是map。map同样的，也是基于红黑树的实现，所以时间复杂度一样。不过和set不一样的是，map中的元素是key-value对（键值对）。就是说，你能用key找到对应的value。（当然了，和set一样，不允许重复的key；或者说，map中使用key确定元素）
  举例：

map<string ,int> score;
score["alice"]=95;
printf("Alice's score is %d\n",score["alice"]);

输出：Alice's score is 95
（顺带一提，有个东西叫KV数据库，面试时可能被问到，其实这里的KV就是指key-value，键值对）

• 然后我说，我就要存重复的元素，或者有重复的key，怎么办？没关系，我们有multiset和multimap
• 如果我觉得基于平衡树还不够快，而且我不需要元素有序，怎么办？ C++11 引入了新的，基于hash的unordered_set和unordered_map，当然还有相应的允许重复关键词的unordered_multiset和unordered_multimap

最后还有一类容器，封装了一些基本数据结构，包括：

• stack，栈
• queue，队列
• priority_queue，优先队列，基于堆的实现，默认大根堆

3、STL迭代器

我们现在把数据放进容器里，容器很好的把数据组织起来了。
然后我们怎么去访问这些数据？
vector和map重载了下标运算符，其他的呢？
这个时候，我们需要 迭代器（iterator） 。
迭代器（iterator）在用起来的时候，和指针非常类似，指向STL容器中的元素，用*来解引用，获取具体元素，可以++ / --来移动到下一个/上一个位置，可以用== !=来判断两个迭代器是否指向同一个位置。
但是，迭代器还是会有一些具体类型的，比如：

• 反向迭代器，++反而指向前一个（x-1）元素，--反而指向后一个（x+1）元素
• 双向迭代器，你只能做上面我们提到的那些事情了
• 随机访问迭代器，除了双向迭代器能做的，还能有随机跳转的能力（更像指针了），也就是说，对随机访问迭代器it，你可以it+=5来让it往后跳5个位置，可以it[5]获取it后的5个元素的值（相当于*(it+5)），还可以用> >= < <=比较相对位置。

具体的应用，和一些注意事项，我们将在之后结合STL容器进行讲解。

4、STL算法

最后我们来简单介绍一下STL算法了。
其实一些简单的算法，STL都帮我们实现了 —— 包括排序、二分，第k大，等等等等。
但是，有那么多不同容器，还有C语言数组，怎么通过一个实现来搞定一切呢？
统一通过迭代器来访问和操作数据就可以了！

还有，不少算法返回的是迭代器，如果你要知道下标的话，可得动手做一下减法。

我们将在下一篇来好好说说这些算法函数。

5、还有2个——string和bitset

最后再提2个类，string和bitset类。

string，顾名思义，字符串类。
我们不是有C语言的字符数组加上'\0'来当字符串挺好的吗，为什么要引入string类？
因为，当我们想把字符串放进set，以及map中当做key的情况下，我们肯定不是单单指针做比较（这样毫无意义），而是要内容做比较。
那么，要内容做比较，怎么办？
A）自己写个结构体/类，里面一个char数组，还要实现小于比较
B）为什么不用现成的实现呢？
这个现成的实现，就是string类了。

bitset，它是一个位向量/位示图的实现。
或者更直白点，这是一个每个元素只用一个bit（位）的bool[]，而且还可以玩各种位运算。

两者的具体应用，我们都会在之后讲解。