几乎每一个软件项目都要用到诸如链表，搜索树，堆，哈希表等一系列常用数据结构以及排序，搜索等算法。究竟是用现有的标准库(STL,boost)，还是根据项目需要自己实现呢？之所以提出这个问题，是因为笔者发现很多有名的开源项目都没有用一行的STL(
更不用说boost,loki之类的，笔者见识有限，至今还没见过有影响力的软件用了boost，尽管他很优秀)，于是搜集了一些关于STL的讨论，便成此文。
自己做轮子，还是搭便车？
在一些性能要求较高的场合，是否用STL在国外论坛似乎一直有争论。
（参见 STL for game engine） . 反对STL的一方认为，STL由于其通用性的考虑，效率始终不太高。支持方认为STL都是高手写成且充分受业界评价，已经足够优化，自己实现的数据结构不 见得比他好，只需要在少部分性能关键的代码段做优化即可。
很多开发团队认为，借助外部库需要非常谨慎，因为代码不掌握在自己手中，对调试和排错有时候会惹麻烦。基于这个理由，很多有实力的公司会开发自己的库。比如百度，EA有自己的STL实现，QQ客户端则用自己写的一套框架。
还有不少中小型开源项目，干脆用到什么就写什么样的数据结构和算法。一个团队做的东西一般都有个大体方向，形成自己风格的算法库不是难事。个人觉得，每种数据结构都有各自适合的算法，泛型虽然从概念上是个优雅的好主意，但是为了实现泛型，一堆iterator转来转去，未必就够针对性的实现来得直观(毕竟一种软件所用的算法是有限的，而且有时需要特定的优化)。
anyway, 掌握数据结构的实现方法和STL的使用都应该是一个程序员的基本功。下面分别讨论。
使用并扩展STL
选择实现版本。STL只是一个规范，他的实现版本对性能也有很大影响。一般用SGI的STL实现，比起VC下的PJ版实现要高效，在VC++下编程，可以用STLPort替换掉VC下的版本。
明白原理。抱怨STL慢在很多情况下是因为使用不当，用一个库之前最好能明白他的实现原理。侯捷翻译的<STL源码剖析>以SGI版本深入浅出讲述了container, iterator, algorithm的原理。比如，如果知道vector的自动增长原理，使用的时候就会用reserve先分配好预计的内存，减少重新分配，拷贝数据的开销, 这样就已经很接近原生数组了。
扩展STL。如果对STL实现很了解，还可以自己扩展他，比如写自己的allocator, 或者在他之上添加新的container，并适应泛型算法的调用要求。有本数<designing components with the C++ STL>有相关的例子。
自己做轮子 如果项目中大量类型使用相同的数据结构，在C++中用模板来实现就最自然不过，在此就不讨论了。
在C下写的数据结构怎么适应不同类型呢？支撑整个互联网的关键软件都是用纯C来写(linux/unix, mysql, 各种web server, memcached)，他们有些规模也不小，如何做到一份算法代码给不同类型使用呢？这就需要一些很tricky的宏技巧。
方法一：算法函数的参数的值是void指针，指定结构体长度。比如C标准库中的qsort. 在livemedia开源项目中，hashtable通过类型信息来把void指针转换成相应类型。
方法二：利用偏移量取回结构体数据。
最经典的是linux内核的链表实现(参见
深入分析linux内核链表) . list_entry宏从链表结点中还原出结构体类型。
#define list_entry(ptr, type, member) container_of(ptr, type, member)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
//offsetof宏定义在[include/linux/stddef.h]中：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
这可以说是类型无关的链表实现范例。这个container_of宏技巧还用于linux内核中red black tree的实现。
方法三：用宏代替模板。有些很雷人的实现，比如freeBSD有个左倾红黑树的实现，全是宏替换.(
LLRBT宏实现)