皮皮网

1.STL源码剖析9-set、码剖multiset
2.STL源码剖析总结笔记（2）：容器（containers）概览
3.STL源码剖析总结笔记（3）：vector初识
4.STL 源码剖析：sort
5.STL源码剖析总结笔记（5）：认识迭代器的析简好帮手--list

STL源码剖析9-set、multiset

       STL源码剖析-set、体中multiset

       在深入探讨STL源码时，文完set与multiset是整版关键组件，它们皆基于红黑树实现。码剖饮料公司源码这些数据结构设计旨在高效处理有序集合。析简set类及其内部rb tree模板参数identity，体中定义在stl_function.h文件中，文完是整版仿函数的一种实现。这表明set类能够灵活地根据用户自定义的码剖比较规则来组织数据，从而提供强大的析简灵活性。

       具体而言，体中stl_set.h文件中定义了set类，文完它封装了红黑树结构，整版用于存储无重复元素的集合。借助rb tree的特性，set能够保证插入、删除、查找等操作的时间复杂度为O(log n)。而identity参数的选择，使得用户能基于不同的比较逻辑自定义元素间的相对顺序，适应多种应用场景。

       多集类multiset则是在set的基础上扩展而来的，它允许集合中元素重复出现。这种设计使得multiset在需要存储有重复元素的有序集合时更为适用。与set类似，multiset同样基于红黑树实现，但其模板参数identity的用法与set相同，依然定义在stl_function.h中，以便实现自定义的random库源码比较逻辑。

       在stl_multiset.h文件中，可找到multiset类的定义。它继承自set，并通过增加对重复元素的支持，为用户提供了一个更灵活的数据结构选择。通过灵活运用multiset，开发人员能够轻松实现需要频繁插入、删除重复元素的有序集合，同时保持高效的操作性能。

       总结而言，set与multiset作为STL中的重要组件，分别针对无重复元素与允许重复元素的有序集合提供高效实现。通过自定义比较逻辑与红黑树结构的结合，它们不仅保证了数据的有序性，还提供了高效的操作性能，成为众多应用程序中不可或缺的数据结构。

STL源码剖析总结笔记（2）：容器（containers）概览

       容器作为STL的重要组成部分，其使用极大地提升了解决问题的效率。深入研究容器内部结构与实现方式，对提升编程技能至关重要。本文将对容器进行概览，分为序列式容器、关联式容器与无序容器三大类。

       容器大致分为序列式容器、关联式容器和无序容器。其中序列式容器侧重于顺序存储，关联式容器则强调元素间的键值关系，而无序容器可以看作关联式容器的一种。

       容器之间的关系可以归纳为：序列式容器为基层，关联式容器则在基层基础上构建了更复杂的枫叶辅助源码数据结构。例如，heap和priority容器以vector作为底层支持，而set和map则采用红黑树作为基础数据结构。此外，还存在一些非标准容器，如slist和以hash开头的容器。在C++ 中，slist更名为了forward-list，而hash开头的容器改名为了unordered开头。

       在容器的实现中，sizeof()函数可能揭示容器的内部大小对比。需要注意的是，尽管在GNU 4.9版本中，一些容器的设计变得复杂，采用了较多的继承结构，但实际上，这些设计在功能上并未带来太大差异。

       熟悉容器的结构后，我们可以从vector入手，探索其内部实现细节。其他容器同样蕴含丰富的学习内容，如在list中，迭代器（iterators）的设计体现了编程的精妙之处；而在set和map中，红黑树的实现展现了数据结构的高效管理。

       本文对容器进行了概览，旨在提供一个全面的视角，后续将对vector、list、set、map等容器进行详细分析，副业卖源码揭示其背后的实现机制与设计原理。

