八股文-0901

知识列表

enum class
std::chrono
default和delete
列表初始化
shared_ptr底层实现，是否线程安全
shared_ptr复制给weak_ptr时内部做了什么
STL容器是线程安全的吗？怎么样在多线程环境下使用容器
map和unordered_map的区别
红黑树和哈希表的复杂度
哈希表的底层实现，哈希平衡算法
红黑树有什么好处
Linux的线程调度底层是不是红黑树？
vector
迭代器的++it和it++哪个好
vector和list的区别
list和deque的区别
map的插入方式
迭代器失效
STL如何解决哈希冲突的
priority_queue的底层原理及使用场景
何时使用forward_list
stack
如何优化大量的数据的插入
STL排序算法是如何工作的，他们如何与容器互动？
迭代器和指针的区别

1.enum class

enum class是C++11引入的一种强枚举类型，解决了传统枚举类型的命名冲突和隐式转换问题

在传统的枚举中，枚举是全局可见的，所以当两个枚举中有重名的成员时，编译器会不知道调用哪个枚举成员，而enum class的成员的访问必须使用类作用域来访问，避免了冲突

在传统的枚举中，成员是可以与整数相互转换的，而enum class 禁止成员与整数的相互转换

在 C++ 中，enum class 的默认值与传统的枚举（enum）略有不同。默认情况下，enum class 的第一个枚举值的整数值为 0，后续值依次递增，但如果没有显式指定值，enum class 的枚举值不会自动赋予其他值。

2.std::chrono

std::chrono是C++11引入的时间库，用于处理时间点，时间段和时钟。std::chrono提供了类型安全和高精度的时间处理。

std::chrono的基本组件

时间点：std::chrono::time_point：表示某个时钟的特定时间

时间段：std::chrono::duration：表示时间间隔

时钟：std::chrono::steady_clock , std::chrono::system_clock , std::chrono::high_resolution_clock：提供当前时间点

std::chrono的用法

获取当前时间。auto now = std::chrono::system_clock::now(); std::time_t now_c = std::chrono::system_clock::to_time(now); std::cout <<std::ctime(&now_c);
测量代码执行时间。auto start = std::chrono::high_resolution_clock::now();
std::this_thread::sleep_for(std::chrono::seconds(2));
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = end – start;
std::cout << “Task took ” << duration.count()<< “seconds”<<std::endl;

3.default和delete

C++11引入了default和delete，允许显式声明默认构造函数，析构函数，拷贝构造函数和赋值运算符重载，也可以禁止特定的函数实现

default用于显示的指定编译器生成默认的函数实现

delete用于显示的禁止某个函数

4.列表初始化

形如变量 = {};

int arr[] = {1,2,3};

vector<int> vec = {1,2};

5.shared_ptr底层实现，是否线程安全

shared_ptr的底层实现依赖于引用计数来跟踪共享对象的使用情况。shared_ptr使用一个控制块来存储引用计数和其他元数据。

控制块包含两个引用计数：1.共享计数（shared_count），表示有多少个shared_ptr实例共享同一个对象；2.弱计数（weak count）：表示有多少个weak_ptr实例引用该对象

shared_ptr的内部结构通常包括：1.指向对象的指针，2.指向控制块的指针，3.其他元数据

线程安全性：shard_ptr的引用计数操作是线程安全的，也就是说，当创建一个shared_ptr的对象时，shared_ptr的引用计数的增加是线程安全的，一个shared_ptr的对象销毁时，其引用计数的减少也是线程安全的

但是对于shared_ptr管理的对象却不是线程安全的，当多个线程访问该共享对象时，也是存在资源竞争的问题

6.shared_ptr复制给weak_ptr时内部做了什么

引用控制块：weak_ptr会指向与shared_ptr相同的控制块
增加弱计数：控制块中的weak_count会增加，以表明有一个新的weak_ptr引用了该对象

7.STL容器是线程安全的吗？怎么样在多线程环境下使用容器

大多数STL容器本身不是线程安全的，这意味着在多个线程同时访问同一个STL容器时，如果没有适当的同步机制就会出现资源竞争和未定义行为。

通常，多个线程同时读同一个STL容器是安全的，但是对同一个进行写操作不安全

8.map和unordered_map的区别

map的底层实现是红黑树（自平衡的二叉排序树），元素是按照键值来排序的，支持有序遍历；map的插入，查找，删除的时间复杂度是logn，迭代器在插入和删除后仍然有效；内存方面，map通常使用更多的内存来存储节点，比如父节点，左子节点，右子节点

unordered_map的底层实现是哈希表（哈希映射），元素是无序存储的；unordered_map的查找，插入，删除的平均时间复杂度是O(1)，最坏是O(n)（当哈希冲突过多时）；迭代器在插入和删除后失效；由于使用哈希表，内存使用更加紧凑，但可能会因为哈希表的负载因子而造成更多的内存分配（例如，桶的数量）

