嵌入式开发高频面试题——第四章 常见算法（下）

4.2.1 Vector和List的异同

Vector 和 List 都是C++ STL中的序列容器，但它们在底层实现和适用场景上有明显的区别。

• 底层实现：

  • Vector 是动态数组，它在内存中占据连续的空间，因此支持通过索引直接访问元素。
  • List 是双向链表，在内存中不要求元素是连续存储的，因此不支持直接索引访问，而是通过指针进行遍历。

• 访问速度：

  • Vector 的随机访问速度快，因为可以通过索引直接访问元素。
  • List 的随机访问速度慢，访问某个元素需要从头遍历链表直到找到目标元素。

• 插入和删除操作：

  • Vector 的插入和删除操作（尤其是在中间位置）效率较低，因为需要移动插入点之后的所有元素以保持内存连续。
  • List 的插入和删除操作效率高，只需调整相邻节点的指针即可，不需要移动其他元素。

• 内存使用：

  • Vector 使用连续的内存，因此可能需要频繁的内存分配和重新分配来扩展容量。
  • List 不要求内存连续，因此内存分配和释放的频率较低，但每个元素需要额外存储指向前后节点的指针。

4.2.2 Vector的内存增长与底层实现

Vector 的内存是通过动态数组实现的，内存增长机制如下：

• 内存增长策略：当 vector 容量不足时，它会按照一定的增长策略分配新的内存空间。通常会以当前容量的2倍（有些实现可能是1.5倍）来增长。

• 重新分配：当 vector 扩展容量时，它会在新的内存区域中分配两倍大小的空间，然后将旧数组中的元素移动到新的内存区域中。旧的内存空间随后会被释放。

• 底层实现：

  • vector 通过动态数组管理内存，因此它支持常量时间的随机访问。
  • 在插入或删除操作时，如果操作位置在 vector 的中间或开头，所有后续元素都需要移动以保持数组的连续性，这可能导致时间复杂度为O(n)的开销。

4.2.3 Vector和Deque的比较

Vector 和 Deque 都是序列容器，它们的主要区别在于内存管理和操作效率：

• 内存管理：

  • Vector 使用单块连续内存存储数据。
  • Deque 使用一系列固定大小的内存块来存储元素，不要求内存是连续的，因此在首尾添加和删除元素的效率更高。

• 操作效率：

  • Vector 在尾部添加或删除元素的时间复杂度为O(1)，但在头部添加或删除元素的时间复杂度为O(n)。
  • Deque 支持在头尾两端的快速插入和删除操作，时间复杂度为O(1)。

• 适用场景：

  • 使用 vector 的场景适合频繁的随机访问和尾部操作。
  • 使用 deque 的场景适合需要在两端进行插入或删除操作的场景。

4.2.4 STL里有sort函数，为什么list还要定义sort？

STL 中的 sort 函数是针对随机访问迭代器设计的，这意味着它要求底层容器（如 vector、deque）支持随机访问（通过索引访问元素）。但是 list 是一个双向链表，只支持双向迭代器，因此无法直接使用 sort。

list 中定义的 sort 函数使用的是基于合并排序的算法，因为合并排序可以在链表中高效实现，且稳定。链表不适合随机访问，所以快速排序等算法在链表上不适用。

4.2.5 STL底层数据结构实现

STL 底层数据结构基于泛型编程，使用模板来实现一系列常用的数据结构和算法。STL 中常用的容器及其底层实现：

• Vector：基于动态数组实现，支持随机访问。
• List：基于双向链表实现，支持高效的插入和删除操作。
• Deque：基于分段连续数组实现，适用于两端快速操作。
• Map/Set：基于红黑树（平衡二叉搜索树）实现，支持快速的查找、插入和删除。
• Unordered Map/Set：基于哈希表实现，支持均摊时间复杂度为O(1)的查找、插入和删除。

4.2.6 利用迭代器删除元素会发生什么？

在STL容器中使用迭代器删除元素时，可能会发生以下情况：

• Vector/Deque：删除一个元素后，所有指向删除元素之后的迭代器都会失效（因为元素被移动，地址发生变化）。解决方案是使用 erase 函数，该函数会返回删除元素之后的有效迭代器。

• List：删除一个元素后，只有指向被删除元素的迭代器会失效，其他迭代器仍然有效。可以安全地使用 erase 函数。

• Map/Set：删除元素后，只有指向被删除元素的迭代器失效，其他迭代器不会失效。

4.2.7 Map的实现与查找效率

Map 是通过红黑树（平衡二叉搜索树）实现的，红黑树是一种自平衡二叉搜索树。它的查找、插入和删除操作的时间复杂度为O(log n)。

红黑树的特点：

• 每个节点都是红色或黑色。
• 根节点是黑色。
• 叶节点（NIL节点）是黑色。
• 红色节点的子节点必须是黑色（不能有两个红色节点相连）。
• 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

4.2.8 几种模板插入的时间复杂度

• Vector：在末尾插入元素的时间复杂度为O(1)，在中间插入元素的时间复杂度为O(n)。
• List：在任意位置插入元素的时间复杂度为O(1)，前提是已知插入位置的迭代器。
• Deque：在两端插入元素的时间复杂度为O(1)，在中间插入元素的时间复杂度为O(n)。
• Map/Set：插入元素的时间复杂度为O(log n)（红黑树的性质）。

这些时间复杂度使得不同的STL容器在不同的场景下各有优劣，因此选择合适的容器和算法是关键。