STL源码剖析总结笔记（3）：vector初识

       vector是c++中常用且重要的容器之一。相较于固定大小的array，vector拥有动态分配内存的特性，允许它在使用过程中随着元素的增删而自行调整大小。这种动态性使得vector在处理不可预知数据量时更为便捷。

       内部结构上，vector使用了数组作为存储基础，并通过start, finish和end of storage三个迭代器进行访问和管理空间。其中，start和finish分别指向可用空间的首端和尾端，end of storage则指向内存块的末尾。在vector大小为字节（位系统下，一个指针占4字节）的情况下，其大小为3。因此，vector可以灵活地通过迭代器定位数据的大小与位置。

       内存管理机制是vector的精华之一。当空间耗尽时，vector会自动扩展为二倍的内存容量，以容纳新增元素。此过程涉及创建新空间，复制原有数据，然后释放旧空间，确保资源的有效利用。

       vector提供了丰富的迭代器，遵循随机访问的行为，允许直接获取和修改数据，增强操作的效率。这些迭代器简化了对数据结构的溯源码测试遍历与修改操作。

       在添加与删除数据时，vector提供了pop_back(), erase, insert等高效方法。例如，pop_back()简单地删除尾部元素，erase允许清除一个范围内的数据，并通过复制来维持数据的连续性。insert操作根据具体需求进行数据的插入与调整，确保结构的完整性与数据的正确性。

       综上，vector以其灵活的内存管理和高效的数据操作，成为学习STL和掌握容器结构的理想选择。其清晰的内部机制和丰富的功能特性，为程序设计提供了强大的支持。

STL 源码剖析：sort

       我大抵是太闲了。

       更好的阅读体验。

       sort 作为最常用的 STL 之一，大多数人对于其了解仅限于快速排序。

       听说其内部实现还包括插入排序和堆排序，于是很好奇，决定通过源代码一探究竟。

       个人习惯使用 DEV-C++，不知道其他的编译器会不会有所不同，现阶段也不是很关心。

       这个文章并不是析完之后的总结，而是边剖边写。不免有个人的猜测。而且由于本人英语极其差劲，大抵会犯一些憨憨错误。

       源码部分sort

       首先，在 Dev 中输入以下代码：

       然后按住 ctrl，鼠标左键sort，就可以跳转到头文件 stl_algo.h，并可以看到这个：

       注释、模板和函数参数不再解释，我们需要关注的是函数体。

       但是，中间那一段没看懂……

       点进去，是一堆看不懂的#define。

       查了一下，感觉这东西不是我这个菜鸡能掌握的。

       有兴趣的 戳这里。

       那么接下来，就应该去到函数__sort 来一探究竟了。

       __sort

       通过同样的方法，继续在stl_algo.h 里找到 __sort 的源代码。

       同样，只看函数体部分。

       一般来说，sort(a,a+n) 是对于区间 [公式] 进行排序，所以排序的前提是 __first != __last。

       如果能排序，那么通过两种方式：

       一部分一部分的看。

       __introsort_loop

       最上边注释的翻译：这是排序例程的帮助程序函数。

       在传参时，除了首尾迭代器和排序方式，还传了一个std::__lg(__last - __first) * 2，对应 __depth_limit。

       while 表示，当区间长度太小时，不进行排序。

       _S_threshold 是一个由 enum 定义的数，好像是叫枚举类型。

       当__depth_limit 为 [公式] 时，也就是迭代次数较多时，不使用 __introsort_loop，而是使用 __partial_sort（部分排序）。

       然后通过__unguarded_partition_pivot，得到一个奇怪的位置（这个函数的翻译是无防护分区枢轴）。

       然后递归处理这个奇怪的位置到末位置，再更新末位置，继续循环。

       鉴于本人比较好奇无防护分区枢轴是什么，于是先看的__unguarded_partition_pivot。

       __unguarded_partition_pivot

       首先，找到了中间点。

       然后__move_median_to_first（把中间的数移到第一位）。

       最后返回__unguarded_partition。

       __move_median_to_first

       这里的中间数，并不是数列的中间数，而是三个迭代器的中间值。

       这三个迭代器分别指向：第二个数，中间的数，最后一个数。

       至于为什么取中间的数，暂时还不是很清楚。

       `__unguarded_partition`

       传参传来的序列第二位到最后。

       看着看着，我好像悟了。

       这里应该就是实现快速排序的部分。

       上边的__move_median_to_first 是为了防止特殊数据卡 [公式] 。经过移动的话，第一个位置就不会是最小值，放在左半序列的数也就不会为 [公式] 。

       这样的话，__unguarded_partition 就是快排的主体。

       那么，接下来该去看部分排序了。

       __partial_sort

       这里浅显的理解为堆排序，至于具体实现，在stl_heap.h 里，不属于我们的讨论范围。

       （绝对不是因为我懒。）

       这样的话，__introsort_loop 就结束了。下一步就要回到 __sort。

       __final_insertion_sort

       其中某常量为enum { _S_threshold = };。

       其中实现的函数有两个：

       __insertion_sort

       其中的__comp 依然按照默认排序方式 < 来理解。

       _GLIBCXX_MOVE_BACKWARD3

       进入到_GLIBCXX_MOVE_BACKWARD3，是一个神奇的 #define：

       其上就是move_backward：

       上边的注释翻译为：

       __unguarded_linear_insert

       翻译为“无防护线性插入”，应该是指直接插入吧。

       当__last 的值比前边元素的值小的时候，就一直进行交换，最后把 __last 放到对应的位置。

       __unguarded_insertion_sort

       就是直接对区间的每个元素进行插入。

       总结

       到这里，sort 的源代码就剖完了（除了堆的那部分）。

       虽然没怎么看懂，但也理解了，sort 的源码是在快排的基础上，通过堆排序和插入排序来维护时间复杂度的稳定，不至于退化为 [公式] 。

       鬼知道我写这么多是为了干嘛……

