1.STL源码剖析9-set、码剖multiset
2.推荐一本C++书籍，清晰本人是码剖初学者
3.STL 源码剖析：sort
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一样，star chart 源码下载它也依赖红黑树的数据结构，但对元素的比较规则更为宽松，允许基于给定的比较仿函数进行重复元素的插入和查找。
推荐一本C++书籍，本人是初学者
C++入门经典
评：也许这本书不为大家所熟悉，但是对我却意义非常。大一一个暑假，我就看了这么一本书，笔记抄了三本（作业本），大四走的时候扔笔记那叫一个伤心啊。我是在完全不了解C++的时候用这本书入的门，也是那个时候开始用的Code::Blocks，^_^。
C++ Primer
评：我读的第二本C++方面的书（大学教材就不算了，从来没有看过一眼），刚学的时候最后几章看不太懂。C++圣经级的书籍，程序员枕边必备书籍。
C++ templates
评：这本书当时读起来很吃力，大部分都是电视源码录制教程靠用笔抄过来的，除了第一章，后几章基本上不太懂。事实证明，我当时的选择是非常正确的，这本书后来为我学习STL，深入理解C++打下了坚实的基础。只读过一遍，我的C++模板功底是在论坛练出来的，C++的学习不断的实践和回顾。
C++标准程序库
评：没的说，必备书籍。没事的时候，翻一翻。
STL源码剖析
评：这本书和上一本书，是我唯一看过三遍的书（但是还想看第四遍），每一遍都有新的收获。第一遍就是抄，其实我学程序设计都是抄过来的，第一遍对STL还没什么理解；第二遍熟悉了STL，大部分搞的asp源码 电子档案差不多了，也都理解了；第三遍就是把第二遍中没看懂的内存配置器（第二遍感觉非常不理解）给搞懂了。最让我蛋疼的是RB_TREE了，现在想起来都头疼。时间长了，好多又忘了，但是思想一直记得呢。我郑重的很负责任的告诉大家：“没学模板，千万不要看STL源码，没意义，真的。”
Effective C++ 和 More Effective C++
评：STL和这两本书作为提升功力很好的一个选择。之所以放到一起，我觉得它们是一个类型的书。More……比前者要难很多，我觉得。看了很多遍了，但是有一些还是不懂。这两本书是值得反复思考，反复阅读的书。
Effective STL
评：不做过多的互助直销系统源码评价，一直想看，都没看完过。我有纸质版的。
高质量C++编程指南
评：我看的电子版，我的感觉是看完“很痛快”。
深度探索C++对象模型
评：加深理解C++必备书籍，看了个大概，没细看。我觉得翻译的不好，看着很别扭。
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 的源码是在快排的基础上，通过堆排序和插入排序来维护时间复杂度的稳定，不至于退化为 [公式] 。
鬼知道我写这么多是为了干嘛……
