60道C++STL高频题整理（附答案背诵版）

1.请解释vector容器和它的特点。

在C++中，vector是标准模板库（STL）的一部分，它是一个动态数组。与普通数组相比，它的大小可以在运行时动态改变。下面是vector的一些主要特点和应用场景：

动态大小：与传统的数组不同，vector可以根据需要动态地扩展或缩减大小。这意味着你不需要事先知道数据的数量。
随机访问：就像数组一样，vector支持随机访问，这意味着你可以通过索引直接访问任何元素，访问时间是常数时间复杂度（O(1)）。
内存管理：vector在内部管理其存储的内存。当元素被添加到vector中，并且当前分配的内存不足以容纳它们时，它会自动重新分配更多的内存。
灵活性：你可以在vector的末尾添加或删除元素，而且效率很高。但在中间或开始位置插入或删除元素可能会比较慢，因为这可能需要移动现有的元素。

应用场景

动态数据集合：当你需要一个可以根据数据量动态调整大小的数组时，vector是一个很好的选择。例如，处理用户输入的数据集，其中输入数量事先未知。
需要快速访问的数据：由于vector支持随机访问，它非常适合于需要频繁读取元素的情况，比如查找或排序算法中。
性能敏感的应用：由于其元素紧密排列在连续的内存块中，vector通常提供高效的内存访问性能，适合用于性能敏感的应用。

总之，vector是一个非常灵活且强大的容器，适合用于多种不同的编程场景。在实际应用中，选择正确的数据结构往往是优化程序性能的关键。

2.vector如何保证元素的连续存储？

vector 在 C++ STL 中保证元素连续存储的方式主要体现在它的内部实现上。具体来说，vector 使用动态分配的数组来存储其元素。这意味着在内存中，vector 的所有元素都被放置在一个连续的内存块中。以下是这种实现的几个关键点：

动态数组：vector 的底层是一个动态数组。当创建一个 vector 时，它会在堆上分配一块连续的内存来存储元素。
自动扩容：当向 vector 添加元素，而当前的内存空间不足以容纳更多元素时，vector 会自动进行扩容。这个过程包括分配一个更大的内存块、将现有元素复制到新的内存块中，并释放旧的内存块。
内存管理策略：vector 通常使用“倍增”策略来扩容，即每次扩容时将容量增加到当前的两倍（或者按照特定的增长因子增加）。这样做可以平衡内存使用和性能，尽管可能会导致一定程度的内存浪费。
连续性的好处：由于所有元素都存储在连续的内存块中，vector 能够提供快速的随机访问。这对于需要经常访问元素的场景特别有用，例如在循环或算法中。

应用场景示例

图形处理：在处理图像或图形时，像素或顶点数据可以存储在 vector 中，以利用其快速随机访问的优势。
科学计算：在科学计算中，大量数值数据（如矩阵的元素）通常需要连续存储，以便高效处理。

连续存储的设计使得 vector 在很多情况下都是一个高效且灵活的选择。

3.当vector空间不足时，如何扩容？

当 vector 的空间不足以容纳更多元素时，它会进行扩容操作以提供更多的存储空间。这个过程涉及以下步骤：

确定新容量：首先，vector 需要确定新的容量。这通常是当前容量的两倍（或其他预定义的增长因子）。这种倍增策略是为了在扩容次数和每次扩容的成本之间找到平衡。
分配新内存：接着，vector 会在堆上分配一块新的、更大的连续内存空间来存放元素。
复制元素：将现有的所有元素从旧内存区域复制到新分配的内存区域。这一步通常使用拷贝构造函数或移动构造函数（如果元素类型支持移动语义）。
释放旧内存：一旦所有元素都被成功复制到新内存区域，vector 会释放原来的内存空间。
更新内部指针：最后，vector 更新其内部数据结构，如指向元素数组的指针、大小和容量。

扩容的影响和考虑因素

性能成本：扩容是一个相对昂贵的操作，因为它涉及到内存分配和元素的复制或移动。这就是为什么合理选择初始容量或使用 reserve() 方法预留足够空间可以提高性能。
迭代器失效：扩容会导致之前所有指向 vector 元素的迭代器、指针和引用失效，因为元素已经被移动到了新的内存位置。

