C++ 7
vector 底层原理和扩容过程
- 底层原理
● vector 是 C++ 标准库中的一个容器，可以看作是一个动态数组，它的大小可以根据元素的增加而增长。它通过在堆上分配一段连续的内存空间存放元素，支持时间复杂度为 O（1 ) 的随机访问。
● vector 底层维护了三个迭代器和两个变量，这三个迭代器分别指向对象的起始字节位置，最后一个元素的末尾字节和整个 vector 分配空间的末尾字节。两个变量分别是 size 和 capacity ，Size 表示当前存储元素的数量，capacity 表示当前分配空间的大小。当创建一个 vector 对象时，会分配一个初始化大小的空间存放元素，初始化空间可以通过构造函数的参数指定，缺省情况下为 0。当对 vector 容器进行增加和删除元素时，只需要调整末尾元素指针，而不需要移动整个内存块。 - 扩容机制
● 当添加元素的数量达到当前分配空间的大小时，vector 会申请一个更大的内存块，然后将元素从旧的内存块拷贝到新的内存块中，并释放旧的内存块。 扩容可能导致原有迭代器和指针失效，扩容完成后，容器返回指向新内存区域的迭代器或指针。
● vector 扩容的机制分为固定扩容和加倍扩容。
○ 固定扩容就是在每次扩容时在原容量的基础上增加固定容量。但是固定扩容可能会面临多次扩容(扩容的不够大)的情况，时间复杂度较高。
○ 加倍扩容就是在每次扩容时原容量翻倍，优点是使得正常情况下扩容的次数大大减少，时间复杂度低，缺点是空间利用率低。
push_back()和emplace_back()的区别
push_back()和emplace_back()都是C++标准库容器（如std::vector）中用来添加元素的方法，但它们在添加元素的方式上有所不同：
- push_back()：
○ 语法是container.push_back(value);，传入的是一个值或对象的副本/移动版本。
○ 它接受一个元素的副本或移动该元素，然后将其添加到容器的末尾。
○ 这个方法需要先构造一个元素的副本或移动构造一个临时对象，然后再将其添加到容器中。 - emplace_back()：
○ 语法是container.emplace_back(args…);，传入的是构造新元素所需的参数列表。
○ 它使用就地构造（emplace）的方式，直接在容器的内存空间中构造新元素。
○ 这个方法避免了元素的复制或移动操作，因为它直接在容器的末尾空间构造新元素。 - 性能：
○ emplace_back()通常比push_back()更高效，因为它避免了额外的复制或移动操作。
○ 当构造函数需要大量资源时，emplace_back()的优势更加明显。
map dequeu list的实现原理
- std:: map
● 基于红黑树：std::map 基于一种自平衡的二叉搜索树——红黑树实现。
● 有序容器：元素按照键的顺序自动排序，通常是按照小于（<）运算符定义的顺序。
● 唯一键：每个键都是唯一的，不允许有重复的键。
● 时间复杂度：提供对数时间复杂度 （O(log n)） 的查找、插入和删除操作。
● 迭代器：由于 std::map 是基于树的，迭代器在遍历时是有序的。 - std::list
● 基于双向链表：std::list 是一个双向链表，每个元素都持有指向前一个和后一个元素的指针。
● 无序容器：元素在容器中没有特定的顺序。
● 插入和删除：提供高效的插入和删除操作，特别是当需要在容器中间插入或删除元素时。
● 时间复杂度：提供线性时间复杂度 （O(n)） 的查找操作，但插入和删除可以在 O(1) 时间内完成，前提是已经拥有指向待插入或删除元素的迭代器。
● 迭代器：由于 std::list 是线性结构，迭代器在遍历时是顺序的，但不支持随机访问。 - std::deque
● 基于动态数组：std::deque 是一个基于动态数组的序列容器，可以高效地从两端添加或删除元素。
● 允许序列操作：可以快速地在队列的前端和后端添加或删除元素。
● 时间复杂度：提供常数时间复杂度 （O(1)） 的前端和后端插入和删除操作。中间插入或删除操作可能需要 O(n) 时间。
map && unordered_map的区别和实现机制
- map
● 基于红黑树：std::map 基于一种自平衡的二叉搜索树（通常是红黑树）实现，可以保持元素有序。
● 有序容器：元素按照键的顺序自动排序，可以通过键值进行有序遍历。
● 元素访问：提供对元素的快速查找、插入和删除操作，时间复杂度为 O(log n)。
● 唯一键：每个键都是唯一的，不允许有重复的键。
● 迭代器稳定性：由于基于树结构，迭代器在遍历时是稳定的，即使容器发生插入或删除操作，迭代器指向的元素也不会改变，除非该元素被删除。 - unordered_map
● 基于哈希表：std::unordered_map 基于哈希表实现，通过哈希函数将键分布到数组的槽位中。
● 无序容器：元素在容器中是无序的，不能按键的顺序进行遍历。
● 元素访问：理想情况下，提供平均时间复杂度为 O(1) 的快速查找、插入和删除操作。最坏情况下，性能可能下降到 O(n)。
● 允许重复键：实际上，std::unordered_map 不允许有重复的键，因为哈希表的设计不允许两个元素具有相同的哈希值。如果发生哈希冲突，会通过某种方式（如链表或开放寻址）解决。
● 迭代器稳定性：由于基于哈希表，迭代器的稳定性不如 std::map。在发生哈希表的重新哈希 （rehashing） 时，迭代器可能会失效。
● 遍历顺序与创建该容器时输入元素的顺序是不一定一致的，遍历是按照哈希表从前往后依次遍历的。 - 使用场景
● 当需要元素有序且对性能有较高要求时，应选择std::map。
● 当元素的顺序不重要，且需要快速访问元素时，应选择std::unordered_map。 - 实现机制
● std::map 的实现依赖于红黑树的旋转和颜色变换来保持树的平衡，确保操作的时间复杂度。
● std::unordered_map 的实现依赖于一个良好的哈希函数来最小化冲突，并通过解决冲突的机制（如链表或开放寻址）来存储具有相同哈希值的元素。