STL源码剖析总结笔记（5）：认识迭代器的好帮手--list

       在深入探讨STL中的`list`容器之前，我们先简要回顾了`vector`的特性以及分配器（`allocator`）的作用。接下来，我们将转向一个具有代表性的容器——`list`。之所以说其具有代表性，是因为`list`利用非连续的空间存储元素，从而在空间利用上更为精确。学习`list`是掌握迭代器机制的第一步。

       “list”实质上是双向链表，它具有两个重要特性：前向指针和后向指针。在STL中，`list`节点的定义可能使用`_list_node*`（可能为了兼容性或设计规范）来指代节点结构，其中包含了指向下一个节点和上一个节点的指针。

       `list`的内部实现为一个环状的双向链表结构，通过一个指向虚拟尾节点的指针`node`来方便遍历。`begin()`和`end()`方法的实现依赖于这个`node`。此外，`empty()`、`size()`、`front()`（访问头节点内容）、`back()`（访问尾节点内容）等方法的实现相对直截了当。

       `list`的迭代器（`iterator`）设计得更为复杂，因为非连续的空间分配使得简单指针的操作无法直接使用。迭代器需要智能地追踪当前节点及其前后的节点，以便进行递增、递减和取值操作。这要求迭代器实现诸如`++`和`--`等操作符的重载，同时还需要定义至少1-5个`typedef`类型来支持迭代器的基本行为。

       `++`操作符的重载遵循前置`++`和后置`++`的区别：前置`++`直接返回计算后的结果（即更新后的迭代器），而后置`++`返回迭代器的副本，避免了在C++中直接对整数进行两次后置`++`的操作，因为这会导致未定义的行为。`*`和`->`操作符用于访问当前节点的数据和成员，后者通过`*`操作符访问节点数据后再通过指针访问成员，确保了数据的安全访问。

       `list`的基本操作主要依赖于节点指针的移动和修改，如插入、删除等。这些操作通常需要考虑双向链表的特性以及虚拟尾节点的存在，以避免丢失数据或产生无效指针。例如，`transfer()`方法是一个关键功能，允许将一段连续范围的元素移动到链表中的特定位置，这是许多其他复杂操作的基础。

       在`list`中，`transfer()`方法实现了将`[first,last)`范围内的元素移动到指定位置的逻辑，通过调整节点的`next`和`prev`指针来完成移动，同时确保了数据的完整性。基于`transfer()`方法，其他高级操作也能够实现，尽管这些操作通常不直接暴露给用户，而是通过封装在`list`内部的实现来提供。

       学习`list`不仅有助于理解迭代器的设计原理，也为探索其他容器（如`vector`和`deque`）的实现提供了基础。在接下来的内容中，我们将详细探讨迭代器的实现技巧，以及如何在实际编程中利用这些概念来优化代码。