应用场景示例

数据收集：在不断收集数据的应用场景中（如日志记录或实时数据采集），vector 可以动态扩容以应对数据量的不断增长。
动态数组功能：在需要动态数组功能的场景中，如游戏开发中的动态实体列表，vector 提供了自动扩容的便利。

总的来说，vector 的自动扩容机制使其成为一个非常灵活和强大的容器，适用于多种需要动态数组功能的场景。

4.vector的push_back和emplace_back有什么区别？

vector 的 push_back 和 emplace_back 函数都是用来在 vector 的末尾添加新元素的，但它们之间有几个关键的区别：

构造方式：
- push_back 函数会复制或移动已经构造好的对象到 vector 的末尾。
- emplace_back 函数则是直接在 vector 的末尾构造新元素，它接受的是构造函数的参数，而不是对象本身。
性能：
- 使用 push_back 时，如果传入的是一个临时对象，它首先会被构造，然后再被复制或移动到 vector 中（C++11起，会尝试使用移动构造减少开销）。
- emplace_back 则可以避免这些额外的复制或移动操作，因为它直接在容器的内存中构造对象，从而可能提供更好的性能。
例子：
- 使用 push_back 添加一个复杂对象时：myVector.push_back(MyClass(a, b, c)); 这里 a, b, c 是传递给 MyClass 构造函数的参数，首先在外部构造一个临时的 MyClass 对象，然后将其添加到 vector。
- 使用 emplace_back 相同的操作：myVector.emplace_back(a, b, c); 这里直接将参数 a, b, c 传递给 emplace_back，在 vector 的内存空间中直接构造对象，无需临时对象。

应用场景

优化性能：如果你正在添加的对象是通过多个参数构造的，而这些参数是用来直接构造对象的，使用 emplace_back 可以减少不必要的临时对象创建和复制/移动操作，从而优化性能。
复杂对象：对于构造函数参数多，或者构造成本高的对象，emplace_back 更能显示其性能优势。

在实践中，如果要添加的元素是简单的或已存在的对象，push_back 和 emplace_back 的性能差异可能不明显。然而，对于复杂的对象或者需要构造的场景，emplace_back 往往是更好的选择。

5.使用vector需要注意哪些问题？

使用 C++ STL 中的 vector 时，需要注意以下几个问题：

初始化和默认构造：不同于内置数组，vector 默认构造时是空的。确保在使用之前正确初始化 vector，或在需要时使用 resize() 或 reserve() 方法来分配适当的大小。
性能考虑：
- 扩容开销：vector 的自动扩容机制虽然方便，但可能导致性能损耗。如果你预先知道大致的大小需求，使用 reserve() 预留空间可以提高效率。
- 尾部添加/删除：在 vector 的末尾添加或删除元素是高效的（常数时间复杂度），但在中间或开始位置插入或删除元素会导致后续所有元素的移动，这可能是成本较高的操作。
迭代器失效：在对 vector 进行添加、删除或扩容操作后，所有指向 vector 元素的迭代器、指针和引用可能都会失效。在进行这些操作后，确保不再使用旧的迭代器。
内存管理：虽然 vector 自动管理内存，但仍需注意内存使用。例如，即使使用 clear() 清空了 vector，其容量（占用的内存大小）不会自动减小。如果需要缩减内存占用，可以使用技巧性的方法（如交换一个空的 vector）来减小占用。
对象复制：向 vector 中添加对象时，会进行对象的复制或移动。如果对象较大或复制成本高，这可能导致性能问题。考虑使用移动语义或智能指针来优化性能。
异常安全性：在元素构造或复制过程中可能抛出异常。确保你的代码能够正确地处理这些异常，避免内存泄漏或数据不一致。
选择正确的容器：虽然 vector 是非常通用的容器，但并不总是最佳选择。根据具体的应用场景选择适当的容器（如 list、deque 等）可能会更有效。

应用场景注意事项

动态数据处理：在处理动态增长的数据集时，考虑预先使用 reserve() 分配足够空间，避免频繁的内存重新分配。
大型对象集合：处理大型对象时，考虑使用包含指针或智能指针的 vector，以减少复制成本。
频繁插入/删除操作：如果需要频繁在中间位置插入或删除元素，可能需要考虑其他类型的容器，如 list 或 deque。

