C/C++工程师面试题（STL篇）

STL 中有哪些常见的容器

STL 中容器分为顺序容器、关联式容器、容器适配器三种类型，三种类型容器特性分别如下：

1. 顺序容器 容器并非排序的，元素的插入位置同元素的值无关，包含 vector、deque、list 

• vector：动态数组 元素在内存连续存放。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
• deque：双向队列 元素在内存连续存放。随机存取任何元素都能在常数时间完成（仅次于 vector ）。在两端增删元素具有较佳的性能（大部分情况下是常数时间）。
• list：双向链表 元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。

2. 关联式容器 元素是排序的；插入任何元素，都按相应的排序规则来确定其位置；在查找时具有非常好的性能；通常以平衡二叉树的方式实现，包含set、map。

• set  set中不允许相同元素
• map map 与 set 的不同在于 map 中存放的元素有且仅有两个成员变，一个名为 first，另一个名为 second，map 根据 first 值对元素从小到大排序，并可快速地根据 first 来检索元素。

3. 容器适配器 封装了一些基本的容器，使之具备了新的函数功能，包含 stack、queue。

• stack：栈 栈是项的有限序列，并满足序列中被删除、检索和修改的项只能是最进插入序列的项（栈顶的项），后进先出。
• queue：队列 插入只可以在尾部进行，删除、检索和修改只允许从头部进行，先进先出。

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

以下是其中一些常见容器的查找时间复杂度以及原因：

1. vector（向量）：查找时间复杂度为O(n)，因为vector是基于数组实现的，需要线性遍历整个数组来查找元素。

2. deque（双端队列）：在未排序状态下，查找时间复杂度为O(n)，类似于vector。但在有序状态下，可以利用二分查找，降低查找时间复杂度为O(log n)。

3. list（链表）：查找时间复杂度为O(n)，因为链表是一种线性结构，需要从头开始顺序查找元素。

4. set（集合）和multiset（多重集合）：查找时间复杂度为O(log n)，底层通常使用红黑树实现，具有较好的平衡性能。

5. map（映射）和multimap（多重映射）：查找时间复杂度为O(log n)，底层通常使用红黑树实现，按键进行自动排序。

6. stack（栈）和queue（队列）：查找时间复杂度为O(n)，因为它们是容器适配器，提供了先进先出（FIFO）或后进先出（LIFO）的接口，并不支持快速查找操作。

因此，对于不同的STL容器，其查找时间复杂度取决于底层数据结构的实现方式和算法设计。

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

vector 和 list 的区别：

1. 底层数据结构：

   • vector： 底层使用动态数组实现。
   • list： 底层使用双向链表实现。

2. 插入和删除操作：

   • vector： 插入和删除元素效率低。
   • list： 插入和删除元素效率高，因为只需要修改相邻节点的指针。

3. 随机访问：

   • vector： 支持随机访问，可以通过下标快速访问元素。
   • list： 不支持随机访问，只能通过迭代器顺序访问元素。

4. 空间和内存分配：

   • vector： vector 一次性分配好内存，不够时才进行扩容。
   • list： list 每次插入新节点都会进行内存申请。

适用场景：

• vector： 适用于连续存储，支持随机访问，而不在乎插入和删除的效率。

• list： 适用于不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问。

简述 vector 的实现原理

vector 是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问，由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。

当 vector 的大小和容量相等（size==capacity）时，如果再向其添加元素，那么 vector 就需要扩容。vector 容器扩容的过程需要经历以下 3 步：

1. 重新在堆上创建更大的动态数组，大小是原来的2倍；
2. 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
3. 最后将旧的内存空间释放。

扩容以后它的内存地址会发生改变

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

迭代器失效是指迭代器在遍历容器过程中，由于容器的结构发生改变而导致迭代器指向的元素不再有效。

以下是导致迭代器失效的常见情况：

1. 插入和删除操作： 当在容器中插入或删除元素时，可能会导致容器内存重新分配或元素位置的改变，这可能会使迭代器失效。
2. 清空容器： 清空容器会使容器内的所有元素被删除，这样迭代器指向的元素就会失效。
3. 使用引起重新分配的操作： 例如，在vector中使用push_back()添加元素时，如果超出了当前容量，可能会触发重新分配操作，从而使所有迭代器失效。
4. 排序操作： 如果在排序过程中，容器的元素被移动了位置，迭代器可能会失效。
5. 使用非常量迭代器遍历过程中修改了容器： 如果在使用非常量迭代器遍历容器的过程中，修改了容器的结构（例如插入或删除元素），会使迭代器失效。

deque 的实现原理

分段连续内存、中控器

deque 是由一段一段的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在 deque 的头端或者尾端。

deque 采取一块所谓的 map（不是 STL 的 map 容器）作为主控，这里所谓的 map 是一小块连续的内存空间，其中的每个元素（此处成为一个结点）都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是 deque的存储空间的主体。

红黑树的特性，为什么要有红黑树

红黑树是一种自平衡的二叉搜索树，它具有以下特性：

1. 节点颜色： 每个节点要么是红色，要么是黑色。
2. 根节点和叶子节点： 根节点、叶子节点（NIL节点，即空节点）是黑色的
3. 颜色相邻节点规则： 不能有两个相邻的红色节点。
4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 这保证了红黑树的关键性质：最长路径不超过最短路径的两倍。

2. 各操作的时间复杂度 插入: O(logN) 查看: O(logN) 删除: O(logN)

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

1. map 实现原理 map 内部实现了一个红黑树，红黑树有自动排序的功能，因此 map 内部所有元素都是有序的，红黑树的每一个节点都代表着 map 的一个元素。因此，对于 map 进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map 中的元素是按照二叉树存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值，使用中序遍历可将键值按照从小到大遍历出来。

2. 各操作的时间复杂度 插入: O(logN) 查看: O(logN) 删除: O(logN)

unordered_map 实现原理

unordered_map 容器和 map 容器一样，以键值对（pair类型）的形式存储数据，存储的各个键值对的键互不相同且不允许被修改。但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。底层采用哈希表实现无序容器时，会将所有数据存储到一整块连续的内存空间中，并且当数据存储位置发生冲突时，解决方法选用的是“链地址法”（又称“开链法”）.

map，unordered_map 的区别

1. map是基于红黑树实现的，unordered_map是基于哈希表实现的
2. map根据元素的键值会自动排序，而unordered_map是乱序的
3. map的增删改查时间复杂度是O（logN），而unordered_map的时间复杂度是最好情况是O(1)，最坏情况是O（N）。