C++中的STL相关知识

STL容器

STL中的容器分为序列式容器和关联式容器，其中序列式容器有vector、list、stack、deque、queue、priority_queue，关联式容器包含map、multimap、set、multiset。

vector：是一个连续的动态线性空间，动态体现在它随着元素的添加，会自动扩充空间。vector的数据结构由三个迭代器构成，一个指向当前空间的头部，一个指向当前空间的尾部，一个指向当前最后一个元素尾部。当容量不足以添加新元素时，vector会重新申请一块两倍原容量的连续空间，将原有的数组以及新添的元素存入新的空间，释放原有空间。

注意：尽量避免频繁调用push_back()，如果必须，尽量使用emplace_back()。

list：是一个双向链表，存储的空间不连续，因此它的迭代器必须具备前移和后退的功能。相较于vector而言，list每插入或删除一个元素，就会对空间进行扩充或释放，并且原有的迭代器也不会消失。

deque：是一种双向开口的连续线性空间（伪连续），支持头尾两端的插入删除 *** 作。实际上，deque采用一块map作为主控，这里的map是连续空间，其中的每一个元素，都指向了一段连续的线性空间，因此deque实际上是多块连续空间的拼接空间。如果map容量不足，会选择一块更大的空间作为map。

stack：是一种先进后出的数据结构（FILO），只有一个端口，从栈顶添加元素，从栈顶移除元素。底层由deque构成，封闭了一个端口。

queue：是一种先进先出的数据结构（FIFO），拥有两个端口，从尾部添加元素，从头部移除元素。底层同样是由deque构成，封闭了尾部的出口和头部的入口。

priority_queue：底层是一个vector，利用了堆算法，每次取出数值最高的元素。

map：底层为红黑树，map中的元素以key-value（键值对）的形式表示。允许修改value，但不允许修改key，因为map是根据key的排序来保证它的有序性的。map是可以通过key作为下标 *** 作的，如果key不存在，会默认插入一个默认值和该key存入map中，因此map的下标需要慎用，能用find的情况下尽量用find。

set：底层为红黑树，关键字的简单集合。set中的迭代器是定义为const的，不允许修改元素值（可以绕开迭代器进行修改），set也是根据key的排序来保证它的有序性的。set不支持下标 *** 作。

另外，map和set的插入删除效率高于其他容器，因为set和map内的所有元素都是以节点的方式存储，无关内存移动，只需要调整指针的位置即可。

STL迭代器

Iterator（迭代器）用于提供一种能够顺序访问容器中元素而又不暴露内部表示的方法，类似于指针。严格来说，迭代器是一个类模板，封装了指针，提供了比指针更高级的行为，体现在能够根据不同类型的数据结构实现不同的++、- - *** 作。

迭代器分为输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机选取迭代器五种。

迭代器返回的是对象的引用而不是对象本身，所以要调用返回对象时，需要用*来解引用。

resize和reserve的区别

resize会改变当前容器内元素的数量，如果size变小，则会删除多余的元素；如果size变大，则会将容器的尺寸扩充，并将扩充部分添加初始化值。

reserve仅修改容器的容量，但不修改size的大小。若reserve的值大于原先的容量，那么会重新分配一块足以容纳新容量的空间，然后将原先的容器内的元素复制到新的空间中并释放原来的内存空间。相较于resize，它不会生成默认元素，仅仅起到一个扩容的作用。

如果有大量数据需要push_back()，那么应使用reserve提前设定容量大小。