综合考虑这些因素，可以在使用 vector 时做出更有效的决策，提高程序的性能和稳定性。

6.Vector有哪些应用场景？

vector 在 C++ 中是一种非常灵活和强大的容器，适用于多种不同的应用场景。以下是一些常见的应用场景：

动态数据集合：当你不确定数据集的大小，或者数据集的大小会随时间变化时，vector 是理想的选择。例如，在处理用户输入或读取文件数据时，vector 可以根据需要动态地增长。
高效的随机访问：如果你需要快速访问元素（例如，在数组中随机访问元素），vector 提供了常数时间复杂度（O(1)）的随机访问能力。
替代数组：在 C++ 编程中，vector 通常被用来替代传统的固定大小数组，因为它更加灵活，自动管理内存，并提供了许多便利的功能（如自动扩容、迭代器支持等）。
数学和科学计算：在科学计算、物理模拟、数学建模等领域中，vector 用于存储和操作大量数值数据，如矩阵的行或列。
游戏开发：在游戏开发中，vector 可用于存储游戏对象、粒子、坐标点等动态集合。
图形处理：在图形处理程序中，vector 可以用来存储像素数据、顶点信息、纹理坐标等。
缓冲区：vector 可以作为缓冲区来临时存储数据，例如网络应用中的数据包缓冲或文件读写操作。
容器的容器：在需要存储其他容器（如 vector<vector<int>> 用于二维数组）时，vector 也是一个不错的选择。

综上所述，vector 的灵活性和高效性使其成为 C++ 中最受欢迎的容器之一，广泛应用于各种编程场景。

7.list和vector有什么区别？

list 和 vector 是 C++ STL 中的两种常见容器，它们在底层实现、性能特性和适用场景方面有着显著的区别：

底层数据结构：
- vector 底层是一个动态数组，提供快速的随机访问，但在中间插入或删除元素效率较低。
- list 是一个双向链表，提供快速的任意位置插入和删除操作，但不支持直接的随机访问。
内存分配：
- vector 的元素存储在连续的内存块中，这有助于空间局部性和缓存效率，但可能导致较大的内存重新分配成本。
- list 的元素分散存储，每个元素单独分配内存，增加了额外的内存开销（例如，指针空间），但减少了内存重新分配的频率。
性能特点：
- vector 在末尾添加或删除元素非常高效，但在起始或中间位置进行这些操作效率较低。
- list 在任何位置添加或删除元素都非常高效，但访问元素（尤其是随机访问）的效率低于 vector。
应用场景：
- vector 适用于元素数量变化不大、需要快速随机访问或频繁在尾部添加/删除元素的场景。
- list 适合于元素数量经常变化、需要频繁在列表中间进行插入或删除操作的场景。
迭代器类型：
- vector 支持随机访问迭代器，可以进行+/-操作进行快速定位。
- list 支持双向迭代器，只能逐个元素前进或后退。
内存占用：
- vector 通常比 list 占用更少的内存，除非频繁扩容导致大量未使用的容量。
- list 的每个元素都需要额外的内存来存储前后元素的指针。

应用场景举例

vector：适用于需要快速随机访问的数据集，如数值计算、数组替代、数据缓冲区等。
list：适用于元素频繁插入和删除的场景，如实现队列、栈、复杂的数据结构调整等。

选择正确的容器类型对于优化程序性能和内存使用至关重要。在实际应用中，应根据具体需求和使用场景来选择 vector 或 list。

8.为什么list没有push_front()函数？

您的问题中有一点误解，实际上在C++的标准模板库（STL）中，std::list 是拥有 push_front() 函数的。这个函数用于在列表的前端插入一个元素，它是 std::list 这种双向链表结构的特性之一。

比如说，在某些应用场景中，我们需要快速在序列的前端添加元素，而不是后端。例如，在实现一个队列缓存（如先进先出的缓存策略）时，可能需要频繁地在列表的前端添加新的元素。这时，push_front() 就非常有用，因为它可以在 O(1) 的时间复杂度内完成操作，这对于性能敏感的应用来说是非常重要的。

示例代码如下：

#include <list>
#include <iostream>

