02 C++STL之容器

容器，就是一些模板类的集合，但和普通模板类不同的是，容器中封装的是组织数据的方法（也就是数据结构）。STL 提供有 3 类标准容器，分别是序列容器、排序容器和哈希容器，其中后两类容器有时也统称为关联容器

一、序列容器

STL标准库中的序列式容器包括 array、vector、deque、list 、forward_list 容器。
所谓STL序列式容器，其共同的特点是不会对存储的元素按照大小进行排序，元素排列的顺序取决于存储它们的顺序。即线性排序（类似普通数组的存储方式）来存储某一指定类型（例如int、double等）的数据。

1.数组容器

array<T,N>（数组容器）：定义在< array >头文件中， 表示可以存储N个T类型的元素，是C++本身提供的一种容器。此容器一旦建立，其长度就是固定不变的，也就是说无法增加或者删除元素，只能改变某个元素的值；

2.向量容器

vector（向量容器）：定义在< vector>头文件中，用来存储T类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或者删除元素效率最高（时间复杂度为O（1）常数阶），在其他位置插入或删除元素效率较差（时间复杂度O（n）线性阶，其中n为容器的元素个数）；

3.双端队列

deque（双端队列）：定义在< deque>头文件中，和vector非常相似，区别在于该容器可以很高效的在头部或者尾部插入或者删除元素，时间复杂度都是O(1)常数阶，但是在容器中某一位置处插入或者删除元素，时间复杂度O(n)线性阶；

4.链表容器

list（链表容器）：定义在< list >头文件中，是一个长度可变的，由T类型元素组成的序列，它是双向链表的形式组织元素，在这个序列的任何地方都可以高效的增加或者删除元素（时间复杂度都为O(1)），但访问容器的任意元素的速度比前三种容器都要慢，这是因为list必须从第一个元素或者最后一个元素开始遍历访问，直到到达自己想要的元素；

5.正向链表

forward_list（正向链表）：定义在< forward_list>头文件中，和list非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

注意：除此之外，stack和queue本质上也属于序列容器，只不过他们都是在deque容器的基础上改头换面而成，通常更习惯称他们为适配容器。

二、关联容器

排序容器

包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。
map/set为关联类容器，map中元素的结构为K-V（键值），set为K（键），它们均不允许两个元素有相同的键值，并且所有元素会根据元素的键值自动排序，STL底层使用了红黑树来构造map/set，红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。

1.set 集合容器

定义在 < set > 头文件中，容器各个元素键和值完全相同，且各个元素的值不能重复（保证了各元素键的唯一性）。它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高

2.multiset多重集合容器

定义在 < set > 头文件中，和 set 容器唯一的不同在于，multiset 容器中存储元素的值可以重复。

3.map映射容器

定义在 < map > 头文件中，map 容器存储的都是 pair 类型的键值对元素，更确切的说，该容器存储的都是 pair<const K, T> 类型（其中 K 和 T 分别表示键和值的数据类型）的键值对元素， map 容器存储的各个键值对，键的值既不能重复也不能被修改。map内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的。

4.multimap 多重映射容器

定义在 < map > 头文件中，multimap 容器具有和 map 相同的特性，即 multimap 容器也用于存储 pair<const K, T> 类型的键值对（其中 K 表示键的类型，T 表示值的类型），其中各个键值对的键的值不能做修改；并且，该容器也会自行根据键的大小对存储的所有键值对做排序操作。和 map 容器的区别在于multimap 容器中可以同时存储多（≥2）个键相同的键值对。

哈希容器

C++ 11 新加入 4 种关联式容器，分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射、 unordered_multimap 哈希多重映射。
与map/set功能类似，但内部所存的元素是无序的。STL底层使用了哈希表的结构来实现这两个容器。

1.unordered_set 哈希集合

定义在< unordered_set >头文件中，不再以键值对的形式存储数据，而是直接存储数据元素本身（当然也可以理解为，该容器存储的全部都是键 key 和值 value 相等的键值对，正因为它们相等，因此只存储 value 即可）。另外，该容器存储的元素不能重复，且容器内部存储的元素也是无序的。

2.unordered_multiset 哈希多重集合

定义在< unordered_set >头文件中，和 unordered_set 唯一的区别在于，该容器允许存储值相同的元素。

3.unordered_map 哈希映射

定义在< unordered_map >头文件中，存储键值对 <key, value> 类型的元素，其中各个键值对键的值不允许重复，且该容器中存储的键值对是无序的。

4.unordered_multimap 哈希多重映射

定义在< unordered_map >头文件中，和 unordered_map 唯一的区别在于，该容器允许存储多个键相同的键值对。