STL 源码剖析：sort
我大抵是太闲了。
更好的源码源代阅读体验。
sort 作为最常用的码案 STL 之一，大多数人对于其了解仅限于快速排序。案例
听说其内部实现还包括插入排序和堆排序，源码源代于是码案仿react源码很好奇，决定通过源代码一探究竟。案例
个人习惯使用 DEV-C++，源码源代不知道其他的码案编译器会不会有所不同，现阶段也不是案例很关心。
这个文章并不是源码源代析完之后的总结，而是码案边剖边写。不免有个人的案例猜测。而且由于本人英语极其差劲，源码源代大抵会犯一些憨憨错误。码案
源码部分sort
首先，在 Dev 中输入以下代码：
然后按住 ctrl，鼠标左键sort，就可以跳转到头文件 stl_algo.h，并可以看到这个：
注释、模板和函数参数不再解释，我们需要关注的是函数体。
但是，中间那一段没看懂……
点进去，是一堆看不懂的#define。
查了一下，spring源码手写框架感觉这东西不是我这个菜鸡能掌握的。
有兴趣的 戳这里。
那么接下来，就应该去到函数__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
就是js源码在线解密直接对区间的每个元素进行插入。
总结
到这里，sort 的源代码就剖完了（除了堆的那部分）。
虽然没怎么看懂，但也理解了，sort 的源码是在快排的基础上，通过堆排序和插入排序来维护时间复杂度的稳定，不至于退化为 [公式] 。
鬼知道我写这么多是为了干嘛……
c语言中预处理命令都有哪些
我们可以在C源程序中插入传给编译程序的各中指令，这些指令被称为预处理器指令，它们扩充了程序设计的环境。现把常用的预处理命令总结如下：
1. 预处理程序
按照ANSI标准的定义，预处理程序应该处理以下指令：
#if #ifdef #ifndef #else #elif
#endif
#define
#undef
#line
#error
#pragma
#include
显然，上述所有的个预处理指令都以符号#开始，，每条预处理指令必须独占一行。
2. #define
#define指令定义一个标识符和一个串（也就是字符集），在源程序中发现该标识符时，都用该串替换之。这种标识符称为宏名字，相应的替换称为宏代换。一般形式如下：
#define macro-name char-sequence
这种语句不用分号结尾。宏名字和串之间可以有多个空白符，但串开始后只能以新行终止。
例如：我们使用LEFT代表1，用RIGHT代表0，我们使用两个#define指令：
#define LEFT 1
#define RIGHT 0
每当在源程序中遇到LEFT或RIGHT时，编译程序都用1或0替换。
定义一个宏名字之后，可以在其他宏定义中使用,例如：
#define ONE 1
#define TWO ONE+ONE
#define THREE ONE+TWO
宏代换就是用相关的串替代标识符。因此，如果希望定义一条标准错误信息时，可以如下定义：
#define ERROR_MS “Standard error on input \n”
如果一个串长于一行，可在行尾用反斜线”\”续行，如下：
#define LONG_STRING “This is a very very long \
String that is used as an example”
3. #error
#error指令强制编译程序停止编译，它主要用于程序调试。#error指令的一般形式是：
#error error-message
注意，宏串error-message不用双引号包围。遇到#error指令时，错误信息被显示，可能同时还显示编译程序作者预先定义的其他内容。
4. #include
程序中的#include指令要求编译程序读入另一个源文件。被读入文件的名字必须用双引号(“”)或一对尖括号(<>)包围，例如：
#include “stdio.h”
#include <stdio.h>
都使C编译程序读入并编译头文件以用于I/O系统库函数。
包含文件中可以包含其他#include指令，称为嵌套包含。允许的最大嵌套深度随编译器而变。
文件名被双括号或尖括号包围决定了对指定文件的搜索方式。文件名被尖括号包围时，搜索按编译程序作者的定义进行，一般用于搜索某些专门放置包含文件的特殊目录。当文件名被双括号包围时，搜索按编译程序实时的规定进行，一般搜索当前目录。如未发现，再按尖括号包围时的办法重新搜索一次。
通常，绝大多数程序员使用尖括号包围标准的头文件，双引号用于包围与当前程序相关的文件名。
5. 条件编译指令
若干编译指令允许程序员有选择的编译程序源代码的不同部分，这种过程称为条件编译。
5.1#if、#else、#elif #endif
条件编译指令中最常用的或许是#if,#else,#elif和#endif。这些指令允许程序员根据常数表达式的结果有条件的包围部分代码。
#if的一般形式是：
#if constant-expression
Statement sequence
#endif
如#if后的常数表达式为真，则#if和#endif中间的代码被编译，否则忽略该代码段。#endif标记#if块的结束。
#else指令的作用与C语言的else相似，#if指令失败时它可以作为备选指令。例如：
#include <stdio.h>
#define MAX
Int main(void)
{
#if MAX>
printf(“Compiled for array greater than .\n”);
#else
printf(“Complied for small array.\n”);
#endif
return 0;
}
注意，#else既是标记#if块的结束，也标记#else块的开始。因为每个#if只能写一个#endif匹配。
#elif指令的意思是“否则，如果”，为多重编译选择建立一条if-else-if（如果-否则-如果链）。如果#if表达式为真，该代码块被编译，不测试其他#elif表达式。否则，序列中的下一块被测试，如果成功则编译之。一般形式如下：
#if expression
Statement sequence
#elif expression1
Statement sequence
#elif expression2
Statement sequence
.
.
.
#elif expression
Statement sequence
#endif
5.2#ifdef和#ifndef
条件编译的另一个方法是使用编译指令#ifdef和#ifndef，分别表示“如果已定义”和“如果未定义”。#ifdef的一般形式如下：
#ifdef macro-name
Statement sequence
#endif
如果macro-name原先已经被一个#define语句定义，则编译其中的代码块。
#ifndef的一般形式是：
#ifndef macro-name
Statement sequence
#endif
如果macro-name当前未被#define语句定义，则编译其中的代码块。
我认为，用这种，可以很方便的开启/关闭整个程序的某项特定功能。
#ifdef和#ifndef都可以使用#else或#elif语句。
#inlucde <stdio.h>
#define T
Int main(void)
{
#ifdef t
Printf(“Hi T\n”);
#else
Printf(“Hi anyone\n”);
#endif
#ifndef M
Printf(“M Not Defined\n”);
#endif
Return 0;
}
6. #undef
#undef指令删除前面定义的宏名字。也就是说，它“不定义”宏。一般形式为：
#undef macro-name
7. 使用defined
除#ifdef之外，还有另外一种确定是否定义宏名字的方法，即可以将#if指令与defined编译时操作符一起使用。defined操作符的一般形式如下：
defined macro-name
如果macro-name是当前定义的，则表达式为真，否则为假。
例如，确定宏MY是否定义，可以使用下列两种预处理命令之一：
#if defined MY
或
#ifdef MY
也可以在defined之前加上感叹号”!”来反转相应的条件。例如，只有在DEBUG未定义的情况下才编译。
#if !defined DEBUG
Printf(“Final Version!\n”);
#endif
使用defined的一个原因是，它允许由#elif语句确定的宏名字存在。
8. #line
#line指令改变__LINE__和__FILE__的内容。__LINE__和__FILE__都是编译程序中预定义的标识符。标识符__LINE__的内容是当前被编译代码行的行号，__FILE__的内容是当前被编译源文件的文件名。#line的一般形式是：
#line number “filename”
其中，number是正整数并变成__LINE__的新值；可选的“filename”是合法文件标识符并变成__FILE__的新值。#line主要用于调试和特殊应用。
9. #pragma
#pragma是编译程序实现时定义的指令，它允许由此向编译程序传入各种指令。例如，一个编译程序可能具有支持跟踪程序执行的选项，此时可以用#pragma语句选择该功能。编译程序忽略其不支持的#pragma选项。#pragma提高C源程序对编译程序的可移植性。
. 预处理操作符#和##
有两个预处理操作符：#和##，它们可以在#define中使用。
操作符#通常称为字符串化的操作符，它把其后的串变成用双引号包围的串。例如：
#include <stdio.h>
#define mkstr(s) #s
int main(void)
{
Printf(mkstr(I like C));
Return 0;
}
预处理程序把以下的语句：
Printf(mkstr(I like C));
变成
Printf(“I like C”);
操作符##把两个标记拼在一起，形成一个新标记。例如：
#include <stdio.h>
#define concat(a,a) a##b
int main(void)
{
Int xy = ;
Printf(“%d”,concat(x,y));
Return 0;
}
预处理程序把以下语句：
Printf(“%d”,concat(x,y));
变成
Printf(“%d”,xy);
操作符#和##主要作用是允许预处理程序对付某些特殊情况，多数程序中并不需要。
. 预定义宏
C规范了5个固有的预定义宏，它们是：
__LINE__
__FILE__
__DATE__
__TIME__
__STDC__
__LINE__和__FILE__包含正在编译的程序的行号和文件名。
__DATE__和内容形如month/day/year(月/日/年)的串，代表源文件翻译成目标码的日期。
__TIME__中的串代表源代码编译成目标码的时间，形如hour:minute:second(时：分：秒)
如果__STDC__的内容是十进制常数1，则表示编译程序的实现符合标准C。
c语言编程题打印出所有的“水仙花数”所谓“水仙花数”是指一个三位数其各位数字立方和等于该数本身
打印出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数
本身。例如：是一个“水仙花数”，因为=1的三次方＋5的三次方＋3的三次方。
1.程序分析：利用for循环控制-个数，每个数分解出个位，十位，百位。
2.程序源代码：
main()
{
int i,j,k,n;
printf("'water flower'number is:");
for(n=;n<;n++)
{
i=n/;/*分解出百位*/
j=n/%;/*分解出十位*/
k=n%;/*分解出个位*/
if(i*+j*+k==i*i*i+j*j*j+k*k*k)
{
printf("%-5d",n);
}
}
printf("\n");
}
2024-12-28 18:24
2024-12-28 18:08
2024-12-28 17:13
2024-12-28 16:40
2024-12-28 16:24
