本人开学后花了三天终于在昨天3.10（也是本人的阳历生日）完成了红黑树的实现 自认为没有bug…… 不过感觉接口设计上不是很好，觉得得学习一下stl 源码在github上，点这里 上面那个是看思路自己意淫出来的，这里有个模仿STL的版本 但是没有改好。。还有几个error…… 除此之外，特别想说一个知识点，就是在模板实现上，其声明和定义是不能卸载两个文件里的，因为在编译的时候，编译器就必须知道类的大小（好吧，其实我也解释不大来…… 非要写在两个文件里的话，我只知道特化，当然，这不是很可取。 完。…
一点废话 最近终于看完了《STL源码剖析》的前三章，个人觉得前三章是这本书最重要的部分，考虑到时间问题（简历还没投啊，拖太晚了），其他的具体实现先放放也罢。 关于STL中的空间配置器(allocator)，在STL的运用角度上看，空间配置器是最不需要知道的东西。而在STL的实现上，空间配置器是最必须也是最先需要知道的东西。 乱七八糟的东西 首先我们必须知道的是，在C++中通过new一个新的对象，它的实际步骤可以分为两个部分：配置内存(allocat)，调用构造函数(construct)。而当我们通过delete一个对象的时候，它的实际步骤也可以分为两个部分：调用析构函数(destroy)，释放内存(deallocat)。 关于构造和析构，并不是我这里讲的重点，只要会点基础的cpp就好了。 而关于对象构造前的空间配置和对象析构后的空间释放，SGI STL对此的设计哲学如下： * 向system heap 申请空间 * 考虑多线程状态 * 考虑内存不足的应变措施 * 考虑过多的小型区块可能造成的内存碎片问题 核心部分 一些乱七八糟的东西讲完了（…
动态链接库与静态链接库的区别 静态链接库 静态链接库是将整个库文件都与目标程序链接在一起，整合到一个可执行文件中。 动态链接库 动态链接库与静态链接库相反，在可执行文件中，只记录了库文件的一些信息（位置啊，函数名什么的……瞎猜的），在需要的时候有OS进行调用。 另外动态链接还分为载入时链接，与运行时链接。 载入时链接是在程序载入时，将整个库文件同时载入，而运行时链接是在程序运行时发现这段函数程序未在内存中而由OS载入。 可以理解成运行时链接是动态的动态。 区别与比较 一点小区别： 静态链接库不能引用其他库文件，而动态链接库则可以。 以下讨论两者优劣势力，只谈优势，因为动态链接库的优势就是静态链接库的劣势，反之亦然。 动态链接库优势： 1. 这种链接方式，使得所有需要这个库文件的文件共享一个库文件在内存上的拷贝，与静态链接相比，可以减少内存的消耗。这对频繁调用的函数来说十分有利。 2. 维护性增强。只要保持接口不变，在修改库文件之后，只需要编译库文件即可，而静态链接库则需要重新编译整个文件。这对大项目来说，是不划算的。 3. 减小…
本文转自此博文,因无法联系作者擅自转载,若需要删除请作者留言 只有首先调用close()发起主动关闭的一方才会进入TIME_WAIT状态，进入TIME_WAIT状态的TCP连接需要经过2MSL才能回到初始状态，其中，MSL是指Max Segment Lifetime，即数据包在网络中的最大生存时间。每种TCP协议的实现方法均要指定一个合适的MSL值，如RFC1122给出的建议值为2分钟，又如Berkeley体系的TCP实现通常选择30秒作为MSL值。这意味着TIME_WAIT的典型持续时间为1-4分钟。 产生原因及好处 对于TIME_WAIT的存在，有两个理由。一个原因是为了防止一个连接中延迟的数据段会被后序的连接错误的解析。当一个连接处于2MSL状态的时候，任何到达的数据段都将会被丢弃。第二个原因是为了实现TCP全双工连接的终止可靠性。 为实现TCP这种全双工（full-duplex）连接的可靠释放 参考TCP释放连接4次挥手过程，假设发起active close的一方（通常为client）发送的ACK（4次交互的最后一个包）在网络中丢失，那么由于TC…
自从上一次写完红黑树入门已经过去一个多月了……当时天真的我觉得就算再难只要花个一个下午就可以把删除操作搞懂，然而……………… 阅前须知 但是我现在在这里申明一点，其实红黑树的删除操作也算不上太难，有一点是因为分类情况太多了。而我迟迟没有理解的一个主要原因在于 我们讨论的删除节点并不是我们在红黑树删除操作中传入的删除的节点,而是被删除节点的替换节点 因为在二叉查找树的删除过程中，被删除的节点实际上会被一个前驱最大节点或者是后继最小节点来替代。 而我们在红黑树中，可以在替换节点的同时，替换节点的颜色改成删除节点的颜色，那么我们的修复目标一下子缩小到了几乎是最下面的子树层，并且对删除节点处的性质并没有任何改变。实在是妙极！ 另外感谢这篇文章，我是通过这个博文学习的，并且图片也来自这个博客，写的很好，推荐。 正文 由前文所得，我们的删除操作可以分为两部分，一个是删除，一个是修复。 当然插入的时候也可以分为插入和修复两部分，而且很有条理性，但是插入太简单了，也没细说。 在这里仍然需要提一个大前提：在二叉查找树的删除操作中，对于替换节点，其实是有两个选择的，…
老实说，LeetCode在我眼中的地位并不是很高，今天偶然刷了一下，没想到，写三个不会三个…… 是我变菜了，还是本来就不是那么简单，不过就结论来说，LeetCode对现在的我来说有刷一刷的价值。 这是三道成套的问题。提供题号 141,142,287。 1. 如何判断一个链表中是否存在环。不允许修改链表，不允许申请O(N)及以上的空间。 2. 在第一个问题的基础上，找到环的入口点。限制相同。 3. 给 n+1 个数字，范围是 [1,n] ，找出重复的那一个数字。只允许使用O(1)的空间，不允许修改数组，复杂度低于 $ O(N^2) $ 先剧透一下，第三个问题和第二个问题是一样的……我特么……惊了。 直接说解法，第一个问题。创建两个指针，一个指针走两步，一个指针走一步，…
之前的文章有提到，PC（一般为32位）的启动过程为 BIOS -> MBR -> loader -> kernel。 BIOS在休眠后的最后任务是从硬盘中的第0柱面第0磁头第1扇区中读取MBR，其实就是逻辑0扇区。因为扇区是从1开始计数的。 BIOS所做的内部原理对我来说是从来不去涉及的，所以也就不讨论这个。 从MBR开始才是我们程序猿所能任意写的内容，而MBR同BIOS一样，也需要对下一阶段loader进行过渡。 而一个特别麻烦的地方就是，没有任何库与函数供我们调用……因此我们只能在汇编层面从硬盘读取数据。 老实说，我也不清楚应该从哪开始讲，后续内容都建立在以下基础知识之上： * CPU通过端口访问设备 * 硬盘中的块表示有CHS和LBA方式 * 通道的概念 * 一个PATA线可以挂两个硬盘，一个主盘，一个从盘 * 以前一般主板只支持４个PATA硬盘，所以只需两个通道，这里也只提两个通道 * 硬盘的IO接口称为硬盘控制器 硬盘控制器的主要端口寄存器 Primary 通道Secondary 通道读操作 写操作0x1F00x170DataData…
以前嫌麻烦留着没看，今天补了一下，发现其实只是一些api的调用罢了，这里做个笔记。 对于我们用户来来说，获取物理内存的容量一般用内核调用即可，比如Linux 2.6中使用的detect_memory函数调用。其本质就是使用BIOS的中断0x15检测的。 这里稍微解释一下BIOS(可跳过)，BIOS，基本输入输出系统，PC启动加载的第一个软件，介于操作系统与硬件的抽象层，可用于检测，加载引导程序或者操作系统。显然，PC的启动流程应该是 BIOS -> MBR -> loader -> kernel。 简要说明 开始正文。中断0x15有三个子功能，子功能号放到EAX或者AX中，其简要说明： * EAX = 0xE820 遍历所有内存 * AX = 0xE801 分别检测低 15 MB 和 16 MB ~ 4 GB的内存，最大支持 4 GB。 * AX…