数据结构及存储结构
| 数据结构 | 底层存储 | 复杂度 |
|---|---|---|
| map | 红黑树 | O(logn) |
| unordered_map | 散列表 | O(1) |
| list | 双向链表 | O(n) |
| priority_queue | 堆（数组实现） | O(logn) |
算法
排序
sort
- 底层实现：C++ 标准库中的
sort()函数通常使用一种名为 “introsort” 的混合排序算法来实现。这是一种综合了快速排序、堆排序和插入排序的排序算法。 - 工作原理：
sort()函数首先会尝试使用快速排序算法进行排序，通过选择一个枢轴元素来将序列分割成两个部分，并递归地对子序列进行排序。当递归深度达到一定阈值时，为了避免最坏情况下的时间复杂度，算法会转而采用堆排序算法。如果序列较小，则会使用插入排序算法进行排序。 - 复杂度：平均时间复杂度为 O(n log n)，其中 n 是待排序序列的大小。空间复杂度为 O(log n)。
quick_sort
-
底层实现：
quick_sort()函数是基于快速排序算法的一种实现。 -
工作原理：快速排序算法通过选取一个枢轴元素将序列分割为两个子序列，较小的元素放在枢轴的左侧，较大的元素放在右侧。然后对这两个子序列递归地应用相同的操作，直到子序列的大小为 1 或 0，此时递归结束。
-
复杂度：平均时间复杂度为 O(n log n)，其中 n 是待排序序列的大小。最坏情况下的时间复杂度为 O(n^2)。空间复杂度为 O(log n)。
常见问题
STL 是什么
STL（Standard Template Library，标准模板库）是C++编程语言的一个标准库，主要包含了许多常用的数据结构和算法，并为其提供了一系列的通用接口，方便开发者进行快速开发、高效地复用代码。
STL包括容器、迭代器、算法以及仿函数等组件，它们的设计思想是基于泛型编程和模板元编程。STL允许用户通过重载运算符或定义函数对象对其现有的模板进行扩展，支持自定义类型和算法，从而大大增强了程序的可扩展性和可维护性。
STL标准库中包含了很多容器（如vector、list、map、set等）、算法（如sort、search、find等）和迭代器（如输入输出流迭代器、反向迭代器等），这些组件可以帮助程序员实现许多常见的数据结构和算法，例如线性表、树、图、排序、查找等，从而提高了程序的开发效率和代码质量。
总之，STL是一种非常强大和实用的C++库，广泛应用于软件开发、算法竞赛等领域，是C++程序员必须掌握的一个重要工具。
STL中包含哪些容器？它们之间有什么区别？
STL（Standard Template Library，标准模板库）中包含了多种容器，主要分为以下三类：
顺序容器
顺序容器是指元素按照一定的顺序存储和访问的容器。常见的顺序容器有vector、list、deque、array等。其中，vector和deque都是基于数组实现的可变长度容器，而list则是基于双向链表实现的容器。
关联容器
关联容器是指元素按照一定规则排序后存储和访问的容器。常见的关联容器有set、multiset、map、multimap等。其中，set和map是基于平衡二叉树实现的，而multiset和multimap允许重复元素。
无序容器
无序容器是指元素不按照任何特定顺序存储和访问的容器。常见的无序容器有unordered_set、unordered_multiset、unordered_map、unordered_multimap等。这些容器通常使用哈希表来实现，具有O(1)的插入、查找和删除操作。
这些容器之间的区别主要包括以下几个方面：
- 存储方式不同：顺序容器按照逻辑顺序存储元素，而关联容器和无序容器则根据元素的键值进行存储。
- 插入和查找的时间复杂度不同：顺序容器在尾部插入元素和访问尾元素时速度较快，而关联容器和无序容器则可以通过键值快速查找元素。
- 内存分配方式不同：顺序容器通常使用连续内存块来存储元素，而关联容器和无序容器则需要动态分配内存。
- 支持的操作不同：不同的容器支持的操作有所区别。例如，只有顺序容器和关联容器支持排序操作，而只有无序容器支持哈希相关操作。
在选择容器时，需要根据具体的应用场景和需要进行权衡和选择。例如，如果需要对元素进行频繁的插入和删除操作，可以选择使用list或deque；如果需要高效地进行查找操作，则可以选择使用set、map等关联容器；如果需要快速进行元素的插入、查找和删除操作，则可以选择使用unordered_set、unordered_map等无序容器。
STL中包含哪些算法？它们的时间复杂度分别是多少？
STL（Standard Template Library，标准模板库）中包含了大量的算法，这些算法主要分为以下几类：
- 查找和排序算法：如find、find_if、sort、stable_sort等。
- 变动操作算法：如copy、replace、remove、unique等。
- 数值算法：如accumulate、inner_product、partial_sum、adjacent_difference等。
- 集合操作算法：如set_union、set_intersection、set_difference、merge等。
- 堆算法：如make_heap、pop_heap、push_heap等。
- 其他算法：如count、for_each、transform、reverse等。
这些算法的时间复杂度各不相同，具体如下：
- 查找和排序算法：通常具有O(nlogn)或O(n)的时间复杂度。
- 变动操作算法：通常具有O(n)的时间复杂度。
- 数值算法：通常具有O(n)的时间复杂度。
- 集合操作算法：通常具有O(n)的时间复杂度。
- 堆算法：通常具有O(logn)的时间复杂度。
STL中的迭代器有哪些种类？它们之间有什么区别？
STL（Standard Template Library）中的迭代器是一种用于遍历容器中各个元素的对象。根据其所支持的操作和能力，可以将迭代器分为以下五类：
- 输入迭代器（Input Iterator）：支持读取元素的值，但不允许修改或重复读取元素。例如
std::istream_iterator。 - 输出迭代器（Output Iterator）：支持写入元素的值，但不允许读取或重复写入元素。例如
std::ostream_iterator。 - 前向迭代器（Forward Iterator）：支持在容器中沿着一个方向遍历每个元素，并且能够多次读取或写入同一元素。例如
std::forward_list::iterator。 - 双向迭代器（Bidirectional Iterator）：支持前向迭代器的所有操作，同时还支持反向遍历容器并进行修改操作。例如
std::list::iterator。 - 随机访问迭代器（Random Access Iterator）：支持双向迭代器的所有操作，同时还支持随机访问容器中任意元素的操作，并支持指针算术、取下标等高级操作。例如
std::vector::iterator。
这些迭代器之间的区别在于它们所支持的操作和能力不同。输入迭代器和输出迭代器都只能向前遍历容器中的元素，且不能进行修改、重复访问等操作。前向迭代器可以在容器中向前遍历每个元素，并且能够多次读取或写入同一元素。双向迭代器可以支持反向遍历容器并进行修改操作，而随机访问迭代器则可以支持高级的指针算术、下标操作等。
使用迭代器可以方便地对STL中的容器进行遍历和操作，从而简化代码的编写和维护。在实际应用中，我们可以根据需要选择合适的迭代器类型来完成相应的任务。
什么是STL中的迭代器失效？如何避免迭代器失效？
STL中的迭代器失效是指，当容器发生插入、删除或移动元素等操作时，之前获取的某些迭代器可能会失效，导致使用这些迭代器访问容器时出现未定义行为。
为了避免迭代器失效，可以采取以下措施：
- 避免在循环中对容器进行插入、删除或移动操作，因为这可能会导致循环内的迭代器失效。
- 使用emplace()函数而不是insert()函数来插入新元素。emplace()函数可以直接在容器中构造新元素，避免复制或移动现有元素，从而减少迭代器失效的可能性。
- 对于需要对容器中的元素进行操作的情况，可以使用智能指针（如shared_ptr）来管理容器中的元素，这样即使容器发生变化，指向元素的智能指针仍然有效。
- 在进行容器操作时，尽量使用下标或者迭代器来访问容器中的元素，而不是使用指针。因为指针可能会受到容器重新分配内存的影响，从而失效。
STL中的容器和算法都是采用什么方式实现的？
STL中的容器和算法都是采用模板类和泛型编程的方式实现的。
容器是通过模板类来实现的，每个容器都有自己的特定类型、迭代器和操作方法。例如，vector容器是使用动态数组来实现的，list容器是使用双向链表来实现的，map容器是使用红黑树来实现的等等。
算法是通过函数模板来实现的，它们可以接受不同类型的容器和迭代器作为参数，并提供了一系列通用的操作方法。例如，sort()函数可以对任何支持随机访问迭代器的容器进行排序，find()函数可以在任何支持正向迭代器的容器中查找指定元素等等。
这种基于模板类和泛型编程的设计模式，使得STL中的容器和算法具有高度的灵活性和可重用性，可以适应各种数据结构和算法的实现需求。同时还能够提高代码的可读性和可维护性，减少了重复代码的写作量，提高了开发效率。
