Qliphoth's Blog

前言 二叉搜索树具有对数平均时间（logarithmic average time）的表现，但这样的表现构造在一个假设上：输入数据有足够的随机性。而 hashtable （散列表）在插人、删除、查找等操作上具有 “常数平均时间” 的表现，且这种表现是以统计为基础，不需仰赖输入元素的随机性。 ———— 《STL源码剖析》侯捷 本节将会介绍关于 hashtable 的一些基本概念。 本节内容主要参考自：Hello Algo：哈希表 hashtable 的基本概念 「哈希表 hash table」，又称「散列表」，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询。 我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为「桶 bucket」，每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。 那么，如何基于 key 来定位对应的桶呢？这是通过「哈希函数 hash function」实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ， ...

前言 最近打算用 C++ 再刷一刷力扣，但看了一些题的官方解答居然发现很多 C++ 的语法都看不懂，因此准备陆续将 C++ 中一些之前没有怎么学的知识点记录一下。 lambda lambda 的定义 c++ 在 c++11 标准中引入了 lambda 表达式，一般用于定义匿名函数，使得代码更加灵活简洁。 一个 lambda 表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个 lambda 具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda 可能定义在函数内部。一个 lambda 表达式具有如下形式： 1[ capture list ] (parameter list) -> return type { function body } 其中，capture list（捕获列表）是一个 lambda 所在函数中定义的局部变量的列表（通常为空）；return type、parameter list 和 function body 与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同 ...

前言 前面花了很多篇幅介绍红黑树的原理及其在 STL 中的实现。在 STL 中，红黑树不作为一种容器对外开放，而是作为 set 以及 map 的底层容器而使用，本节就将依次介绍它们。 set set 的特性是，所有元素都会根据元素的键值自动被排序。set 的元素不像 map 那样可以同时拥有实值（value）和键值（key），set元素的键值就是实值，实值就是键值。set不允许两个元素有相同的键值。 由于 set 的元素值就是其键值，关系到 set 元素的排列规则，因此 set<T>::iterator 被定义为底层 RB-tree 的 const_iterator，杜绝写入操作。 STL 特别提供了一组 set/multiset 相关算法，包括交集 set_intersection 、联集 set_union、差集 set_difference 、对称差集set_synmetric_difference，会在介绍到算法部分时再做介绍。 由于 RB-tree 是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的 STLset 即以 RB-tree 为底层机制。又由于 se ...

前言 红黑树性质： 节点是红色或黑色。 根是黑色。 所有叶子都是黑色（叶子是 NIL 节点）。 每个红色节点必须有两个黑色的子节点。 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 连一刻都没有为国庆假期悼念，立刻赶来战场的是 ———— 长达七天的调休。而我们也将继续 STL 的旅程，本节将要分析的是 STL 红黑树的构造以及对外接口的实现。 rb-tree 的构造与内存管理 红黑树的构造与析构函数如下： 12345678910public: // 构造、复制、析构函数 rb_tree() { rb_tree_init(); } rb_tree(const rb_tree& rhs); rb_tree(rb_tree&& rhs) noexcept; rb_tree& operator=(const rb_tree& rhs); rb_tree& operator=(rb_tree&& rhs) noexcept; ~rb_tree() &# ...

记录一个 MPTPS 项目的完成过程

前言 红黑树性质： 节点是红色或黑色。 根是黑色。 所有叶子都是黑色（叶子是 NIL 节点）。 每个红色节点必须有两个黑色的子节点。 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 对于红黑树而言，最重要的算法就是如何插入与删除一个节点，而这两个操作又需要大量用到树的左旋与右旋。因此本节主要分析这些算法的实现。这部分建议结合 红黑树寄录 中的内容一起看，会有助于理解。 红黑树算法 常用的辅助函数 以下列出红黑树算法中经常要使用的一些简单函数。 123456789101112131415161718192021222324252627282930313233343536373839404142434445/// @brief 查找最小节点template <class NodePtr>NodePtr rb_tree_min(NodePtr x) noexcept { while (x->left != nullptr) x = x->left; return x;}/// @brief 查找最大节点templ ...

前言 红黑树性质： 节点是红色或黑色。 根是黑色。 所有叶子都是黑色（叶子是 NIL 节点）。 每个红色节点必须有两个黑色的子节点。 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。 规则类怪谈既视感 从本节开始，将会持续分析 STL 中的红黑树实现，在按照 MyTinySTL 的版本实现了一遍，再看完 STL 源码剖析以及 STL 源码后，感觉这三者的实现都各有不同，而且红黑树太过繁杂，因此这部分的分析有些可能会与 STL 中的实现差别较大。 但博主认为，红黑树这里主要还是理解它的结构与各种操作，简而言之，就是理解 红黑树寄录 这里的内容，虽然是用 python 写的，但也算是完整地实现了红黑树，至于 STL 的话，无非就是在此基础上做了与整个 STL 框架的兼容而已，如 traits、iterator 等，理解思想就好，没必要死磕源码。 本节将会分析红黑树的节点及迭代器的结构设计。 rb-tree 的节点设计 rb-tree 的节点结构分为两层，将节点与数据分开定义，rb_tree_node_base定义指针；rb_tree_node继承前者，增加了数据，就是 ...

记录一个 MPTPS 项目的完成过程

继续被 C++ 折磨

记录一个 MPTPS 项目的完成过程

记录一个 MPTPS 项目的完成过程

前言 经历了相当漫长的历程，终于将 STL 的序列式容器基本分析完毕，接下来将进入关联式容器的分析。相比于序列式容器，关联式容器中真正需要实现的底层容器更少，仅有两个。但是，但是，这两位可都是重量级：红黑树与哈希表。它们的复杂程度要远超之前的 vector、list 以及 deque，并且红黑树不仅复杂还让人及其费解，用一个词来形容就是又臭又长，理解与实现起来都十分困难。但这已经是我们实现 STL 之路上的倒数第二个阻碍了，翻过这座山，我们就是冠军。 标准的 STL 关联式容器分为 set（集合）和map（映射表）两大类，以及这两大类的衍生体 multiset（多键集合）和 multimap（多键映射表）。这些容器的底层机制均以 RB-tree （红黑树）完成。RB-tree 也是一个独立容器，但并不开放给外界使用。 此外，SGI STL 还提供了一个不在标准规格之列的关联式容器: hash table（散列表），以及以此 hashtable 为底层机制而完成的 hash_set（散列集合）、hash_map（散列映射表）、hash_multiset（散列多键集合）、hash_mul ...

继续被 C++ 折磨

继续被 C++ 折磨

前言 priority_queue 是一个优先级队列，是带权值的。支持插入和删除操作，其只能从尾部插入，头部删除，并且其顺序也并非是根据加入的顺序排列的。priority_queue 因为也是队列的一种体现，所以也就跟队列一样不能直接的遍历数组，也就没有迭代器。priority_queue 本身也不算是一个容器，它是以 vector 为容器以 heap 为数据操作的 container adapter。 priority_queue 由于前置知识点 vector 与 heap 都已经梳理过，priority_queue 只是做了一层封装，比较简单，因此这里直接列出代码。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061 ...