int main() {
    std::list<int> mylist;

    // 在列表前端插入元素
    mylist.push_front(10);
    mylist.push_front(20);
    mylist.push_front(30);

    // 打印列表元素
    for (int n : mylist) {
        std::cout << n << '\n';
    }

    return 0;
}

这段代码创建了一个 std::list<int> 类型的列表，然后使用 push_front() 函数在列表前端依次插入了三个整数。最后，这段代码会打印出 30, 20, 10，即按照插入顺序的逆序显示。

9.list如何实现元素的插入和删除？

在C++标准模板库（STL）中，std::list 是一个双向链表。由于它的双向链表特性，std::list 支持在任何位置高效地插入和删除元素。

元素插入：

使用 push_back() 在列表尾部添加元素；
使用 push_front() 在列表头部添加元素；
使用 insert() 在指定位置插入元素。这需要一个迭代器指向插入点，插入操作之后迭代器将指向新插入的元素。

元素删除：

使用 pop_back() 删除列表尾部元素；
使用 pop_front() 删除列表头部元素；
使用 erase() 删除指定位置的元素。这同样需要一个迭代器指向要删除的元素；
使用 remove() 删除所有与指定值相等的元素。

由于链表的每个元素都是独立的节点，插入或删除操作不需要移动其它元素，因此这些操作通常都是常数时间复杂度（O(1)），这也是链表结构的优点之一。

示例应用场景：

当实现一个任务队列，且任务有不同的优先级时，可以使用 insert() 将高优先级的任务插入到适当的位置。
在游戏开发中，可能需要管理多个动态生成和销毁的对象，使用 std::list 可以有效地插入和删除这些对象。

示例代码：

#include <list>
#include <iostream>

int main() {
    std::list<int> mylist;

    // 在列表末尾插入元素
    mylist.push_back(1);
    mylist.push_back(2);
    mylist.push_back(3);

    // 在列表头部插入元素
    mylist.push_front(0);

    // 在第二个元素之后插入一个元素
    auto it = mylist.begin();
    std::advance(it, 2);
    mylist.insert(it, 5);

    // 删除第二个元素
    it = mylist.begin();
    std::advance(it, 1);
    mylist.erase(it);

    // 删除所有值为3的元素
    mylist.remove(3);

    // 打印列表的元素
    for (int n : mylist) {
        std::cout << n << '\n'; // 应该打印出 0, 1, 5
    }

    return 0;
}

在这段代码中，我们首先在 std::list 的头部和尾部插入了元素，然后找到了第二个元素的位置并在其后插入了一个新元素，接着删除了特定位置的元素，最后删除了所有值为3的元素。

10.map底层是如何实现的？

C++ 标准模板库（STL）中的 std::map 通常是基于平衡二叉搜索树实现的，最常见的是红黑树。红黑树是一种自平衡的二叉搜索树，它通过在树的节点中维护额外的信息（颜色标记为红或黑）来确保树保持平衡。这种平衡性质确保了 std::map 的主要操作（如插入、删除和查找）的时间复杂度保持在 O(log n)，其中 n 是树中元素的数量。

红黑树的特性：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
所有叶子（NIL节点）都是黑色的。
每个红色节点的两个子节点都是黑色的（没有两个连续的红色节点）。
从任何节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些特性帮助保持树的平衡，从而保证了高效的操作时间。

应用场景：

在需要快速查找、插入和删除的键值对集合中，std::map 是一个理想的选择。
它适用于数据库索引、缓存实现、频率统计等场景，其中元素经常被查找和更新。

示例代码：

#include <iostream>
#include <map>

int main() {
    // 创建一个map
    std::map<std::string, int> mymap;

    // 插入键值对
    mymap["apple"] = 5;
    mymap["banana"] = 3;
    mymap["orange"] = 2;

    // 访问元素
    std::cout << "apple has " << mymap["apple"] << " units.\n";

    // 查找元素
    auto it = mymap.find("banana");
    if (it != mymap.end()) {
        std::cout << "banana found with " << it->second << " units.\n";
    }

    // 删除元素
    mymap.erase("orange");

    return 0;
}

