皮皮网

1.c++如何能学好啊？
2.STL 源码剖析：sort
3.STL源码剖析总结笔记（5）：认识迭代器的码剖好帮手--list

c++如何能学好啊？

       复制来的：

       ----------------------------------------------------------------------------------------------------------------------------

       一些同学问我，如何学好C++，析高我没有别的码剖办法给你们，唯一的析高办法就是读书，读大量的码剖书，就可以解决。析高远控手机软件源码要把C++作为日常语言，码剖而不是析高一种程序语言，这样就好办了。码剖

       有人又要问我，析高那么我应该读什么书才好？没有时间怎么办？我只能对你们说，码剖没时间的析高话，就别学C++了，码剖做你们喜欢做的析高事。生活中没有

       C++，码剖也同样美好。如果你准备学，一定要学好，那么我开个书单，应该问题不是甚大。

       首先肯定要读一读Bjarne Stroustrup的The Design and Evolution of C++，了解一下这个语言的历史。接下来就可以看别的书了，但要不停地回头看这本书，看到你不断地学到的新技术是怎么样一点点地被接纳到这个语言中去的。

       第一本书因人而异，基础好一些的，可以看Stanley B. Lippman的C++ Primer，这本书非常地巨大，你打星号的部分可以不要看。基础不太好的tomcat 源码跟踪，可以看Stanley B.Lippman的Essential C++，这本书份量要轻得多，不过四个C++的范型都讲了，而且讲得非常清楚。

       第二本应该停止技术层面的东西，静下心来看看Pike和Kernighan的The Practiceof Programming，好好地整理一下，在程序设计中应该有哪些注意的事项。这本非常薄的booklet，可以说是程序员必读的指南。

       第三本书，就应该是Bruce Eckel写的、候捷译的Thinking in C++，这本书每过半年我就要重读一遍。可以说每一章都是写得发人深省的，这本书让我感觉到了技术运用的非常高的境界，但是语言非常平实，只要认真地读，即使基础不行，也一定可以懂。我在教课的时候，就是用这本书（面对的学生是零基础）。

       要更上一层的话，就要慢一步，先要把握C++设计习惯的良好。这是Scott Meyers的Effective C++和More Effective C++带给我们的无尽收益。我More Effective C++买不起，只好花了块钱复印装订了一本"线装本"，看起来像葵花宝典（;-)）。这两本书是ebuy源码 .net真正的经典，作者对C++的纯熟，使得语言的风格读起来简直是如饴甘甜，就像他站在对面在讲课。我手中有这两本书的原版CD，如果有兴趣，可以发E-mail到sjtu@.net或在饮水思源投条儿给gaobo索要，只要您提供光盘我就给免费烧。如果你已经深刻地理解了Effective C++和More EffectiveC++，那你可以发现，你在众人中已经是鸡群之鹤。可以指导项目运作了，可以编写一切你想做的程序了，可以指出别人看起来不错的代码的大小问题了。如果你能一眼看出有人的代码是对应于"条款"或"条款M6"，那你可真是让本人刮目了。

       我已经讲了，如果要写程序，EC++和MEC++的境界已经足以使你自如应付，可是如果你还不满足，想关注一些理论层面的问题，或是想看看实现的代码，你就不应该错过这几本好极了的书。我是说Herb Sutter的Exceptional C++和MoreExceptional C++，这两本书的难度是非常大的，我对每一条的阅读笔记都是十多页。特别是泛型程序设计的部分，这两本书旁征博引，极尽深入探讨之能事，每每看懂一条，都抹汗一次，火速sdk源码大感酣畅淋漓；还有侯捷的 STL源码剖析 ，以实际的例子一点点地讲解一个STL是怎么样实现的，我是刚开始读，不发表评论；而Stanley B. Lippman，Cfront的实现者之一，执笔写出Inside the C++ ObjectModel，我只有一个字，就是基本帅呆了。我从中了解了无数的编译器解释源代码的细节，以及记忆体分配的细节，呵呵，这些都知道了，我还怕什么呢？最近得到了另一Cfront实现者、C++标准委员会Koenig的 C++沉思录，看起来非常不错，这里也推荐给大家，但我也没看完，亦无发言权。

       最后最后，你们，未来的C++理论家们，可要记住，Bjarne Stroustrup的The C++Programming Language无论如何也应该读个四五遍！这是一切C++的书本的源泉。如果还觉得不够，就向C++标准委员会订购一本C++标准。

       一切中国大陆作者的书，一概不要看（包括我的）。一切VC++或讲特定的编译器的书，一概不要看。网站源码讲解如果需要补C语言的课，买一本非常小的K&R的The CProgramming Language足矣，其它的书一概不要看。不要先学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 的源码是在快排的基础上，通过堆排序和插入排序来维护时间复杂度的稳定，不至于退化为 [公式] 。

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

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`）的实现提供了基础。在接下来的内容中，我们将详细探讨迭代器的实现技巧，以及如何在实际编程中利用这些概念来优化代码。