9.红黑树和哈希表的复杂度

红黑树的查找，插入删除的时间复杂度都是O(logN)，对于哈希表的查找，插入删除的平均时间复杂度是O(1)，最坏是O(n)

10.哈希表的底层实现，哈希平衡算法

哈希表的底层实现：

数据结构：哈希表是由一个数组和一个哈希函数组成，数组用于存储数据，数组的元素是一个pair，pair存储一个键和对应的值，哈希函数将键（key）映射到数组的索引为止
哈希函数：哈希函数是一个映射函数，将输入键转换成数组的索引，理想的哈希函数应该均匀分布键，避免冲突

哈希表的冲突处理：

冲突：当多个键被映射到同一个索引时会发生冲突

链地址法：每个数组索引维护一个链表，所有哈希到相同索引的元素存储在链表中

开放地址法：在数组内寻找下一个空闲为止来存储冲突的元素；常见的探测方式：1.线性探测，线性的检查下一个位置，2.二次探测，按按二次函数来探测下一个位置，3.双重哈希：使用第二个哈希函数来计算探测步长

哈希平衡算法：

负载因子（Load Factor）：负载因子是元素数量与数组大小的比值，高负载意味着数组较满，增加冲突概率；低负载因子则浪费内存
动态扩容：当负载因子超出阈值时，哈希表会进行扩容。扩容时通常将数组的大小添加到原来的两倍，然后重新计算所有元素的哈希值，重新插入新数组中
动态缩容：当负载因子低于某个阈值，哈希表可能进行缩容，以节省内存，缩容同样需要重新计算所有元素的哈希值并重新插入

桶的基本概念

存储单位：每个桶是哈希表中的一个存储单元，通常是一个数组或链表（或其他容器）。桶的数量通常是哈希表大小的一个参数，它决定了哈希表的容量。
索引：哈希表通过一个哈希函数将键映射到桶的索引位置。这个索引是通过计算键的哈希值并对桶的数量取模（取余）得到的。

11.红黑树有什么好处

红黑树是一种自平衡的二叉搜索树，保证了查找，插入删除的时间复杂度为O(logN)，有效避免了退化成链表的情况。

红黑树广泛用于实现有序容器，如map和set，能够保持元素的有序性

12.Linux的线程调度底层是不是红黑树？

红黑树在Linux的线程调度的使用主要体现在CFS（完全公平调度器）中，主要应用于高效的管理和查找就绪队列中的进程

虚拟运行时间（vruntime）vruntime表示该进程在CPU上的运行时间，而vruntime是通过标准运行时间来调整的，目的是使不同优先级的进程得到公平的CPU时间。CFS通过vruntime来决定哪个进程应当运行
红黑树存储就绪进程就绪队列中的所有进程按照它们的vruntime存储在红黑树中
查找最小vruntime的进程调度器需要快速找到vruntime最小的进程，即红黑树的最左边节点
平衡操作红黑树的平衡操作确保在插入和删除进程的同时，树的高度保持在logn，从而保证了调度的高效性

具体的操作

进程的插入：当一个新进程进入就绪队列时，调度器将其根据vruntime插入到红黑树中
进程删除：当一个进程被调度器选中运行并从就绪队列移出时，调度器从红黑树中删除该进程。
进程选择：调度器通过查找红黑树中vruntime最小的节点来选择下一个要运行的进程

13.vector

1.vector的底层实现

vector是基于动态数组来实现的，它通过动态分配内存和扩展机制来管理内存，存储元素在连续的内存块中。

vector提供高效的随机访问性能，插入和删除操作在末尾最为高效，当在中间进行插入删除操作的效率相对较低

2.vector的默认大小

vector的默认大小为0，不会分配任何内存

3.vector的扩容机制

当容量不足时，按照1.5或者2倍的增长速率来扩展容量，扩容时会分配新内存，复制旧数据到新内存，释放旧内存

4.vector如何释放空间

clear:清空内容，不清空容量

shrink_to_fit：释放多余容量，减少内存的使用

删除元素后，内存不会自动释放，需要手动调用shrink_to_fit才会释放

5.vector避免push_back扩容容器开销的方法

使用resevrve方法预分配足够的容量，可以避免多次插入后的扩容的开销

6.vector的resize和reserve的区别

resize是改变vector的大小，并初始化新元素；如果 new_size 小于当前大小，vector 中的元素会被截断，如果 new_size 大于当前大小，vector 会增加元素，新增的元素会被初始化为指定的值（或默认值）。

reserve 用于改变 vector 的容量（capacity），即为未来的元素分配内存，但不会改变向量的实际大小（size）。

如果 new_capacity 大于当前容量，vector 会分配足够的内存以容纳 new_capacity 个元素，但不会添加任何元素。

