MyTinySTL

为什么选择实现一个简化版STL？

STL是C++标准库的核心，但底层实现复杂且抽象。通过实现MyTinySTL，可以深入理解容器、迭代器、内存分配器等核心组件的设计原理，也能让我更好地理解C++ 项目

细说你对STL 的深入理解

如何实现vector的动态扩容？

回答：vector底层是动态数组，当size超过capacity时会触发扩容。MyTinySTL采用2倍扩容策略（标准库可能为1.5倍），通过new申请新内存，拷贝原有数据，释放旧内存。扩容时迭代器会失效，因为元素地址发生变化

红黑树在map中的应用及优势？

回答：红黑树是自平衡二叉搜索树，保证插入、删除、查找的时间复杂度为O(log n)。在map中还需要对键进行排序，键值对按红黑树规则排序，支持有序遍历。相比哈希表（unordered_map），红黑树在频繁插入删除时更稳定，无需处理哈希冲突

如何处理迭代器失效问题？

回答：以vector为例，插入或删除元素可能导致迭代器失效。例如，push_back触发扩容时，所有迭代器、指针、引用失效；erase删除元素后，被删除位置之后的迭代器失效。解决方案是使用erase返回的合法迭代器继续操作

如何测试容器性能？

回答：通过单元测试框架（如TestCase和UnitTest类）验证功能正确性；性能测试可通过插入大量数据（如1000万元素）对比标准库耗时。例如，vector插入耗时129ms（标准库210ms），体现了内存预分配和减少系统调用的优化

如何优化哈希表（unordered_map）的性能？

回答：采用链地址法解决哈希冲突，结合负载因子（如0.75）触发扩容。优化点包括：
使用质数作为桶数量，减少哈希聚集。
局部缓存哈希值，避免重复计算

如果被问到未实现的细节（如deque的迭代器设计）？

回答：这个部分我不太了解，但基于STL原理，deque采用分段连续空间（多个缓冲区+中控数组），迭代器需记录当前段位置和边界。可引用《STL源码剖析》中的设计思路

从项目中学到的最重要的技术点？

回答：

• 模板元编程：通过type_traits实现类型萃取，优化算法对不同数据类型的适配。
• 内存管理：理解内存池和自由链表如何减少碎片，提升小对象分配效率。
• 迭代器设计：将容器与算法解耦，通过迭代器泛化访问逻辑

MyTinySTL与标准STL的主要区别是什么？

回答：它其实是标准库的简化版，然后因为我不用考虑兼容性，比如说操作系统的和编译器的兼容性，就避免了一些不必要的代码

然后我能够针对特定场景选择合适的策略，因此这个简化版的效率在部分场景会略高于标准库

细说你针对哪些特殊场景做出了改变，对效率提高了多少

内存分配策略：

两级分配器：一级直接调用malloc处理大块内存，二级采用内存池管理小块内存（16个自由链表，管理8-128字节），减少内存碎片和系统调用次数 。
标准库的 new/delete 会产生内存碎片并增加系统调用开销。

stack 容器

• 我定义了两个参数，分别是指定初始大小和初始值
• 在初始化stack时可传入
• 标准STL呢，它需要先构造临时容器【通过deque】，再移动构造

std::deque<int> temp(100, 42); // 显式构造临时容器
std::stack<int> s(std::move(temp)); // 移动构造

对于数据排序算法

小规模数据用快速排序【例如size小于10000】
大规模数据使用归并排序，减少内存访问

标准 STL 对比：
sort（通常是内省排序）在处理大数据时可能有较多随机内存访问。

内存泄漏检测

特殊场景：检测内存泄漏和重复释放问题。
标准 STL 对比：
标准库未提供内置内存泄漏检测。【可以用智能指针避免泄漏】

MyTinySTL 的跟踪所有内存分配【比如说通过这个计数法，构造的时候加1，析构的时候减1】，程序结束时可报告未释放的内存块。