在这个例子中，我们创建了一个 std::map 来存储水果的库存，使用字符串作为键（水果的名字）和整数作为值（库存量）。我们展示了如何插入键值对，访问和查找特定的元素，以及如何删除元素。

11.set 的底层是如何实现的？

C++ 标准模板库（STL）中的 std::set 通常是基于平衡二叉搜索树实现的，与 std::map 类似，它的底层实现通常也是红黑树。红黑树的特性和优势同样适用于 std::set，使得它在插入、删除和查找操作上的时间复杂度都是 O(log n)，其中 n 是树中元素的数量。

std::set 的关键特性：

它存储的是唯一键值。即在 std::set 中，没有两个元素可以有相同的值。
元素被自动排序（通常是按照升序），这是由底层的二叉搜索树的性质决定的。

应用场景：

当需要一个集合来存储唯一元素，并且频繁进行查找、插入和删除操作时，std::set 是一个非常合适的选择。
std::set 常用于需要自动排序且不包含重复元素的场景，如在一组数据中查找不重复的元素，或者维护一个已排序的唯一元素集合。

示例代码：

#include <iostream>
#include <set>

int main() {
    // 创建一个set
    std::set<int> myset;

    // 插入元素
    myset.insert(3);
    myset.insert(1);
    myset.insert(4);
    myset.insert(1); // 这个插入操作不会成功，因为1已经存在

    // 遍历和打印元素
    std::cout << "Elements in set: ";
    for (int elem : myset) {
        std::cout << elem << " "; // 输出将是 1 3 4
    }
    std::cout << std::endl;

    // 查找元素
    if (myset.find(3) != myset.end()) {
        std::cout << "Element 3 is found in the set." << std::endl;
    }

    // 删除元素
    myset.erase(3);

    return 0;
}

在这段代码中，我们创建了一个 std::set<int> 并插入了几个整数。注意到尽管我们尝试插入了两次数字1，但在 std::set 中它只会存在一次。接下来，代码展示了如何遍历 std::set，检查元素是否存在，以及如何删除元素。由于 std::set 自动对元素进行排序，因此遍历结果将是有序的。

12.map、set、multimap、multiset有什么区别？

在C++的标准模板库（STL）中，map、set、multimap、和multiset是常用的关联容器，它们的主要区别在于存储键值对的方式和是否允许重复元素。

std::map：
- 存储键值对（key-value pairs），每个键都是唯一的。
- 查找、插入和删除操作的时间复杂度为 O(log n)。
- 常用于需要根据键快速查找值的场景。
std::set：
- 只存储键，不存储值。
- 每个键都是唯一的，不允许重复。
- 同样支持 O(log n) 时间复杂度的查找、插入和删除。
- 常用于需要维护一个不重复元素集合的场景。
std::multimap：
- 类似于 std::map，但允许多个元素拥有相同的键。
- 适用于需要将多个值关联到一个键的场景。
std::multiset：
- 类似于 std::set，但允许元素重复。
- 用于需要存储多个重复元素且保持元素排序的场景。

总的来说，map 和 set 提供了存储唯一元素的能力，而 multimap 和 multiset 允许存储重复元素。它们都基于红黑树（或其他类型的平衡二叉搜索树）实现，因此在元素的查找、插入和删除操作上表现出较高效率。选择使用哪一个容器取决于具体的应用需求，比如是否需要键值对、是否允许重复等因素。

13.如何在map和set中查找元素？

在C++的标准模板库（STL）中，std::map 和 std::set 都提供了高效的查找方法。这两种容器都基于红黑树（一种平衡二叉搜索树），因此它们的查找操作时间复杂度都是 O(log n)，其中 n 是容器中元素的数量。

在 std::map 中查找元素：

使用 find 方法：给定一个键，它返回一个指向该键的迭代器。如果键不存在，则返回 end() 迭代器。

std::map<int, std::string> myMap;
// ...（添加一些元素）

auto it = myMap.find(10); // 查找键为10的元素
if (it != myMap.end()) {
    std::cout << "Found: " << it->second << std::endl;
} else {
    std::cout << "Key not found." << std::endl;
}

使用 count 方法：这个方法返回与给定键匹配的元素数量。由于 map 中的键是唯一的，因此返回值要么是 0（未找到），要么是 1（找到了）。
```
if (myMap.count(10) > 0) {
    std::cout << "Key found." << std::endl;
} else {
    std::cout << "Key not found." << std::endl;
}
```

