STL六大组件: 容器、迭代器、算法

容器就是数据结构，用来将数据元素按照一定的规则进行排列，不同的容器拥有不同的排列规则，不同的排列规则可以达到不同的数据操作特点。 算法就是提供对容器数据元素的一些操作。 迭代器就是容器和算法之间的桥梁，粘合剂。

1 string

问：string存取字符[]和at的异同? 答：1 相同,[]和at都可以返回第n个字符 2 不同，at访问越界会抛出异常，[]越界会直接程序会挂掉。

2 vector

长度动态改变的动态数组，连续的内存空间，随机存取效率高。 vector是单口容器，在队尾插入和删除元素效率高，在指定位置插入会导致数据元素移动，效率低。 问：vector如何实现动态增长? 答: 当vector空间满的时候，再当插入新元素的时候，vector会重新申请一块更大的内存空间，将原空间数据拷贝到新的内存空间，然后释放旧的内存空间，再将新元素插入到新空间中，以此可以看出vector的空间动态增长效率较低。

3 deque

deque是双向开口的连续性空间，头尾辆段都可以做元素的插入和删除操作 deque和vector的最大差异？ 一在于deque允许常数时间内对头端进行元素插入和删除操作。 二在于deque没有容量的概念，因为它是动态的以分段的连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样“因旧空间不足而重新分配一块更大的空间，然后再复制元素，释放空间”这样的操作不会发生在deque身上，也因此deque没有必要提供所谓的空间保留功能。

4 queue

先进先出的数据结构，不具有遍历行为。 必须从一个口数据元素入队，另一个口数据元素出队。

5 stack

先进后出的数据结构，stack不具有遍历行为，没有迭代器。 只有一个出入口

6 list

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 问：链表和数组有什么区别？ 答：1) 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。 2) 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据元素。（数组中插入、删除数据项时，需要移动其它数据项）

7 set/multiset

数据元素会自动进行排序。set是以RB-tree(红黑树，平衡二叉树的一种)为底层机制，查找效率特别高。 二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。二叉搜索树的放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在二叉搜索树中找到最大元素和最小元素是非常简单的事情。

8 map/multimap

当我们给容器中插入元素的时候，容器内部实施了拷贝动作，将我们要插入的元素再另行拷贝一份放入到容器中，而不是将原数据元素直接放进容器中，也就是说我们提供的元素必须能够被拷贝。 STL容器都是值引用，在向容器中加入元素的时候，实际上是对元数据进行了一份拷贝，将拷贝的数据放入到容器中

顺序容器

vector deque list forward_list array string

容器适配器

queue stack