C++日更八股--day2

### C++ sort 的底层原理
这里其实原来问的是你如何优化快速排序，但是我最初只以为是随机选择基准，但是很显然面试官对此并不满意
闲暇之际，看到一篇介绍sort的原理的文章，才知道原来如是也
1.快速排序：作为主要算法，它通过选择一个pivot元素，将序列划分为两个子序列，一个子序列元素小于枢轴，另一个大于，随后递归排序，时间复杂度达到O(nlogn).
2.堆排序：为了避免快速排序在最坏情况下O(n^2)的最坏情况，当快速排序递归深度超过一定限制的时候，sort迅速切换到堆排序
3.插入排序：当处理小规模的子序列的时候，使用插入排序的性能更好

### 请介绍一下epoll，poll，select
select、poll 和 epoll 是三种Linux下实现 ​​I/O 多路复用
I/O多路复用指的是用一个线程监控多个文件描述符的动态变化
select（相当于逐个点名）：每次调用，都需要告知内核需要监控哪些文件描述符，内核进行标记，然后返回就绪的数量，用户自己还需要再遍历一次
poll（改进版逐一点名）：相对于select使用vector来存储监控的文件描述符，使得容量无限制
epoll（事件通知）：当有文件描述符需要服务的时候，才会通知，且返回的为需要服务的文件描述符，避免遍历
这里肯定就会有朋友问了，有了epoll还要poll干嘛：为了非Linux下使用

这里补充一下loop，绑定器和回调函数
loop：事件循环：​​事件循环​​是一个持续运行的循环结构，负责监听和分发事件。它通过 ​​非阻塞​​ 的方式处理多个任务，避免因等待某个操作（如文件读取）而阻塞整个程序。
  一般流程为循环开始 → 检查是否有事件 → 处理事件 → 等待新事件 → 循环继续
  note：上述三种select等是用于监听，后面这些是处理这些事件的流程
绑定器：绑定器​​用于将一个函数与特定的参数或上下文绑定，生成一个新的函数。通过占位符给函数一个固定的参数
回调函数：允许程序在等待耗时操作时不阻塞主线程。当某一事件发生时进行调用，

### 迭代器失效的场景
vector，这个容器为动态数组，相信学过操作系统分区分配的朋友一定知道，我如果在连续的存储空间中扩容的做法为再找一片空间，当前内容复制过去，再插入
那么由于迭代器（类似于指针），你地址都变了，我肯定失效了
deque（双端队列）：底层为分段连续的数组，插入会导致全部迭代器失效，规则复杂，这里不做赘述，自行了解
map/set/multimap/multiset：底层是红黑树，后面我会在数据结构章节介绍这种结构，插入删除不会失效
unordered_map/unordered_set（哈希表）：插入如果导致扩容，迭代器失效
note：删除操作肯定会导致当前迭代器失效，这很容易理解