锐明科技 C++开发-一面 面经

1. 请详细说明I/O多路复用的原理，并对比select、poll和epoll的区别

答案：

I/O多路复用是一种同步I/O模型，允许单个线程监控多个文件描述符，当某个文件描述符就绪时进行相应的读写操作。

三种机制对比：

• select：使用固定大小的位图（通常1024个fd）每次调用需要将fd集合从用户态拷贝到内核态返回后需要遍历所有fd检查哪个就绪，时间复杂度O(n)跨平台性好，但性能较差
• poll：使用链表存储fd，没有数量限制同样需要拷贝fd集合和遍历时间复杂度O(n)解决了select的fd数量限制问题
• epoll（Linux特有）：使用红黑树管理fd，使用事件驱动机制通过epoll_ctl注册fd，无需每次拷贝就绪的fd会被放入就绪队列，只需遍历就绪队列，时间复杂度O(1)支持边缘触发（ET）和水平触发（LT）两种模式适合大量连接但活跃连接较少的场景

2. STL中vector的底层实现机制是什么？扩容策略如何？

答案：

底层实现：

• vector是动态数组，底层使用连续的内存空间存储元素
• 维护三个指针：start（起始位置）、finish（已使用空间的末尾）、end_of_storage（可用空间的末尾）

扩容策略：

• 当插入元素时，如果finish == end_of_storage，触发扩容
• 通常按1.5倍或2倍容量扩容（GCC是2倍，MSVC是1.5倍）
• 扩容步骤： 申请新的更大内存空间将原有元素拷贝/移动到新空间释放旧空间更新三个指针

时间复杂度：

• 随机访问：O(1)
• 尾部插入/删除：均摊O(1)
• 中间插入/删除：O(n)

注意事项：

• 扩容会导致迭代器失效
• 预知大小时应使用reserve()预分配空间，避免多次扩容

3. 在高并发场景下，如何设计缓存系统来降低锁的竞争？

答案：

核心策略：

1. 分段锁（Lock Striping）将缓存分成多个段，每段独立加锁不同段的操作可以并发执行类似ConcurrentHashMap的实现
2. 无锁数据结构使用CAS（Compare-And-Swap）原子操作实现无锁队列、无锁哈希表避免线程阻塞，提高并发性能
3. 读写锁优化使用读写锁（shared_mutex）替代互斥锁多个读操作可以并发执行只有写操作需要独占访问
4. 线程本地缓存（TLS）每个线程维护独立的本地缓存减少跨线程的数据竞争定期同步到全局缓存
5. 延迟更新策略批量更新而非实时更新使用双缓冲技术减少锁的持有时间

实际应用：

• Redis的多线程I/O模型
• Memcached的slab分配器
• 数据库连接池的分段管理

4. 快速排序的核心思想是什么？如何优化其性能？

答案：

基本思想：

• 分治算法，选择一个基准元素（pivot）
• 将数组分为两部分：小于pivot和大于pivot
• 递归地对两部分进行排序

算法步骤：

1. 选择基准元素（通常选第一个、最后一个或中间元素）
2. 分区操作：将小于pivot的放左边，大于的放右边
3. 递归处理左右两个子数组
4. 递归终止条件：子数组长度为1或0

时间复杂度：

• 平均：O(n log n)
• 最坏：O(n²)（数组已排序或逆序时）
• 最好：O(n log n)

优化策略：

1. 三数取中法选择pivot取首、尾、中间三个元素的中位数作为pivot避免最坏情况
2. 小数组使用插入排序当子数组长度小于阈值（如10）时，使用插入排序减少递归开销
3. 三路快排将数组分为小于、等于、大于pivot三部分处理大量重复元素时效率更高
4. 尾递归优化先处理