哈喽,各位好!今天我们要一起手搓一个简化版的红黑树std::map,保证大家听完之后,感觉自己也能去写STL了(当然,只是感觉)。 首先,我们要明确目标:我们需要一个类似std::map的东西,它能存储键值对,并且能高效地查找、插入和删除。红黑树就是实现这个目标的绝佳选择,因为它能在最坏情况下保证O(log n)的时间复杂度。 一、红黑树的基础知识:不怕,我用人话讲给你听 红黑树,听起来很高大上,其实就是一种特殊的二叉搜索树。为了保持平衡,它给自己加了一些限制(或者说规则): 每个节点要么是红色,要么是黑色。 就像交通信号灯,非红即黑,简单粗暴。 根节点是黑色。 树的根基一定要稳,所以必须是黑色的。 每个叶子节点(NIL节点,空节点)是黑色。 这些叶子节点其实就是nullptr,也是黑色的。 如果一个节点是红色,那么它的两个子节点都是黑色。 红色节点不能连在一起,不然就乱套了。想象一下红色的多米诺骨牌不能连续摆放。 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点。 这条规则保证了树的平衡性。我们把这个黑色节点的数量叫做“黑高”。 这些规则确保了红黑树不 …
C++ 从零开始实现一个简化版 `std::vector`:深入内存管理
哈喽,各位好!今天我们来一起手撸一个简化版的 std::vector,重点放在内存管理上,保证让你彻底理解 C++ 里面的动态数组是怎么回事儿。 啥是 std::vector? 简单来说,std::vector 就是一个可以自动增长的数组。你不用一开始就确定它的大小,可以随时往里面添加元素,它会自动帮你分配和释放内存。这玩意儿在 C++ 里简直是神器,用得不要太频繁。 为啥要自己实现? 直接用 std::vector 不香吗?香!但是,想要真正理解它的工作原理,特别是内存管理那一块,最好的办法就是自己动手实现一个简化版。这样你才能知道 std::vector 背后都做了些什么,以后遇到内存相关的问题也能更快地定位。 我们简化版的目标 动态增长: 可以像 std::vector 一样,动态地添加元素。 基本操作: 实现 push_back(添加元素到末尾)、size(获取元素个数)、capacity(获取容量)、operator[](下标访问)等基本操作。 内存管理: 重点关注内存的分配、释放和重新分配。 异常安全: 尽量保证在出现异常时,不会导致内存泄漏或者数据损坏。 开始撸代码! 首 …