如果 new_capacity 小于或等于当前容量，则不会进行任何操作。

7.emplace_back和push_back的区别

emplace_back 用于在 vector 的末尾直接构造一个对象，而不是先创建对象再复制或移动它。接受构造对象所需的参数，而不是对象本身。emplace_back 会直接在 vector 的内存中构造对象，避免了不必要的复制或移动操作，这通常会提高性能，尤其是在对象较大或构造开销较大的情况下。

push_back 用于将一个已存在的对象（或临时对象）添加到 vector 的末尾；如果传入的是一个对象，push_back 会先创建一个对象并将其复制到 vector 中。如果传入的是一个临时对象，可能会涉及到移动构造（C++11 及以后的版本）。

如果你已经有一个对象并想将其添加到 vector 中，使用 push_back。
如果你想在 vector 中直接构造一个新对象，使用 emplace_back。这在处理复杂对象或需要传递多个构造参数时尤其有用。

8.如何优化大量数据的插入

使用reserve方法预先分配足够的内存，避免重新分配和数据移动

批量插入，使用insert进行批量插入，而不是逐个插入，避免内存重新分配次数

9.at和operator[]的区别

at()提供边界检查，如果访问越界会抛出std::out_of_range的异常

[]不提供边界检查

14.迭代器的++it和it++哪个好

++it前置递增效率更高，返回的是增加后的元素；对于大多数迭代器（尤其是基础迭代器，如指针和 STL 容器的迭代器），++it 是更高效的，因为它只需要更新迭代器的状态，并返回更新后的迭代器。

it++后置递增通常需要创建一个临时对象来保存当前的迭代器值，然后在递增后返回这个临时对象。这使得后置递增在某些情况下（尤其是自定义迭代器）可能比前置递增稍慢。

15.vector和list的区别

vector的底层实现是连续的内存块，而list的底层是分散的内存块；vector的数据结构是动态数组，list的数据结构是双向链表

vector的随机访问高效，list的需要遍历，效率低；vector的插入和删除在尾部高效，中间低效，list中间高效，末尾和开头较高效

16.list和deque的区别

list的数据结构是双向链表，deque的数据结构是双端队列，分段式连续内存

list是分散的内存块，deque是分段的连续内存块

list的随机访问低效，deque的随机访问高效

list的中间高效，头尾较高效，deque的末尾和开头高效，中间低效

17.map的插入方式

insertmyMap.insert(std::make_pair(1, “One”)); myMap.insert(std::pair<int, std::string>(2, “Two”));
operator[] std::map<int, std::string> myMap; myMap[1] = “One”; // 插入 myMap[2] = “Two”; // 插入 myMap[3]; // 创建键 3，值为默认值（空字符串）
emplace emplace 方法可以直接在 map 中构造元素，避免了不必要的拷贝或移动操作。 myMap.emplace(1, “One”);
使用 insert_or_assign 方法（C++17 引入）insert_or_assign 方法可以插入一个新的键值对，如果键已存在，则更新其值。 myMap.insert_or_assign(1, “One”);

map的插入，如果键已经存在了，那么就不会插入新元素

18.迭代器失效

vector，deque在插入，删除，扩容后都会失效

map，list在删除元素后，指向该删除元素的迭代器会失效，其他的不会失效

19.STL如何解决哈希冲突的

链地址法是最常见的解决哈希冲突的方法。在这种方法中，每个哈希表的槽（bucket）都存储一个链表（或其他容器），用于存储所有映射到同一个哈希值的元素。当发生哈希冲突时，新的元素会被添加到对应槽的链表中

开放地址法是另一种解决哈希冲突的方法。在这种方法中，当发生冲突时，算法会在哈希表中寻找下一个空槽来存储新元素。常见的开放地址法包括线性探测、二次探测和双重哈希。

为了保持哈希表的性能，当元素数量增加时，哈希表会进行动态扩展。这通常会导致重新计算所有元素的哈希值，并将它们重新分配到新的桶中。这个过程通常在负载因子（load factor）超过一定阈值时触发。

20.priority_queue的底层原理及使用场景

priority_queue是基于堆来实现的，通常使用std::vector来作为底层容器，并通过堆算法（std::make_heap，std::push_heap，std::pop_heap）来维护堆结构

priority_queue适用于快速访问最大或最小的场景，如任务调度，事件驱动的模拟，路径搜索算法

21.何时使用forward_list

forward_list是单向链表，内存占用少，只存储一个指向下一个元素的指针。

适用于内存有限且只需要单向遍历的场景，比如读取大量数据并进行线性处理的操作；在实现某些算法时（例如，合并、分割等），std::forward_list 可以提供更高的性能，尤其是在不需要双向遍历的情况下；在对性能有严格要求的场景中，使用 std::forward_list 可以减少内存分配的开销，因为它的内存使用更为紧凑。