在 std::set 中查找元素：

使用 find 方法：和在 map 中的使用方式类似，这个方法在 set 中查找给定值的元素，并返回一个指向该元素的迭代器。如果元素不存在，则返回 end() 迭代器。

std::set<int> mySet;
// ...（添加一些元素）

auto it = mySet.find(5); // 查找值为5的元素
if (it != mySet.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Element not found." << std::endl;
}

使用 count 方法：在 set 中，count 方法返回值要么是 0（元素不存在），要么是 1（元素存在）。

if (mySet.count(5) > 0) {
    std::cout << "Element found." << std::endl;
} else {
    std::cout << "Element not found." << std::endl;
}

这些方法都是非常标准和直观的方式来查找 map 和 set 中的元素。由于这些容器底层是基于平衡二叉搜索树实现的，因此查找操作通常都是非常高效的。

14.unordered_map和map有什么区别？

在 std::map 中查找元素：

使用 find 方法：给定一个键，它返回一个指向该键的迭代器。如果键不存在，则返回 end() 迭代器。

std::map<int, std::string> myMap;
// ...（添加一些元素）

auto it = myMap.find(10); // 查找键为10的元素
if (it != myMap.end()) {
    std::cout << "Found: " << it->second << std::endl;
} else {
    std::cout << "Key not found." << std::endl;
}

使用 count 方法：这个方法返回与给定键匹配的元素数量。由于 map 中的键是唯一的，因此返回值要么是 0（未找到），要么是 1（找到了）。
```
if (myMap.count(10) > 0) {
    std::cout << "Key found." << std::endl;
} else {
    std::cout << "Key not found." << std::endl;
}
```

在 std::set 中查找元素：

std::set<int> mySet;
// ...（添加一些元素）

auto it = mySet.find(5); // 查找值为5的元素
if (it != mySet.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Element not found." << std::endl;
}

使用 count 方法：在 set 中，count 方法返回值要么是 0（元素不存在），要么是 1（元素存在）。

if (mySet.count(5) > 0) {
    std::cout << "Element found." << std::endl;
} else {
    std::cout << "Element not found." << std::endl;
}

15.什么是迭代器，它有什么作用？

迭代器是 C++ 标准模板库（STL）中的一个重要概念。简单来说，迭代器就像是一个指针，用于访问和遍历容器中的元素（比如数组、链表、集合等）。迭代器提供了一种统一的方法来访问容器中的元素，而不需要关心容器的具体类型。

迭代器的主要作用包括：

遍历容器: 通过迭代器可以遍历容器中的所有元素。例如，使用 begin() 和 end() 方法获取容器的起始和结束迭代器，然后通过循环来访问每个元素。
访问元素: 可以通过迭代器读取或修改容器中的元素。
连接算法与容器: STL 中的很多算法（如排序、查找等）都是通过迭代器来操作容器的。

应用场景示例

假设我们有一个 vector<int> 容器，存储了一些整数。我们可以使用迭代器来遍历这个 vector:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 使用迭代器遍历 vector
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

这段代码会输出 vector 中的所有元素。迭代器 it 在每次循环中都指向 vector 的下一个元素，直到达到 end()。这样的遍历方法比较通用，不依赖于容器的具体类型，这是迭代器的一个重要优势。

16.五种迭代器类型分别是什么？

C++ STL 中有五种主要的迭代器类型，它们分别是：

输入迭代器（Input Iterators）: 这种迭代器用于从容器中读取数据。它只支持单向遍历，即只能向前移动（通过 ++ 操作符）。输入迭代器只能进行一次读取，读取后迭代器就会前进到下一个元素。
输出迭代器（Output Iterators）: 与输入迭代器相反，输出迭代器用于向容器中写入数据。它同样只支持单向遍历，且只能进行一次写入操作，写入后迭代器会自动前进到下一个位置。
前向迭代器（Forward Iterators）: 前向迭代器类似于输入和输出迭代器，但它支持多次读写操作。它也只能单向遍历，但可以对同一个元素进行多次访问。
双向迭代器（Bidirectional Iterators）: 如其名，双向迭代器可以在容器中向前和向后移动。它扩展了前向迭代器的功能，使得迭代器可以使用 -- 操作符向前移动。双向迭代器在像 list 和 set 这样的容器中非常有用。
随机访问迭代器（Random Access Iterators）: 这是最强大的迭代器类型，它支持所有前面提到的迭代器的功能，并且能够进行随机访问。这意味着除了能够向前和向后移动，随机访问迭代器还能够直接跳跃到任意位置（如通过 + 或 - 操作符）。vector 和 deque 容器提供了随机访问迭代器。

