1.[stl 源码分析] std::list::size 时间复杂度
2.[stl 源码分析] std::sort
3.STL源码学习（3）- vector详解
4.STL源码剖析总结笔记（5）：认识迭代器的码设好帮手--list
5.STL 源码剖析：sort
6.STL源码剖析总结笔记（2）：容器（containers）概览
[stl 源码分析] std::list::size 时间复杂度
在对Linux上C++项目进行性能压测时，一个意外的码设发现是std::list::size方法的时间复杂度并非预期的高效。原来，码设这个接口在较低版本的码设g++（如4.8.2）中是通过循环遍历整个列表来计算大小的，这导致了明显的码设性能瓶颈。@NagiS的码设拼多多免费助力工具源码提示揭示了这个问题可能与g++版本有关。
在功能测试阶段，码设CPU负载始终居高不下，码设通过火焰图分析，码设std::list::size的码设调用占据了大部分执行时间。火焰图的码设使用帮助我们深入了解了这一问题。
查阅相关测试源码（源自cplusplus.com），码设在较低版本的码设g++中，std::list通过逐个节点遍历来获取列表长度，码设这种操作无疑增加了时间复杂度。码设然而，对于更新的g++版本（如9），如_glibcxx_USE_CXX_ABI宏启用后，list的实现进行了优化。它不再依赖遍历，而是利用成员变量_M_size直接存储列表大小，从而将获取大小的时间复杂度提升到了[公式]，显著提高了性能。具体实现细节可在github上找到，如在/usr/include/c++/9/bits/目录下的代码。
[stl 源码分析] std::sort
std::sort在标准库中是一个经典的复合排序算法，结合了插入排序、快速排序、堆排序的优点。该算法在排序时根据几种算法的优缺点进行整合，形成一种被称为内省排序的高效排序方法。
内省排序结合了快速排序和堆排序的优点，快速排序在大部分情况下具有较高的效率，堆排序在最坏情况下仍能保持良好的性能。内省排序在排序过程中，先用快速排序进行大体排序，然后递归地对未排序部分进行更细粒度的排序，直至完成整个排序过程。在快速排序效率较低时，内省排序会自动切换至插入排序，以提高排序效率。TURN服务源码
在实现上，std::sort使用了内省排序算法，并在适当条件下切换至插入排序以优化性能。其源码包括排序逻辑的实现和测试案例。排序源码主要由内省排序和插入排序两部分组成。
内省排序在排序过程中先快速排序，然后对未完全排序的元素进行递归快速排序。当子数组的长度小于某个阈值时，内省排序会自动切换至插入排序。插入排序在小规模数据中具有较高的效率，因此在内省排序中作为优化部分，提高了整个排序算法的性能。
插入排序在排序过程中，将新元素插入已排序部分的正确位置。这种简单而直观的算法在小型数据集或接近排序状态的数据中表现出色。内省排序通过将插入排序应用于小规模数据，进一步优化了排序算法的性能。
综上所述，std::sort通过结合内省排序和插入排序，实现了高效且稳定的数据排序。内省排序在大部分情况下提供高性能排序，而在数据规模较小或接近排序状态时，插入排序作为优化部分，进一步提高了排序效率。这种复合排序方法使得std::sort成为标准库中一个强大且灵活的排序工具。
STL源码学习（3）- vector详解
STL源码学习（3）- vector详解
vector的迭代器与数据类型：vector内部的连续存储结构使得任何类型的数据指针都可以作为其迭代器。通过迭代器，可以执行诸如指针操作，如访问元素值。 vector定义了两个迭代器start和finish，分别指向元素的起始和终止地址，同时还有一个end_of_storage标记空间的结束位置。vector的容量保证大于等于已分配元素空间，提供了获取空间大小的函数，如front和back的值以引用返回，更高效。 空间配置原理：STL中的vector使用SGI STL容器的二级空间配置器。vector头部包含配置信息，如data_allocator作为空间配置器的别名。简单配置器（simple_alloc）是ps 各种源码封装了高级和低级配置器调用的抽象类。 构造函数与内存管理：vector通过空间配置器创建元素。构造函数允许预分配并初始化元素，fill_initialize用于调整空间范围，allocate_and_fill则分配空间并填充。这个过程涉及data_allocator的allocate函数，分配空间并返回起始地址。 vector析构时，调用deallocate函数释放空间。pop_back和erase方法会移除元素并销毁相应空间，clear则清除全部元素。insert操作复杂，根据元素数量和容器状态可能需要扩容。 插入与扩展操作：push_back在末尾插入元素，如果空间不足，可能需要扩容。insert接受三个参数，根据情况处理插入操作，可能抛出异常并销毁部分元素。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`的open支付源码迭代器（`iterator`）设计得更为复杂，因为非连续的空间分配使得简单指针的操作无法直接使用。迭代器需要智能地追踪当前节点及其前后的节点，以便进行递增、递减和取值操作。这要求迭代器实现诸如`++`和`--`等操作符的重载，同时还需要定义至少1-5个`typedef`类型来支持迭代器的基本行为。
`++`操作符的重载遵循前置`++`和后置`++`的区别：前置`++`直接返回计算后的结果（即更新后的迭代器），而后置`++`返回迭代器的副本，避免了在C++中直接对整数进行两次后置`++`的操作，因为这会导致未定义的行为。`*`和`->`操作符用于访问当前节点的数据和成员，后者通过`*`操作符访问节点数据后再通过指针访问成员，确保了数据的安全访问。
`list`的基本操作主要依赖于节点指针的移动和修改，如插入、删除等。这些操作通常需要考虑双向链表的特性以及虚拟尾节点的存在，以避免丢失数据或产生无效指针。例如，`transfer()`方法是一个关键功能，允许将一段连续范围的元素移动到链表中的特定位置，这是许多其他复杂操作的基础。
在`list`中，`transfer()`方法实现了将`[first,last)`范围内的元素移动到指定位置的逻辑，通过调整节点的`next`和`prev`指针来完成移动，同时确保了数据的完整性。基于`transfer()`方法，其他高级操作也能够实现，尽管这些操作通常不直接暴露给用户，而是通过封装在`list`内部的实现来提供。
学习`list`不仅有助于理解迭代器的设计原理，也为探索其他容器（如`vector`和`deque`）的实现提供了基础。在接下来的内容中，我们将详细探讨迭代器的实现技巧，以及如何在实际编程中利用这些概念来优化代码。
STL 源码剖析：sort
我大抵是太闲了。
更好的阅读体验。
sort 作为最常用的 STL 之一，大多数人对于其了解仅限于快速排序。
听说其内部实现还包括插入排序和堆排序，formmaking源码解析于是很好奇，决定通过源代码一探究竟。
个人习惯使用 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源码剖析总结笔记（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源码剖析9-set、multiset
STL源码深入研究：set与multiset的内部结构详解
1. 结论
在C++标准模板库(STL)中，set和multiset是两种常用的数据结构，它们底层实现依赖于红黑树（rb tree）。set是一种无序的关联容器，不允许有重复元素，而multiset则允许元素重复，但仍然保持插入顺序。
2. set的实现
set内部的红黑树使用了stl_function.h中的仿函数模板参数，这个仿函数用于定义元素的比较规则。set类在stl_set.h文件中定义，它通过这个仿函数确保了元素的唯一性，保证了查找、插入和删除操作的高效性。
3. multiset的特性
与set不同，multiset在stl_multiset.h中定义，它允许元素重复，这主要通过维护每个元素在树中的多个实例来实现。与set一样，它也依赖红黑树的数据结构，但对元素的比较规则更为宽松，允许基于给定的比较仿函数进行重复元素的插入和查找。
从应用到源码理解STL反向迭代器
在实际应用中，我们可能需要从序列容器（如vector）的尾部移除不满足特定条件的部分元素。这通常涉及从尾部开始的迭代操作。然而，容器成员函数erase不接受反向迭代器作为参数。因此，我们需要将反向迭代器转换为普通迭代器。先来看看STL迭代器的分类和转换关系。
STL迭代器主要分为用途迭代器，它们之间存在转换关系，但不是所有迭代器类型都可以相互转换。转换关系需通过迭代器的构造函数定义，有些可以直接转换，有些则需调用特定方法。
特别地，反向迭代器到普通迭代器的转换可以通过调用反向迭代器的base()方法实现。但初版代码存在缺陷，未能按预期将元素正确删除。通过跟踪代码并参考cpp reference文档，我们发现base()方法返回的迭代器实际上比预期位置靠后一个元素。
为了修正这个问题，我们需要将通过base()方法得到的迭代器向前移动一个位置，以正确指向第一个符合移除条件的元素。修改代码后，可以确保元素按约定进行删除。
在一般场景下，迭代器的使用主要涉及遍历访问和遍历修改元素值。对于删除和插入操作，可能需要将反向迭代器转换为普通迭代器。STL容器的erase和insert成员函数仅接受普通迭代器作为参数。
在执行插入操作时，直接使用base()将反向迭代器转换为普通迭代器，并传入insert函数，其语义是一致的。而在删除操作中，直接使用base()转换后的迭代器可能无法正确执行，因为反向迭代器和普通迭代器在终止位置上的处理存在差异。为了修正此问题，需要手动调整，确保迭代器的有效性。
对于反向迭代器，通过正确的反向迭代操作得到的迭代器，在不等于rend()返回的迭代器时，都是指向有效值的。因此，除了rend().base()-1操作可能导致问题外，其他转换通常都是安全的。
讨论end()迭代器的前移操作时，需要考虑是否能够安全地访问容器的尾端元素。对于随机访问迭代器，如vector容器，end()返回的迭代器可以进行前移操作，但需确保移动操作的合法性。对于双向访问迭代器如list，同样可以进行前移操作以访问尾端元素。
结束讨论前，还需要确认iterator的-1操作是否对指向容器尾端元素的迭代器有效。在vector容器中，通过end成员函数返回的迭代器通过-1操作可以得到指向尾端元素的普通迭代器。对于list容器，其end成员函数返回的迭代器也支持前移操作。
总结来说，支持向前移动操作的迭代器访问容器内元素的容器，其end成员函数通过前移操作可以得到一个指向容器尾端元素的迭代器。这符合双向迭代器的设定语义。通过反向迭代器的原理，我们也能验证end()函数返回的迭代器可以进行反向移动。
