首先声明标题只是抱怨性质的话。
今天本来是想写一个带堆优化的 Dijkstra 算法的，我不愿意自己写一个堆，所以就打算用 STL 的相应代码来实现。据我目前所知，STL 里有两种方式维护一个堆，一种是用 priority_queue, 一种是用 make_heap, push_heap, pop_heap 一类的函数。由于 priority_queue 不能实现修改堆中的 key 操作（也就是最大堆中的 Increase-key, 或者最小堆中的 Decrease-key 操作），而且封装得太紧，所以我选用了后者。
由于 Dijkstra 算法中，有一步是要找到最小 dist 的那个顶点，这一步如果用堆优化，就可以把复杂度从 n 降为 1（其主要的开销在堆的维护上，所以总复杂度是 nlogn）。但是有的时候某些已知顶点 v 的 dist 是会改变的，所以这个时候需要把堆里与 v 对应的 key 进行修改。为了修改这个元素，首先要知道这个元素的下标为几何，这个时候可以维护一个数组，其下标为 v 的元素指向堆中相应的代表 v 的元素。这个时候麻烦就来了：如果对堆进行了修改，刚才所述的数组也同样需要修改。这个时候貌似 make_heap 之类的函数也无能为力了。
阅读全文
我之前总是觉得，10 万行 C++ 代码里，用到一个 union 就不错了（可能比较夸张）。但是现在我突然想到，在一类情况下，union 还是大有用武之地的。
有的时候我们需要直接对二进制数据进行操作，比如将一个结构体的信息保存到一个二进制文件里的时候，或者直接操作一些底层的东西，或者说开发一些底层的协议啥的。在之前我都是用“把结构体指针转换成 char 数组指针”，然后进行的。
阅读全文
在父类的构造函数或析构函数中调用虚函数，调用的不是子类的重载函数，而就是这个类的相应函数。但是如果在父类的其它函数中调用虚函数，会调用到子类的重载函数。
其实这个是很容易理解的，构造函数调用的顺序，是先调用父类的构造函数，再调用子类的构造函数。由于父类的构造函数运行的时候，子类甚至没被初始化，所以不好调用子类的虚函数。反过来看，析构函数是从子类开始调用到父类，父类的析构函数调用的时候，子类已经析构了，这时虚函数也不能够调用子类的。
阅读全文
今天做 POJ 1204 的时候，我写了一个树结构，每个节点里有一个边数组，因为一个节点最多 26 条边，所以直接开了一个 26 的数组。相当于是邻接表写的吧。然后因为节点是用 vector 存储的，当时也考虑到 vector 在重分配 (reallocation) 的时候会让该容器之前的迭代器、指针和引用失效 (A reallocation invalidates all previously obtained iterators, references and pointers to elements of the vector), 所以才选用了数组下标替代指针的方法。因为通过下标访问元素是 vector 已经封装好了的函数，无论内存如何重分配，也不会改变任何元素的下标。
但是即使是这样，程序还是在内存重新分配的时候出了问题。这个问题非常诡异，所以写一篇文章备忘一下，也请各位看官注意。
后来就让这个 Bug 给我整了两个 Time Limit Exceeded. 在 Visual Studio .NET 里调试那是一点问题也没有，而用 G++ 4.3.4 编译的时候就出问题了。
阅读全文
首先发点牢骚，谷歌上搜索 operator-> 是不能搜索到预期的结果的，因为 > 这个符号谷歌没有处理好，或者说谷歌根本没打算处理……
还好我灵感一来就写了 operator-> 结果搜到的大多数是 operator>> 但是少量的是 operator-> 最后点击了一个韩文的网页，用谷歌翻译把韩文翻译成了英文，最后看懂了。这是我从出生到现在第一次如此由衷地感谢棒子。
阅读全文
最近在校内网广泛流传一篇笑话，说是一个 IT 男去相亲的时候问了别人三个问题，其中第一个问题是：“C++ 中的虚函数和纯虚函数有什么区别？”结果那个女孩子没答上来。
考虑到明天俱乐部里刚好要讲到这个问题，我就先在这里写了吧。
阅读全文
C++ <algorithm> 中的函数的名字真让人费解，本文旨在对其简单归纳。如果同时满足“传入开始和结束迭代器对象”、“返回之间的一个迭代器对象的”、“不要求序列是排序过后的序列（即复杂度大约是 O(n) 的）”，都视为线性序列查找函数。这样一来， <algorithm> 里的查找函数，有：find, find_if, find_end, find_first_of, adjacent_find, mismatch, search, search_n, …
这篇文章参考了 http://www.cplusplus.com/reference/algorithm/ . 所有示例代码可以到这里找。
阅读全文
C++ 的书上常说，尽量不要用 #define 来定义常量。这究竟是为什么呢？
其实 C++ 并不仅仅不提倡用宏来定义常量，而且还不提倡用宏来定义“函数”。事实上 C++ 并不是很喜欢预处理宏，在很多很多方面，如果不是必需，尽量不要使用预处理宏。
为什么 C++ 不喜欢预处理宏？
首先，预处理宏是“全局”的。所以，在 C++ 这样如此强调命名空间、类这样的东西的语言中，全局的东西真是越少越好。但是其实预处理宏的全局并不是语义上的全局，之所以叫预处理宏，是因为预处理宏会在编译器编译代码之前被简单地替换成代码。
阅读全文
我一直有这样一种观点，C++ 中的引用返回，只适合返回已经存在了的对象的引用。如果想要返回一个在函数中新建的对象的引用，则是有问题的：因为这个新建对象要么放在堆中，要么放在栈中；若是放在了栈中，函数返回的时候，对象就被销毁了，这样的话，返回的引用也就失效了；若是放在堆中，返回的引用虽然是正确的，但是由于“引用”只是另一种形式的“指针”，所以即使引用的生命周期结束了，对象还是在堆里没有得到释放。
基于以上观点，我就觉得，如果想让函数创建一个对象，那么我们应该让函数返回对象的指针，或者直接返回对象本身。然后问题又来了，如果我们的程序里用到了指针，就不是很好看了。而且我们也不想整天记着去销毁这些对象，一疏忽，内存就泄露了。所以我还是偏好返回对象本身。
但是，返回对象本身就有效率问题了：对象在函数里，需要用到构造函数，在对象的构造和处理之后，返回这个对象，当赋值操作进行的时候，是否需要使用复制构造函数，或者需要等号运算符呢？如果需要的话，那临时变量又要销毁，这样一创建再销毁，不是浪费了吗？编译器能不能让函数直接在这个要赋值的空间上进行操作呢？
阅读全文
这篇文章同样是写给同学们滴，我在机房承诺给同学们的链表源代码现在终于兑现啦。
从前我从 VB 转向 C 时，被一个前辈“警告”说，C 语言的指针很难，在 VB 里没有指针的概念，所以我会经历一个相当困难的转型时期。事实证明，这个转型时期比较困难是没错，但是困难并不在指针上。所以其实指针就是个纸老虎，大家不要怕。
什么？哦，什么是链表？好吧……先说说链表本身。链表是由若干个有先后次序的节点组成的图结构，画成图就是这个样子：
单向链表示例
其中，上图的圆圈代表节点，圆圈里的数字是节点里的数据（当然节点的数据可以是数字以外的很多东西），箭头表示节点之间的连接关系。什么？那六个点是什么？那六个点是省略号啊……
这个时候就要说到链表的作用了。链表能表示怎样的一种情况？看看窗外一排停车位，链表就可以表示那一排停着的车，奔驰的下一个是宝马，宝马下一个是保时捷，保时捷下一个是兰博基尼，还有省略号……此时就有如下一种链表关系：
脑海中高档住宅小区的停车场示意图
大家不要觉得链表只能写在一行上，像上面这样也是链表，一条蛇扭了扭应该也算是蛇吧。
阅读全文