这些迭代器类型构成了 STL 设计的基础，使得 STL 算法可以在不同类型的容器上以统一的方式工作。不同类型的迭代器提供了不同级别的功能和灵活性，使得我们可以根据需要选择合适的迭代器类型来操作容器。

17.什么是迭代器的失效？

迭代器失效指的是当容器发生变化时，之前获取的迭代器不再指向有效的元素或者不再有意义，这种情况在 C++ STL 编程中比较常见。迭代器失效主要发生在以下几种情况：

元素被删除或修改: 如果你删除了某个迭代器所指向的元素，那么这个迭代器就失效了。例如，在使用 vector 或 list 的 erase 方法删除元素后，指向被删除元素的迭代器会失效。
容器被重新分配: 对于某些容器（如 vector），如果容量被重新分配（比如在添加元素时容量不足以容纳更多元素），那么指向容器内元素的所有迭代器、引用和指针都将失效。
插入元素: 对于某些容器，如 vector 和 deque，在中间位置插入元素可能会导致指向插入位置之后元素的迭代器失效。

应对迭代器失效

谨慎操作: 在修改容器时，要小心处理迭代器。比如，在删除元素后，不要使用指向被删除元素的迭代器。
更新迭代器: 某些操作（如 insert 和 erase）会返回一个新的迭代器，指向特定的元素。可以使用这些新的迭代器来继续操作。
避免在循环中修改容器: 尽量避免在遍历容器的同时对其进行修改。如果需要这样做，可以使用新的迭代器来代替之前的迭代器。

例子

假设你有一个 vector<int>，并且正在遍历它：

std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it);
        // 此时 it 已经失效，再使用它将是不安全的
    }
}

在这个例子中，删除元素 3 后，it 迭代器失效了。继续使用这个迭代器可能会导致未定义行为。正确的做法是使用 erase 返回的新迭代器来继续遍历。

18.介绍一下STL中的算法库。

C++ 标准模板库（STL）中的算法库是一个功能强大的组件，提供了一系列用于数据处理和操作的通用算法。这些算法主要针对容器进行操作，包括但不限于序列容器（如 vector、list）和关联容器（如 set、map）。STL 算法的一个关键特点是它们与容器类型无关，这意味着同一个算法可以用在不同类型的容器上。

STL 算法库大致可以分为以下几类：

非修改性算法（Non-modifying algorithms）: 这类算法不修改容器中的元素。典型的操作包括遍历（for_each）、查找（find、find_if）、计数（count、count_if）、搜索（search）等。
修改性算法（Modifying algorithms）: 这类算法会修改容器中的元素。它们包括对元素进行操作的算法（如 copy、move、replace、fill）、删除操作（如 remove、unique）以及重新排列元素的操作（如 reverse、rotate、shuffle）。
排序和相关操作（Sorting and related operations）: 这些算法用于排序容器中的元素，如 sort、stable_sort、partial_sort。还包括用于在已排序的序列中执行操作的算法，如 binary_search、lower_bound、upper_bound。
数值算法（Numeric algorithms）: 这类算法主要用于数值计算，包括对序列进行数学运算（如 accumulate、inner_product）和生成数值序列（如 iota、adjacent_difference）。

应用示例

假设我们有一个 vector<int>，我们可以使用 STL 算法进行各种操作。例如，我们可以使用 sort 对其进行排序，使用 find 来查找特定元素，或使用 accumulate 来计算所有元素的总和：

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {4, 1, 3, 5, 2};

    // 排序
    std::sort(v.begin(), v.end());

    // 查找
    auto it = std::find(v.begin(), v.end(), 3);

    // 计算总和
    int sum = std::accumulate(v.begin(), v.end(), 0);

    std::cout << "Sorted vector: ";
    for (int n : v) std::cout << n << ' ';
    std::cout << "\nFound 3 at position: " << (it - v.begin());
    std::cout << "\nSum of elements: " << sum << std::endl;

    return 0;
}

