STL备忘录——容器

STL作为Cpp标准库的一部分，是Cpp数据处理的一大利器。在Cpp的开发中，如何合理地使用STL能够很好地体现开发人员对Cpp基础。

STL的内容很多，在此总结一下各种容器的用法和使用场景，作为备忘。对容器的实现原理不作深入探讨，暂时会用即可。

STL的容器很多，首先要掌握分类才能方便记忆。

容器的分类

STL对定义的通用容器分三类：顺序性容器、关联式容器和容器适配器。

顺序性容器包括：vector、deque、list、forward_list、array以及string。

今天介绍常用的array、vector、list、deque

顺序性容器

array

一个大小不可变的数组，是最轻量的顺序性容器。但其不能在尾部追加，只支持随机访问和改写。和vector相比，它的性能优势并不明显，且API限制太大，因此使用场景较少。

vector

一个可变大小的数组，元素被保存在一段连续空间中。因为是顺序结构，具有读快写慢的性质。允许在尾部插入，但由于其线性储存的性质，需要进行扩容，采用翻倍扩容的方式。

API参考

list

双向链表，读慢写快。因链表结构，不需要进行翻倍式扩容。但只能支持正向或反向遍历，需要快速访问其中某元素，则性能较差。

API参考

deque

deque是由一段段连续储存空间组成的链式结构。因其特殊的结构，在写入方面，也非常有趣。在两端写入很快（链式储存的性质），在中间写入则较慢（线性储存的性质）。
支持随机访问，但性能不及vector。

API参考

关联式容器

set

set集合容器实现了红黑树（Red-Black Tree）的平衡二叉检索树的的数据结构，在插入元素时，它会自动调整二叉树的排列，把该元素放到适当的位置，以确保每个子树根节点的键值大于左子树所有节点的键值，而小于右子树所有节点的键值；另外，还得确保根节点的左子树的高度与有字数的高度相等，这样，二叉树的高度最小，从而检索速度最快。要注意的是，它不会重复插入相同键值的元素，而采取忽略处理。

API参考

map

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有序的好处。

API参考

容器适配器

所谓容器适配器，只是提供了一个符合特定数据结构的接口。它可以由一种或多种上面介绍的容器实现。

stack

stack可以用任务顺序性容器实现。

 stack<int> intDequeStack;  
 stack<int,vector<int>> intVectorStack;  
 stack<int,list<int>> intListStack;  

priority_queue

priority_queue类，能够按照有序的方式在底层数据结构中执行插入操作，也能从底层数据结构的前面执行删除操作。

priority_queue能够用STL的序列容器vector和deque实现。默认情况下使用vector作为底层容器的。当元素添加到priority_queue时，它们按优先级顺序插入。

这样，具有最高优先级的元素，就是从priority_queue中首先被删除的元素。通常这是利用堆排序来实现的。

堆排序总是将最大值（即优先级最高的元素）放在数据结构的前面。这种数据结构称为（heap）

默认情况下，元素的比较是通过比较器函数对象less<T>执行的。

priority_queue具有几个常见的操作：

1.根据priority_queue的优先级顺序在适当位置插入push函数（通过调用底层容器的push_back，然后使用堆排序为元素重新排序）

2.删除priority_queue的最高优先级元素的pop（删除堆顶元素之后通过调用底层容器的pop_back实现）

3.获取priority_queue的顶部元素引用的top函数（通过调用底层容器的front函数实现）

4.判断priority_queue是否为空的empty函数（通过调用底层容器的empty函数实现）

5.获取priority_queue元素数量的size函数（通过调用底层容器的size函数实现）

为了获取最佳性能，使用vector作为priority_queue的底层容器。