何时不使用 `std::forward_list`

需要双向访问：如果你需要在容器中进行双向遍历或在中间位置插入和删除元素，std::list 或 std::vector 会更合适。
随机访问需求：如果你需要频繁地随机访问元素，std::vector 是更好的选择，因为它支持常数时间的随机访问。

22.stack

底层容器是std::deque，但可以使用其他容器std::vector或list

23.如何优化大量的数据的插入

1. 选择合适的容器

std::vector：
- std::vector 是动态数组，支持快速随机访问和在末尾高效插入。为了优化插入性能，可以在插入大量数据之前使用 reserve 方法预分配足够的内存，避免多次内存分配和拷贝。
std::vector<int> vec; vec.reserve(10000); // 预分配内存 for (int i = 0; i < 10000; ++i) { vec.push_back(i); // 在末尾插入 }
std::deque：
- std::deque 允许在两端高效插入和删除，但随机访问的性能略逊于 std::vector。如果需要频繁地在两端插入，可以考虑使用 std::deque。
std::list 或 std::forward_list：
- 如果需要在容器的中间位置频繁插入和删除元素，std::list 或 std::forward_list 是更合适的选择。它们提供常数时间复杂度的插入和删除操作。

2. 批量插入

使用 insert 方法：
- 对于 std::vector 和 std::list，可以使用 insert 方法一次性插入多个元素。这样可以减少多次调用 push_back 或 push_front 带来的性能开销。
std::vector<int> vec; std::vector<int> new_elements = {1, 2, 3, 4, 5}; vec.insert(vec.end(), new_elements.begin(), new_elements.end());

3.移动语义

使用 std::move：
- 在处理大量数据时，使用移动语义可以避免不必要的拷贝。确保使用 std::move 来转移大型对象的所有权，从而提高性能。
std::vector<string>vec; std::vector<string> new_elements = {“a”, “b”, “c”}; vec.reserve(vec.size() + new_elements.size()); for (auto& elem : new_elements) { vec.push_back(std::move(elem)); // 移动而非拷贝 }

4.避免频繁的内存分配

预分配内存

在插入大量元素之前，使用 reserve（对于 std::vector）或其他相关方法预分配足够的内存，以避免多次内存分配和拷贝。

5.使用合适的算法

使用 STL 算法：STL 提供了许多算法（如 std::copy, std::transform 等），可以高效地处理数据的插入和移动。利用这些算法可以提高性能。

6.考虑并行处理

并行处理

如果你的数据插入操作可以并行化（例如，多个线程可以同时处理不同的数据块），考虑使用 C++17 的并行算法或其他并行库（如 OpenMP、Intel TBB 等）来加速插入过程。

7.选择合适的自定义分配器

自定义分配器：在一些特殊情况下，使用自定义分配器可以优化内存分配的性能，尤其是在处理大量数据时。

24.STL排序算法是如何工作的，他们如何与容器互动？

STL 中的排序算法主要包括：

std::sort
std::stable_sort
std::partial_sort
std::nth_element

`std::sort`

工作原理：std::sort 是一个快速排序算法（通常是基于 introsort），它在平均情况下具有 O(n log n) 的时间复杂度。它会对容器中的元素进行原地排序，即不需要额外的存储空间。通常使用快速排序，堆排序，插入排序的混合算法
使用方法：std::sort 接受两个迭代器作为参数，指定要排序的范围。可以通过提供自定义比较函数来改变排序的顺序。适合vector和deque

`std::stable_sort`

工作原理：std::stable_sort 保持相等元素的相对顺序，通常使用归并排序实现。它的时间复杂度也是 O(n log n)，但由于需要额外的存储空间，性能可能略逊于 std::sort。适用于所有类型的迭代器
使用方法：与 std::sort 类似，std::stable_sort 也接受两个迭代器和一个可选的比较函数。

`std::partial_sort`

工作原理：std::partial_sort 将范围内的前 n 个元素排序，而其余元素不一定有序。适用于只需要前 k 个最小或最大元素的情况。
使用方法：指定要排序的范围和目标元素的数量。

std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());// 排序前3个元素

`std::nth_element`

工作原理：std::nth_element 将范围内的第 n 个元素放到其最终位置，并确保该元素左边的所有元素都小于或等于它，右边的元素都大于或等于它。它的时间复杂度为 O(n)。
使用方法：指定要排序的范围和目标元素的迭代器。

std::nth_element(vec.begin(), vec.begin() + 2, vec.end()); // 找到第3小的元素

25.迭代器和指针的区别

迭代器是对容器访问的抽象，不一定是指针。是STL提供的统一的接口访问不同类型的容器

指针是实际的内存地址表示，适用于数组等简单结构