STL 算法库的强大之处在于其通用性和灵活性。你可以在不同类型的容器上使用这些算法，且不需要改变算法本身。这大大简化了数据处理和操作的过程。

19.find()和binary_search()有什么区别？

find() 和 binary_search() 是 C++ STL 中的两种不同的搜索算法，它们的主要区别在于它们的工作原理和使用场景。

find() 函数:
- 工作原理: find() 是一种线性搜索算法。它从容器的开始位置遍历到结束位置，逐个检查每个元素，直到找到目标元素或遍历完所有元素。
- 时间复杂度: 因为它是一种线性搜索，所以在最坏的情况下，其时间复杂度是 O(n)，其中 n 是容器中元素的数量。
- 使用场景: find() 可以在任何类型的容器上使用，不论容器是否排序。这意味着它适用于无序容器（如 std::list、std::unordered_set）和有序容器（如 std::vector、std::set）。
binary_search() 函数:
- 工作原理: binary_search() 是一种二分搜索算法。它要求容器预先被排序。搜索开始于容器的中间元素，根据比较结果决定是继续在左侧子区间搜索还是右侧子区间搜索，这个过程递归进行，直到找到目标元素或确定元素不存在。
- 时间复杂度: 二分搜索的时间复杂度是 O(log n)，其中 n 是容器中元素的数量。这比线性搜索快得多，但前提是容器必须已经排序。
- 使用场景: binary_search() 仅适用于已排序的容器，如排序后的 std::vector、std::deque 或 std::array。它不适用于自然无序的容器，如 std::list 或 std::unordered_set。

示例

假设有一个已排序的 std::vector<int>：

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // 使用 find() 查找元素 3
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "find(): Element found." << std::endl;
    } else {
        std::cout << "find(): Element not found." << std::endl;
    }

    // 使用 binary_search() 查找元素 3
    bool found = std::binary_search(v.begin(), v.end(), 3);
    if (found) {
        std::cout << "binary_search(): Element found." << std::endl;
    } else {
        std::cout << "binary_search(): Element not found." << std::endl;
    }

    return 0;
}

在这个例子中，find() 通过遍历来查找元素 3，而 binary_search() 则利用二分搜索的方式来判断元素 3 是否存在。选择哪种搜索方法取决于容器是否已排序以及对时间效率的要求。

20.sort()函数的实现原理是什么？

sort() 函数是 C++ STL 中用于排序的一个重要算法。在大多数实现中，它是基于快速排序算法实现的，但具体实现可能会根据不同的情况选择不同的排序算法，以优化性能。以下是 sort() 函数的一些关键特点：

快速排序（Quick Sort）: 快速排序是 sort() 函数的主要实现算法。快速排序是一种分治算法，它通过选择一个“枢纽”元素来将数组分成两个子数组，一个包含所有小于枢纽的元素，另一个包含所有大于枢纽的元素。然后，它递归地对这两个子数组进行同样的操作。
插入排序（Insertion Sort）: 对于较小的数据集，快速排序可能不如插入排序高效。因此，sort() 函数在处理小数组时可能会使用插入排序。
归并排序（Merge Sort）: 在一些实现中，当递归到较小的子数组时，sort() 函数可能会使用归并排序，特别是在需要稳定排序（即相等元素的相对顺序保持不变）时。
内省排序（Introsort）: 内省排序是一种混合排序算法，结合了快速排序、堆排序（Heap Sort）和插入排序的特点。它从快速排序开始，但如果递归深度超过某个阈值（通常是基于待排序元素数量的对数），则改用堆排序。
性能: sort() 函数通常优化得很好，其平均时间复杂度为 O(n log n)，其中 n 是要排序的元素数量。它比 C 语言中的 qsort 函数更快，因为它使用模板，这允许在编译时进行更多优化。
稳定性: 标准并未要求 sort() 函数是稳定的。如果需要稳定排序，可以使用 stable_sort() 函数。