1. STL 中有哪些常见的容器

顺序容器容器并非排序的，元素的插入位置同元素的值无关，包含 vector、deque、list；
1. vector：动态数组元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能；
2. deque：双向队列元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于 vector ）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）；
3. list：双向链表元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取；
关联式容器元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现，包含set、multiset、map、multimap；
1. set/multiset set中不允许相同元素，multiset 中允许存在相同元素；
2. map/multimap map 与 set 的不同在于 map 中存放的元素有且仅有两个成员变，一个名为 first，另一个名为 second，map 根据 first 值对元素从小到大排序，并可快速地根据 first 来检索元素。map 和multimap 的不同在于是否允许相同 first 值的元素
容器适配器封装了一些基本的容器，使之具备了新的函数功能，包含 stack、queue、priority_queue；
1. stack：栈栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的项），后进先出
2. queue：队列插入只可以在尾部进行，删除、检索和修改只允许从头部进行，先进先出；
3. priority_queue：优先级队列内部维持某种有序，然后确保优先级最高的元素总是位于头部，最高优先级元素总是第一个出列。

2. STL 容器用过哪些，查找的时间复杂度是多少，为什么？

STL 中常用的容器有 vector、deque、list、map、set、multimap、multiset、unordered_map、unordered_set 等；
容器底层实现方式及时间复杂度分别如下：
1. vector 采用一维数组实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N) 查看: O(1) 删除: O(N) ；
2. deque 采用双向队列实现，元素在内存连续存放，不同操作的时间复杂度为：插入: O(N) 查看: O(1) 删除: O(N) ；
3. list 采用双向链表实现，元素存放在堆中，不同操作的时间复杂度为：插入: O(1) 查看: O(N) 删除: O(1) ；
4. map、set、multimap、multiset 上述四种容器采用红黑树实现，红黑树是平衡二叉树的一种。不同操作的时间复杂度近似为: 插入: O(logN) 查看: O(logN) 删除: O(logN) ；
5. unordered_map、unordered_set、unordered_multimap、 unordered_multiset 上述四种容器采用哈希表实现，不同操作的时间复杂度为：插入: O(1)，最坏情况O(N) 查看: O(1)，最坏情况O(N) 删除: O(1)，最坏情况O(N) 注意：容器的时间复杂度取决于其底层实现方式。

3. vector 的扩容机制，扩容以后，它的内存地址会变化吗？

当 vector 的大小和容量相等（size==capacity）也就是满载时，如果再向其添加元素，那么 vector 就需要扩容。

vector 容器扩容的过程需要经历以下 3 步：

完全弃用现有的内存空间，重新申请更大的内存空间；
将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
最后将旧的内存空间释放。因为 vector 扩容需要申请新的空间，所以扩容以后它的内存地址会发生改变。vector 扩容是非常耗时的，为了降低再次分配内存空间时的成本，每次扩容时 vector 都会申请比用户需求量更多的内存空间（这也就是 vector 容量的由来，即 capacity>=size），以便后期使用。

4. vector 和 list 的区别，分别适用于什么场景？

区别：
1. vector 底层实现是数组，list 是双向链表；
2. vector 支持随机访问，list 不支持；
3. vector 是顺序内存，list 不是；
4. vector 在中间节点进行插入删除会导致内存拷贝，list 不会；
5. vector 一次性分配好内存，不够时才进行扩容，list 每次插入新节点都会进行内存申请；
6. vector 随机访问性能好，插入删除性能差，list 随机访问性能差，插入删除性能好；
适用场景：
1. vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用 vector；
2. list 拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list；

5. deque 的实现原理

deque 是由一段一段的定量的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在 deque 的头端或者尾端。deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然 deque 是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。
deque 采取一块所谓的 map（不是 STL 的 map 容器）作为主控，这里所谓的 map 是一小块连续的内存空间，其中每一个元素（此处成为一个结点）都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是 deque的存储空间的主体。

6. set 的实现原理

set 底层使用红黑树实现，一种高效的平衡检索二叉树。

set 容器中每一个元素就是二叉树的每一个节点，对于 set 容器的插入删除操作，效率都比较高，原因是二叉树的删除插入元素并不需要进行内存拷贝和内存移动，只是改变了指针的指向；
对 set 进行插入删除操作都不会引起迭代器的失效，因为迭代器相当于一个指针指向每一个二叉树的节点，对 set的插入删除并不会改变原有内存中节点的改变；
set 中的元素都是唯一的，而且默认情况下会对元素进行升序排列；
不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，再插入新元素。不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。

7. map 实现原理，各操作的时间复杂度是多少

map 实现原理 map 内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而 AV L是严格平衡二叉搜索树），红黑树有自动排序的功能，因此 map 内部所有元素都是有序的，红黑树的每一个节点都代表着 map 的一个元素。因此，对于 map 进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map 中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值，使用中序遍历可将键值按照从小到大遍历出来；
各操作的时间复杂度插入: O(logN) 查看: O(logN) 删除: O(logN)；

8. map，unordered_map 的区别

导入的头文件 map：#include <map><span> </span>unordered_map：#include <unordered_map>；
原理及特点：
1. map：内部实现了一个红黑树，该结构具有自动排序的功能，因此 map 内部的所有元素都是有序的，红黑树的每一个节点都代表着 map 的一个元素，因此，对于 map 进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了 map 的效率。
2. unordered_map：内部实现了一个哈希表，因此其元素的排列顺序是杂乱的，无序的；

9. 迭代器失效原因，有哪些情况

STL 中某些容器调用了某些成员方法后会导致迭代器失效。

例如 vector 容器，如果调用 reserve() 来增加容器容量，之前创建好的任何迭代器（例如开始迭代器和结束迭代器）都可能会失效，这是因为，为了增加容器的容量，vector 容器的元素可能已经被复制或移到了新的内存地址。

序列式容器迭代器失效对于序列式容器，例如 vector、deque，由于序列式容器是组合式容器，当当前元素的迭代器被删除后，其后的所有元素的迭代器都会失效，这是因为 vector、deque都是连续存储的一段空间，所以当对其进行 erase 操作时，其后的每一个元素都会向前移一个位置。解决：erase 返回下一个有效的迭代器；
关联式容器迭代器失效对于关联容器，例如如 map、 set，删除当前的迭代器，仅仅会使当前的迭代器失效，只要在 erase 时，递增当前迭代器即可。这是因为 map 之类的容器，使用了红黑树来实现，插入、删除一个节点不会对其他点造成影响。erase 迭代器只是被删元素的迭代器失效，但是返回值为 void，所以要采用 erase(iter++) 自增方式删除迭代器；

自由意志

STL面试题（1）