STL面试题库

CodeShouhu大约 38 分钟使用指南Markdown

STL面试题库

1，请详细解释 STL 的基本组成部分，以及每一个部分各自的作用

STL，也就是标准模板库，主要由以下六个基本组成部分构成：

容器（Containers）：容器是用来存储数据的数据结构，例如 vector、list、deque、set 和 map 等。从实现的角度看，STL 容器是一种类模板（class template）。
算法（Algorithms）：STL 提供了一系列常用算法，如 sort、search、copy 和 erase 等。这些算法从实现的角度来看，是一种函数模板（function template）。
迭代器（Iterators）：迭代器在容器中起到类似指针的作用，可以用来遍历容器中的元素。迭代器是一种将 operator*、operator->、operator++ 和 operator-- 等指针相关操作予以重载的类模板（class template）。
仿函数（Functors）：仿函数的行为类似于函数，可以作为算法的某种策略。它们通常用于自定义算法的行为。
适配器（Adapters）：适配器用于修饰容器、仿函数或迭代器的接口，使它们符合特定的需求。例如，STL 提供了 stack 和 queue 等适配器，它们对 deque 或 list 等容器进行了包装，以提供符合栈和队列特性的接口。
空间配制器（Allocators）：空间配制器负责空间的配置与管理。它们在容器的创建和销毁过程中管理内存空间，可以根据需求自定义内存管理策略。（1）对象的创建与销毁；（2）内存的获取与释放。

