幾乎每一個軟件項目都要用到諸如鏈表，搜索樹，堆，哈希表等一系列常用數據結構以及排序，搜索等算法。究竟是用現有的標準庫(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宏實現)