这些组成部分共同构成了 STL 的基本结构，为 C++ 程序员提供了强大且灵活的工具集，可用于处理各种数据结构和算法问题。

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
int main() {  
    // 创建一个vector容器  
    std::vector<int> vec{3, 1, 4, 1, 5, 9, 2, 6, 5};  
  
    // 使用STL算法对vector容器进行排序  
    std::sort(vec.begin(), vec.end());  
  
    // 使用STL算法在vector容器中查找元素  
    auto it = std::find(vec.begin(), vec.end(), 5);  
    if (it != vec.end()) {  
        std::cout << "Found the element: " << *it << std::endl;  
    } else {  
        std::cout << "Element not found." << std::endl;  
    }  
  
    // 输出排序后的vector容器中的元素  
    for (auto& elem : vec) {  
        std::cout << elem << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

输出：

Found the element: 5  
1 1 2 3 4 5 5 6 9

上述代码中，我们使用了STL的vector容器来存储整数数据，使用std::sort算法对容器中的元素进行排序，使用std::find算法查找容器中的元素，并通过迭代器输出排序后的元素。

速记

2，详细解释 STL 中常见的容器，每类型的容器包含的特征，举例

STL 中的常见容器主要分为三类：顺序容器、关联式容器和容器适配器。

顺序容器（Sequence Containers）：顺序容器是一种线性结构的可变大小容器，元素按顺序存储和访问。STL 提供了几种顺序容器，如 vector、list、deque 和 array。
- vector：vector 使用动态数组实现，支持随机访问。当元素数量超过当前容量时，vector 会重新分配内存空间，并将所有元素复制到新的内存空间。
- list：list 使用双向链表实现，不支持随机访问。它可以在常数时间内进行元素的插入和删除操作。
- deque：deque 使用双端队列实现，支持随机访问。与 vector 类似，deque 也支持在头部和尾部的快速插入和删除操作。
- array：array 是 C++11 引入的固定大小数组容器，不支持动态扩展。
  关联式容器（Associative Containers）：关联式容器是非线性结构的容器，元素通过键值进行存储和访问。STL 提供了几种关联式容器，如 set、multiset、map 和 multimap。
- set/multiset：set 和 multiset 使用红黑树实现，元素按键值的顺序存储。set 不允许重复键值，而 multiset 允许重复键值。
- map/multimap：map 和 multimap 也使用红黑树实现，元素按键值的顺序存储。map 存储的是键值对，键唯一，而 multimap 允许重复键。
容器适配器（Container Adapters）：容器适配器是对其他容器的接口进行包装，以提供特定功能的容器。STL 提供了几种容器适配器，如 stack、queue 和 priority_queue。
- stack：stack 是后进先出（LIFO）的数据结构，可以使用 deque、list 或 vector 作为底层容器实现。
- queue：queue 是先进先出（FIFO）的数据结构，可以使用 deque 或 list 作为底层容器实现。
- priority_queue：priority_queue 是一种优先队列，元素按优先级顺序出队。它可以使用 vector 或 deque 作为底层容器实现，并提供自定义比较函数来定义优先级。

这些容器的实现原理主要基于数据结构和算法，通过 C++ 的模板机制进行泛型化，以适应不同类型的数据需求。

#include <iostream>  
#include <vector>  
  
int main() {  
    std::vector<int> vec = {1, 2, 3, 4, 5};  
    for (int num : vec) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
    return 0;  
}
输出：
1 2 3 4 5
#include <iostream>  
#include <list>  
int main() {  
    std::list<int> lst = {1, 2, 3, 4, 5};  
    for (int num : lst) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
    return 0;  
}
输出：
1 2 3 4 5
#include <iostream>  
#include <forward_list>  
int main() {  
    std::forward_list<int> flst = {1, 2, 3, 4, 5};  
    for (int num : flst) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
    return 0;  
}
输出：
1 2 3 4 5
#include <iostream>  
#include <set>  
int main() {  
    std::set<int> st = {5, 2, 3, 1, 4};  
    for (int num : st) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
    return 0;  
}
输出：
1 2 3 4 5

#include <iostream>  
#include <multiset>  
  
int main() {  
    std::multiset<int> mst = {5, 2, 3, 1, 4, 2, 3};  
    for (int num : mst) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
    return 0;  
}
输出：
1 2 2 3 3 4 5
#include <iostream>  
#include <map>  
int main() {  
    std::map<std::string, int> mp = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};  
    for (const auto& pair : mp) {  
        std::cout << pair.first << ": " << pair.second << std::endl;  
    }  
    return 0;  
}
输出：
makefile
Alice: 25  
Bob: 30  
Charlie: 35

3，详细解释 STL 中 map hashtable deque list 的特征以及底层原理

STL（Standard Template Library）是C++的一部分，它提供了一系列通用的数据结构和算法。下面简要介绍一下你提到的几种STL容器的实现原理：

map：map 是一个关联容器，它存储的元素是键值对（key-value pair）。在内部，map 通常使用红黑树（Red-Black Tree）实现。红黑树是一种自平衡的二叉搜索树，能够在插入、删除和搜索操作中保持较好的性能。每个节点都包含一个键和一个值，键在树中用作排序的依据。map 的查找、插入和删除操作的时间复杂度通常为 O(log n)，其中 n 是容器中元素的数量。
hashtable：hashtable（也称为哈希表）是一个关联容器，它存储的元素也是键值对。hashtable 通过哈希函数（hash function）将键映射到一个固定大小的数组上。当插入或查找一个元素时，它首先计算键的哈希值，然后使用这个哈希值在数组中查找相应的位置。如果多个键映射到同一个数组位置（称为哈希冲突），hashtable 通常会使用链表或开放地址法来解决这个问题。hashtable 的查找、插入和删除操作的平均时间复杂度通常为 O(1)，但在最坏情况下可能会达到 O(n)。
deque：deque（双端队列，double-ended queue）是一个序列容器，它支持在容器的两端进行快速插入和删除操作。deque 的实现通常使用一个动态数组，并根据需要自动调整数组的大小。此外，deque 还可能使用一个或多个“控制块”（control block）来记录容器的状态信息（如当前大小、容量等）。deque 的插入和删除操作的时间复杂度通常为 O(1) 在容器两端，但在中间插入或删除元素的时间复杂度可能会较高。
list：list（链表，linked list）也是一个序列容器，但它与 deque 的实现方式有很大差异。list 中的元素是通过链表节点连接的，每个节点包含一个指向下一个节点和上一个节点的指针。这种结构使得 list 能够在常数时间内完成在容器任何位置的插入和删除操作。然而，由于链表的存储不是连续的，所以 list 的随机访问操作（如通过索引访问元素）的时间复杂度为 O(n)。

这些STL容器都为开发者提供了丰富的功能和灵活性，可以根据实际需求选择合适的容器来解决问题。

#include <iostream>  
#include <map>  
  
int main() {  
    std::map<std::string, int> age_map;  
    age_map["Alice"] = 20;  
    age_map["Bob"] = 30;  
    age_map["Charlie"] = 25;  
  
    for (const auto &pair : age_map) {  
        std::cout << pair.first << ": " << pair.second << std::endl;  
    }  
  
    return 0;  
}
输出：

makefile
Alice: 20  
Bob: 30  
Charlie: 25

#include <iostream>  
#include <unordered_map>  
  
int main() {  
    std::unordered_map<std::string, int> age_map;  
    age_map["Alice"] = 20;  
    age_map["Bob"] = 30;  
    age_map["Charlie"] = 25;  
  
    for (const auto &pair : age_map) {  
        std::cout << pair.first << ": " << pair.second << std::endl;  
    }  
  
    return 0;  
}
输出：

makefile
Alice: 20  
Bob: 30  
Charlie: 25
注意：由于hashtable不保证排序，所以输出可能与上例不同。


#include <iostream>  
#include <deque>  
  
int main() {  
    std::deque<int> d = {1, 2, 3, 4, 5};  
    d.push_front(0);  
    d.push_back(6);  
  
    for (const auto &elem : d) {  
        std::cout << elem << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}
输出：
0 1 2 3 4 5 6


#include <iostream>  
#include <list>  
  
int main() {  
    std::list<int> l = {1, 2, 3, 4, 5};  
    l.push_front(0);  
    l.push_back(6);  
  
    for (const auto &elem : l) {  
        std::cout << elem << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}
输出：
0 1 2 3 4 5 6

4，详细解释STL 的空间配置器的原理和作用

STL的空间配置器是一个模板类，用于管理对象的存储空间。它是STL容器中的一个关键组成部分，负责容器的内存分配和释放。

空间配置器的主要任务是：

分配内存空间：根据容器的需求，为元素分配适当大小的内存空间。
释放内存空间：当容器不再需要某个元素时，释放其内存空间。
构造和析构对象：在分配内存空间后，构造所需的对象；在释放内存空间前，析构对象。

空间配置器的设计使得STL容器可以与不同的内存管理策略一起使用。例如，可以使用自定义的空间配置器来实现特定的内存管理需求，如使用内存池、共享内存或其他自定义的内存管理机制。

内存配置操作: 通过alloc::allocate()实现内存释放操作: 通过alloc::deallocate()实现对象构造操作: 通过::construct()实现对象释放操作: 通过::destroy()实现

关于内存空间的配置与释放，SGI STL采用了两级配置器：一级配置器主要是考虑大块内存空间，利用malloc和free实现；二级配置器主要是考虑小块内存空间而设计的（为了最大化解决内存碎片问题，进而提升效率），采用链表free_list来维护内存池（memory pool），free_list通过union结构实现，空闲的内存块互相挂接在一块，内存块一旦被使用，则被从链表中剔除，易于维护。

使用自定义的空间配置器或多态的内存资源可以为STL容器提供更大的灵活性，使其适应不同的应用场景和性能需求。

#include <iostream>  
#include <memory>  
  
int main() {  
    // 创建一个空间配置器  
    std::allocator<int> allocator;  
  
    // 使用空间配置器分配内存空间  
    int* ptr = allocator.allocate(5);  
  
    // 在分配的内存空间上构造对象  
    for (int i = 0; i < 5; ++i) {  
        allocator.construct(ptr + i, i);  
    }  
  
    // 输出分配的内存空间中的值  
    for (int i = 0; i < 5; ++i) {  
        std::cout << ptr[i] << " ";  
    }  
    std::cout << std::endl;  
  
    // 释放内存空间  
    for (int i = 0; i < 5; ++i) {  
        allocator.destroy(ptr + i);  
    }  
    allocator.deallocate(ptr, 5);  
  
    return 0;  
}
输出：
0 1 2 3 4

在上面的示例中，我们首先创建了一个std::allocator<int>类型的空间配置器。然后，我们使用allocate函数分配了足够的内存空间来存储5个整数。接下来，我们使用construct函数在分配的内存空间上构造整数对象。最后，我们通过destroy函数销毁对象，并使用deallocate函数释放内存空间。

5，STL 容器用过哪些，以及各自的插入，查找，删除的时间复杂度是多少？

STL 提供了多种容器，每种容器在插入、查找和删除元素时的时间复杂度各不相同。以下是几种常用 STL 容器的插入、查找和删除时间复杂度及其原因：

vector：vector 使用动态数组实现，支持随机访问。在 vector 中插入或删除元素的时间复杂度为 O(n)，因为在最坏的情况下，需要移动插入或删除位置之后的所有元素。查找元素的时间复杂度也为 O(n)，因为需要遍历整个容器来查找元素。
list：list 使用双向链表实现，不支持随机访问。在 list 中插入或删除元素的时间复杂度为 O(1)，因为链表可以在常数时间内插入或删除元素。查找元素的时间复杂度为 O(n)，因为链表只能从头或尾开始遍历，直到找到目标元素或遍历完整个链表。
deque：deque 使用双端队列实现，支持随机访问。在 deque 中插入或删除元素的时间复杂度为 O(1)，因为 deque 可以在常数时间内从头部或尾部插入或删除元素。查找元素的时间复杂度为 O(n)，因为需要遍历整个容器来查找元素。
set/multiset：set 和 multiset 使用红黑树实现，元素按键值的顺序存储。在 set 或 multiset 中插入、查找或删除元素的时间复杂度为 O(log n)，因为红黑树是一种自平衡的二叉搜索树，可以利用键值进行快速插入、查找和删除操作。
map/multimap：map 和 multimap 也使用红黑树实现，元素按键值的顺序存储。在 map 或 multimap 中插入、查找或删除元素的时间复杂度同样为 O(log n)，因为它们的内部实现与 set 和 multiset 类似，也是利用键值进行快速插入、查找和删除操作。

需要注意的是，这些时间复杂度都是在最坏情况下的估计，实际运行时间可能会受到数据分布、元素数量和其他因素的影响。在选择容器时，需要根据具体应用场景和性能需求来选择最合适的容器。

6，迭代器用过吗？什么时候会失效？

用过，常用容器迭代器失效情形如下。

对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。
对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可。
对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。

7，说一下STL中迭代器的作用，有指针为何还要迭代器？

STL 中的迭代器是一种类似于指针的对象，用于遍历容器中的元素。迭代器提供了一种统一的接口，可以用来访问不同类型容器中的元素，如 vector、list、set 等。

迭代器的作用主要有以下几点：

遍历容器中的元素：通过迭代器可以依次访问容器中的每个元素，进行读取或修改操作。
过滤容器中的元素：迭代器可以与 STL 算法结合使用，对容器中的元素进行过滤、排序、查找等操作。
支持多种遍历方式：迭代器支持从前向后、从后向前、跳跃等多种遍历方式，可以根据需求灵活选择。

指针和迭代器的区别主要有以下几点：

迭代器是类模板，表现的像指针，但它不是指针。迭代器封装了指针，并提供了一种更高级的行为，可以根据不同类型的数据结构来实现不同的操作。
迭代器提供了比指针更安全的操作。迭代器在访问元素时会进行边界检查，避免了越界访问的问题。而指针操作时需要手动管理内存，容易引发内存泄漏和越界访问等问题。
迭代器可以与 STL 算法结合使用，实现多种复杂的数据操作。而指针只能进行基本的内存访问和算术运算。
迭代器的操作更加符合面向对象的思想，可以通过重载操作符来实现不同的操作，更加灵活和易于理解。指针的操作则更加底层和直接，需要掌握指针的特性和操作规则。
迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输出其自身。

总之，迭代器是 STL 中的重要概念，提供了一种统一且安全的接口来访问容器中的元素。与指针相比，迭代器更加灵活、安全和易于使用。

以下是一个使用 STL 迭代器的示例，展示了如何遍历 vector 容器中的元素并打印出来：

#include <iostream>
#include <vector>

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

    // 使用 begin() 和 end() 获取容器的起始和结束迭代器
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";  // 解引用迭代器访问元素
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，我们使用了 begin() 和 end() 方法来获取 vector 容器的起始和结束迭代器。通过循环遍历迭代器，我们可以依次访问容器中的每个元素，并使用 *it 来解引用迭代器访问元素的值。最后，我们将元素打印到控制台上。

需要注意的是，在使用迭代器遍历容器时，需要确保迭代器不会越过容器的结束迭代器，否则会导致未定义的行为。同时，如果需要修改容器中的元素，可以使用迭代器的解引用操作符 *it 来访问元素并进行修改。

7，说说 STL 迭代器是怎么删除元素的

在 STL 中，删除元素有多种方式，可以使用容器的成员函数 erase，也可以使用 STL 算法 remove 或 remove_if 结合容器的 erase 方法。无论哪种方式，都需要使用迭代器来定位要删除的元素。

对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器；
对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可；
对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。

以下是使用迭代器删除元素的示例：

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 使用 erase 方法删除指定位置的元素
    vec.erase(vec.begin() + 3);  // 删除下标为 3 的元素，即数字 4

    // 使用 remove 和 erase 方法删除指定值的元素
    vec.erase(std::remove(vec.begin(), vec.end(), 5), vec.end());  // 删除所有值为 5 的元素

    // 使用 remove_if 和 erase 方法删除满足条件的元素
    vec.erase(std::remove_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }), vec.end());  // 删除所有偶数元素

    // 输出删除后的容器内容
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个示例中，我们展示了三种删除元素的方式：使用 erase 方法删除指定位置的元素，使用 remove 和 erase 方法删除指定值的元素，使用 remove_if 和 erase 方法删除满足条件的元素。在每种方式中，我们都使用了迭代器来定位要删除的元素，并调用相应的函数进行删除。需要注意的是，在使用 remove 或 remove_if 方法后，我们需要调用 erase 方法来清除被标记为删除的元素。

需要注意的是，在使用迭代器删除元素时，需要确保迭代器不会越过容器的结束迭代器，否则会导致未定义的行为。同时，删除元素后，被删除元素之后的元素的迭代器会失效，需要重新获取迭代器才能继续遍历。

8，说 STL 中 resize 和 reserve 的区别

STL 中的 resize 和 reserve 方法都是用于容器空间管理的函数，但它们的区别在于用途和行为。

resize 方法用于改变容器的大小，使其能够容纳指定数量的元素。如果容器原来的大小小于指定的大小，resize 会添加新元素到容器的末尾；如果容器原来的大小大于指定的大小，resize 会删除多余的元素。新添加的元素会进行值初始化，也就是调用元素的默认构造函数。如果需要，还可以提供一个额外的参数来指定新添加元素的初始值。

reserve 方法用于预分配容器所需的内存空间，但不改变容器的大小。它的目的是提高容器的性能，避免在添加大量元素时频繁重新分配内存。reserve 方法只会预分配内存空间，并不会创建新的元素，也不会删除多余的元素。

需要注意的是，resize 方法可能会改变容器的大小，而 reserve 方法不会。因此，在使用这两个方法时需要明确目的和需求，以避免不必要的操作或错误。

首先必须弄清楚两个概念：
（1）capacity：该值在容器初始化时赋值，指的是容器能够容纳的最大的元素的个数。还不能通过下标等访问，因为此时容器中还没有创建任何对象。
（2）size：指的是此时容器中实际的元素个数。可以通过下标访问0-(size-1)范围内的对象。
resize和reserve区别主要有以下几点：
（1）resize既分配了空间，也创建了对象；reserve表示容器预留空间，但并不是真正的创建对象，需要通过insert（）或push_back（）等创建对象。
（2）resize既修改capacity大小，也修改size大小；reserve只修改capacity大小，不修改size大小。
（3）两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为0）；reserve只带一个参数，表示容器预留的大小。

以下是一个简单的示例代码，展示了 resize 和 reserve 方法的使用：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;

    // 使用 resize 方法改变容器大小
    vec.resize(5, 10);  // 将容器大小改为 5，新添加的元素初始值为 10
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 使用 reserve 方法预分配内存空间
    vec.reserve(10);  // 预分配足够的内存空间来容纳 10 个元素
    for (int i = 0; i < 5; ++i) {
        vec.push_back(i);  // 添加新元素到容器末尾
    }
    for (int x : vec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

9，说说 STL 容器动态链接可能产生的问题？

STL 容器动态链接可能产生的问题主要包括以下几个方面：

迭代器、指针和引用失效：当容器进行动态内存重新分配时，原有的迭代器、指针和引用可能会失效。这是因为在重新分配内存时，容器的内存地址可能发生改变，导致原有的迭代器、指针和引用指向的内存位置无效。为了避免这个问题，需要在容器进行动态内存重新分配前，重新获取迭代器、指针和引用。
内存泄漏和内存碎片：如果动态链接库中的容器对象没有被正确释放，可能会导致内存泄漏。此外，频繁地进行动态内存分配和释放，可能会导致内存碎片的产生，影响程序的性能。为了避免这个问题，需要确保在使用完容器对象后正确释放内存，并尽量避免频繁地进行动态内存分配和释放。
容器大小限制：动态链接库中的容器大小可能会受到限制，因为动态链接库的内存空间是有限的。如果容器的大小超出了动态链接库的内存空间限制，可能会导致程序崩溃或运行异常。为了避免这个问题，需要合理规划容器的大小，并确保在容器大小超出限制时能够进行正确的错误处理。
多线程访问问题：当多个线程同时访问动态链接库中的容器时，可能会出现数据竞争和线程安全问题。这是因为在多线程环境下，多个线程可能同时修改容器的数据，导致数据的不一致性和不可预测性。为了避免这个问题，需要使用线程安全的容器或采取其他同步机制来保证多线程访问的安全性。

总之，在使用 STL 容器进行动态链接时，需要注意迭代器、指针和引用的失效问题，避免内存泄漏和内存碎片的产生，合理规划容器的大小，并处理好多线程访问的安全问题。

10，详细解释 map 和 unordered_map 的不同之处？以及底层实现原理

map 和 unordered_map 是 STL 中的两种关联容器，它们都可以存储键值对，并通过键进行快速访问。然而，它们在底层实现和使用方式上有一些区别。

底层实现：map 底层实现是红黑树，而 unordered_map 底层实现是哈希表。红黑树是一种自平衡的二叉查找树，它的查找、插入和删除操作的时间复杂度都是 O(log n)，其中 n 是容器中元素的数量。哈希表则是一种通过计算哈希值来快速访问数据的数据结构，它的查找、插入和删除操作的时间复杂度在最理想的情况下可以达到 O(1)，但在哈希冲突严重时可能会退化到 O(n)。
排序：由于 map 底层实现是红黑树，它会根据键的大小自动进行排序，因此 map 中的元素是有序的。而 unordered_map 底层实现是哈希表，它并不保证元素的有序性。
空间复杂度：由于哈希表需要额外的空间来存储哈希桶等信息，因此 unordered_map 的空间复杂度通常会比 map 高一些。
哈希函数和等价关系：unordered_map 需要提供哈希函数和等价关系，而 map 则只需要提供比较函数。哈希函数用于计算键的哈希值，等价关系用于判断两个键是否相等。比较函数用于比较两个键的大小。

总的来说，map 和 unordered_map 都有各自的优点和适用场景。如果需要保持元素的有序性，或者需要使用自定义的比较函数，那么可以选择 map。如果需要快速的查找和插入操作，并且不太关心元素的有序性，那么可以选择 unordered_map。

#include <iostream>  
#include <map>  
#include <unordered_map>  
  
int main() {  
    // std::map 示例  
    std::map<int, std::string> map;  
    map[5] = "five";  
    map[3] = "three";  
    map[8] = "eight";  
    map[1] = "one";  
  
    std::cout << "std::map:" << std::endl;  
    for (const auto &pair : map) {  
        std::cout << pair.first << ": " << pair.second << std::endl;  
    }  
  
    // std::unordered_map 示例  
    std::unordered_map<int, std::string> unordered_map;  
    unordered_map[5] = "five";  
    unordered_map[3] = "three";  
    unordered_map[8] = "eight";  
    unordered_map[1] = "one";  
  
    std::cout << "std::unordered_map:" << std::endl;  
    for (const auto &pair : unordered_map) {  
        std::cout << pair.first << ": " << pair.second << std::endl;  
    }  
  
    return 0;  
}
输出示例：

yaml
复制代码
std::map:  
1: one  
3: three  
5: five  
8: eight  
  
std::unordered_map:  
5: five  
3: three  
8: eight  
1: one
请注意，由于std::unordered_map是基于哈希表实现的，因此每次运行程序时，元素的顺序可能会不同。

11，说说 c++中vector 和 list 的区别，特点，优点，缺点，分别适用于什么场景？

vector 和 list 是 C++ 中的两种标准容器，它们都可以存储和管理一组元素，但它们的内部实现方式和性能特性有很大的差异。

vector

vector 是一个动态数组，它在内存中以连续的方式存储元素。它的主要特点包括：

随机访问：由于 vector 在内存中以连续的方式存储元素，因此可以快速地直接访问任何位置的元素（O(1) 时间复杂度）。
尾部插入和删除效率高：在 vector 的尾部插入或删除元素的时间复杂度是 O(1)。
空间效率：vector 会预先分配一块内存，如果元素数量超过了预先分配的内存，那么 vector 会重新分配一块更大的内存，并把原来的元素复制到新的内存中。这可能导致一些额外的开销。

适用于以下场景：

需要随机访问元素的场景。
需要在尾部进行插入和删除操作的场景。
对于元素数量可以预先估计，或者对内存使用不是特别敏感的场景。

list

list 是一个双向链表，它在内存中以非连续的方式存储元素。它的主要特点包括：

任意位置插入和删除效率高：在 list 中的任何位置插入或删除元素的时间复杂度都是 O(1)。
不支持随机访问：由于 list 在内存中以非连续的方式存储元素，因此访问某个位置的元素需要从头部或尾部开始遍历链表，时间复杂度为 O(n)。
空间效率：list 的元素是分散存储的，每个元素都包含了指向下一个和上一个元素的指针，因此 list 的空间开销比 vector 大。

适用于以下场景：

需要在任意位置进行插入和删除操作的场景。
对于元素的访问顺序是线性的，不需要随机访问的场景。
对于内存使用比较敏感，需要尽量减少内存重新分配的场景。

总的来说，vector 和 list 各有其优点和缺点，选择哪个容器取决于具体的使用场景和需求。

#include <iostream>  
#include <vector>  
#include <list>  
  
int main() {  
    // vector 示例  
    std::vector<int> vec{1, 2, 3, 4, 5};  
    std::cout << "vector: ";  
    for (int i : vec) {  
        std::cout << i << ' ';  
    }  
    std::cout << '\n';  
  
    // 在vector中间插入元素  
    vec.insert(vec.begin() + 2, 100);  
    std::cout << "vector after insert: ";  
    for (int i : vec) {  
        std::cout << i << ' ';  
    }  
    std::cout << '\n';  
  
    // list 示例  
    std::list<int> lst{1, 2, 3, 4, 5};  
    std::cout << "list: ";  
    for (int i : lst) {  
        std::cout << i << ' ';  
    }  
    std::cout << '\n';  
  
    // 在list中间插入元素  
    lst.insert(lst.begin(), 100);  
    std::cout << "list after insert: ";  
    for (int i : lst) {  
        std::cout << i << ' ';  
    }  
    std::cout << '\n';  
  
    return 0;  
}

在这个例子中，我们首先创建了一个vector和一个list，然后在它们的中间插入一个元素。我们可以看到，对于vector，插入操作可能会导致元素的移动，而对于list，插入操作则不会导致其他元素的移动。

12，简述 vector 的实现原理，新增元素，删除元素，迭代器iteraotr

vector 是 C++ 标准库中的一个动态数组，其实现原理是基于连续的内存空间来存储元素。vector 会根据需要自动管理内存，动态地增长或缩小其容量。

新增元素

在 vector 中新增元素有两种方式：使用 push_back() 函数在尾部添加元素，或使用 insert() 函数在指定位置插入元素。

当使用 push_back() 函数时，如果当前的内存空间已经不足以容纳新的元素，vector 会自动重新分配一块更大的内存空间，并把原来的元素复制到新的内存中。

当使用 insert() 函数时，vector 首先需要找到指定位置的元素，然后把该位置及其之后的元素都向后移动一个位置，以便为新元素腾出空间。如果当前的内存空间不足以容纳新的元素，vector 也会自动重新分配内存。

删除元素

在 vector 中删除元素有两种方式：使用 erase() 函数删除指定位置的元素，或使用 clear() 函数清空整个 vector。

当使用 erase() 函数时，vector 首先需要找到指定位置的元素，然后把该位置之后的元素都向前移动一个位置，以便填补被删除元素的空缺。

当使用 clear() 函数时，vector 会把所有元素都删除，并释放内存空间。

迭代器 iterator

vector 提供了迭代器来访问和操作其中的元素。迭代器是一个类似于指针的对象，可以用来遍历 vector 中的元素。

vector 的迭代器支持随机访问，可以在常数时间内访问到任意位置的元素。此外，迭代器还支持自增、自减、比较等操作，可以方便地对 vector 进行遍历和修改。

例如，可以使用以下代码来遍历 vector 中的所有元素：

std::vector<int> vec = {1, 2, 3, 4, 5};
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}

这段代码会输出 1 2 3 4 5。其中，vec.begin() 返回一个指向 vector 第一个元素的迭代器，vec.end() 返回一个指向 vector 末尾位置的迭代器。在循环中，通过迭代器来访问 vector 中的每个元素，并输出其值。

13，简述 STL 中的 map 的实现原理

STL 中的 map 是一个关联容器，用于将键值对（key-value pairs）存储为对应的键（key）和值（value）。map 的实现原理主要是基于红黑树（Red-Black Tree）这种自平衡二叉搜索树。

红黑树是一种特殊的二叉搜索树，它通过调整节点的颜色（红色或黑色）和旋转操作来保持树的平衡，从而保证了在最坏情况下的时间复杂度为 O(log n)。在 map 中，键（key）作为红黑树的键，值（value）作为红黑树的值。

map 中的元素按照键的顺序进行排序，默认情况下是按照键的升序排列。map 支持根据键进行快速查找、插入、删除和修改操作。当进行这些操作时，map 会根据键的值在红黑树中进行搜索，找到相应的节点并进行操作。

map 的迭代器是一个双向迭代器，可以支持从前往后和从后往前遍历 map 中的元素。此外，map 还提供了一些函数，如 find()、count()、erase() 等，方便对元素进行查找、计数和删除操作。

STL（Standard Template Library，标准模板库）中的 map 是一种关联容器，它存储的元素具有键值对（key-value pair）的结构。map 内部的元素会按照键值自动排序。

map 的实现一般是基于红黑树（Red-Black Tree）的，这是一种自平衡的二叉搜索树。map 的键（key）就是红黑树的节点，而值（value）则是存储在相应节点上的数据。

map 的基本操作（如插入、删除和查找）的时间复杂度为 O(log n)，其中 n 是 map 中的元素数量。这是因为在红黑树中，从根节点到任意叶子节点的最长路径不会超过最短路径的两倍，这就保证了操作的效率。

下面是一个简单的 map 使用案例：

#include <iostream>
#include <map>

int main() {
    // 创建一个空的 map 对象
    std::map<int, std::string> myMap;

    // 插入元素
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    // 查找元素
    std::cout << "The value of key 2 is: " << myMap[2] << std::endl;

    // 遍历元素
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    // 删除元素
    myMap.erase(2);

    return 0;
}

在这个例子中，我们首先创建了一个空的 map 对象 myMap，然后插入了三个键值对。接着，我们查找了键为 2 的元素，并输出了它的值。然后，我们遍历了 myMap 中的所有元素，并输出了它们的键和值。最后，我们删除了键为 2 的元素。

14，详细说明push_back 和 emplace_back 的不同之处

push_back和emplace_back都是C++ STL（Standard Template Library，标准模板库）中用于在容器末尾添加元素的方法，但它们在实现方式和效率上有一些区别。

push_back方法接受一个对象作为参数，并将该对象的副本添加到容器的末尾。这意味着在添加对象之前，必须先创建该对象，涉及到构造函数和拷贝构造函数的调用。如果容器存储的是自定义类型的对象，这可能会导致不必要的对象构造和拷贝。

相比之下，emplace_back方法接受与容器中元素类型相对应的参数，并直接在容器的末尾构造一个新对象。这避免了不必要的对象构造和拷贝，因为它在插入之前直接调用构造函数。此外，emplace_back的参数是可变参数模板，因此它可以接受任意数量的参数，并根据容器中的元素类型自动推断参数类型，使得emplace_back更加灵活。

如果要将一个临时变量push到容器的末尾，push_back()需要先构造临时对象，再将这个对象拷贝到容器的末尾，而emplace_back()则直接在容器的末尾构造对象，这样就省去了拷贝的过程。

总的来说，emplace_back相比push_back更高效，因为它避免了对象的复制操作。然而，emplace_back只能用于直接在向量中构造新元素的情况，如果要将现有对象添加到向量中，则必须使用push_back。

#include <iostream>  
#include <vector>  
#include <string>  
  
int main() {  
    std::vector<std::string> v1;  
    std::vector<std::string> v2;  
  
    // 使用 push_back 添加元素  
    v1.push_back("hello");  
    v1.push_back("world");  
  
    // 使用 emplace_back 添加元素  
    v2.emplace_back("hello");  
    v2.emplace_back("world");  
  
    // 输出 v1 中的元素  
    std::cout << "v1: ";  
    for (const auto& s : v1) {  
        std::cout << s << " ";  
    }  
    std::cout << std::endl;  
  
    // 输出 v2 中的元素  
    std::cout << "v2: ";  
    for (const auto& s : v2) {  
        std::cout << s << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

输出结果如下：

v1: hello world   
v2: hello world

可以看到，无论是使用push_back还是emplace_back，最终的输出结果都是相同的。但是，在使用emplace_back时，如果构造函数的参数是右值引用，则可以避免不必要的拷贝或移动操作，从而提高性能。

15，在C++的STL 中 vector 与 list 底层原理是怎么实现的？

STL（Standard Template Library，标准模板库）中的 vector 和 list 是两种常用的序列容器，它们的具体实现方式和常见操作的时间复杂度如下：

vector 的实现方式：

vector 底层采用连续存储的方式，即一块连续的内存空间存储所有的元素。vector 的实现类似于动态数组，它可以根据需要自动扩展容量。当元素数量超过当前容量时，vector 会重新分配一块更大的内存空间，将原有元素复制到新空间中，并释放原空间。

常见操作的时间复杂度：

插入操作：在尾部插入元素的复杂度为 O(1)，在其他位置插入元素的复杂度为 O(n)，其中 n 为 vector 的长度。
删除操作：删除尾部元素的复杂度为 O(1)，删除其他位置元素的复杂度为 O(n)。
查找操作：查找元素的复杂度为 O(n)。
访问操作：访问元素的复杂度为 O(1)。

list 的实现方式：

list 底层采用双向链表的方式实现，每个节点包含数据部分和指向前后节点的指针。list 的元素在内存中是分散存储的，通过指针相互连接。

常见操作的时间复杂度：

插入操作：在任意位置插入元素的复杂度为 O(1)。
删除操作：删除任意位置元素的复杂度为 O(1)。
查找操作：查找元素的复杂度为 O(n)。
访问操作：访问元素的复杂度为 O(n)。

可以看出，vector 和 list 在实现方式和操作复杂度上有明显的区别。vector 适用于需要随机访问元素的场景，而 list 适用于需要频繁插入和删除元素的场景。在实际应用中，可以根据具体需求选择合适的容器。

#include <iostream>  
#include <vector>  
#include <list>  
#include <chrono>  
  
int main() {  
    // vector  
    std::vector<int> vec;  
    auto start = std::chrono::high_resolution_clock::now();  
    for (int i = 0; i < 100000; ++i) {  
        vec.push_back(i);  
    }  
    auto end = std::chrono::high_resolution_clock::now();  
    std::chrono::duration<double> diff = end - start;  
    std::cout << "vector push_back time: " << diff.count() << " s\n";  
  
    start = std::chrono::high_resolution_clock::now();  
    vec.pop_back();  
    end = std::chrono::high_resolution_clock::now();  
    diff = end - start;  
    std::cout << "vector pop_back time: " << diff.count() << " s\n";  
  
    start = std::chrono::high_resolution_clock::now();  
    std::cout << vec[49999] << "\n";  
    end = std::chrono::high_resolution_clock::now();  
    diff = end - start;  
    std::cout << "vector access time: " << diff.count() << " s\n";  
  
    // list  
    std::list<int> lst;  
    start = std::chrono::high_resolution_clock::now();  
    for (int i = 0; i < 100000; ++i) {  
        lst.push_back(i);  
    }  
    end = std::chrono::high_resolution_clock::now();  
    diff = end - start;  
    std::cout << "list push_back time: " << diff.count() << " s\n";  
  
    start = std::chrono::high_resolution_clock::now();  
    lst.pop_back();  
    end = std::chrono::high_resolution_clock::now();  
    diff = end - start;  
    std::cout << "list pop_back time: " << diff.count() << " s\n";  
  
    start = std::chrono::high_resolution_clock::now();  
    auto it = lst.begin();  
    std::advance(it, 49999);  
    std::cout << *it << "\n";  
    end = std::chrono::high_resolution_clock::now();  
    diff = end - start;  
    std::cout << "list access time: " << diff.count() << " s\n";  
  
    return 0;  
}

这个程序首先创建了一个 vector 和一个 list，然后向它们分别插入了 100000 个元素，接着删除了最后一个元素，最后访问了第 50000 个元素。程序输出了这些操作所花费的时间。注意，由于硬件和操作系统的影响，实际运行的时间可能会有所不同。

16，仿函数了解吗？有什么作用

仿函数（Functor）是一种重载了函数调用运算符“operator()”的类或结构体，使得它可以像函数一样被调用。仿函数可以接受参数并返回值，在C++的STL（Standard Template Library，标准模板库）中被广泛应用。

仿函数的作用主要有以下几点：

提供一种灵活的方式来实现函数对象，可以根据实际需求定制自己的函数对象，比如排序、查找等算法。
仿函数可以封装函数参数，使得算法可以接受不同类型的参数，而不仅仅是简单的数据类型，这样可以增加算法的通用性。
仿函数可以保存状态，可以在多次调用之间保持状态，这样可以避免在每次调用时都需要重新计算。
仿函数可以用于函数指针的替代，因为函数指针只能指向全局函数或静态成员函数，而仿函数可以指向任意类型的函数，包括成员函数和非静态成员函数。

在STL中，仿函数通常用于自定义算法的行为。例如，在使用STL的sort算法进行排序时，可以传入一个自定义的仿函数来定义元素的比较规则。这样，通过使用不同的仿函数，可以实现不同的排序方式，如升序排序、降序排序等。

总的来说，仿函数是一种非常灵活和强大的工具，可以用于实现各种算法和数据结构，提高程序的可读性和可维护性。

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

class Student {
public:
    Student(const std::string& n, int s) : name(n), score(s) {}
    std::string name;
    int score;
};

class CompareScore {
public:
    bool operator()(const Student& s1, const Student& s2) {
        return s1.score > s2.score; // 按照成绩从大到小排序
    }
};

int main() {
    std::vector<Student> students = {{"Tom", 80}, {"Jerry", 90}, {"Bob", 70}};
    std::sort(students.begin(), students.end(), CompareScore());
    for (const auto& student : students) {
        std::cout << student.name << " " << student.score << std::endl;
    }
    return 0;
}

STL面试题库