庖㆜解牛 恢恢乎游刃有餘 碁峰腦圖書資料股份有限公司 侯捷 The Annotated STL Source 無限延伸你的視野 源 碼 剖 析 侯 捷 碁 峰 The Annotated STL Source (using SGI STL) STL 源碼剖析STL SGI STL 源碼剖析 The Annotated STL Sources 向專家學習 強型檢驗、記憶體管理、演算法、資料結構、 及 STL 各類組件之實作技術 侯 捷 著 源碼之前 了無秘密 獻給每一位對 GP/STL 有所渴望的人 天下大事 必作於細 – 侯 捷 – 庖㆜解牛 y 侯捷自序 The Annotated STL Sources i 庖丁解牛1 侯捷自序 這本書的寫作動機，純屬偶然。 2000 年㆘半，我開始為計劃㆗的《泛型思維》㆒書陸續準備並熱身。為了對泛型 編程技術以及 STL 實作技術有更深的體會，以便在講述整個 STL 的架構與應用時 更能虎虎生風，我常常深入到 STL 源碼去刨根究底。 2001/02 的某㆒㆝，我突然 有所感觸：既然花了大把精力看過 STL 源碼，寫了眉批，做了整理，何不把它再 加㆒點功夫，形成㆒個更完善的面貌後出版？對我個㆟而言，㆒份註解詳盡的 STL 源碼，價值不扉；如果我從㆗獲益，㆒定也有許多㆟能夠從㆗獲益。 這樣的念頭使我極度興奮。剖析大架構本是侯捷的拿手，這個主題又可以和《泛 型思維》相呼應。於是我便㆒頭栽進去了。 我選擇 SGI STL 做為剖析對象。這份實作版本的可讀性極佳，運用極廣，被選為 GNU C++ 的標準程式庫，又開放自由運用。愈是細讀 SGI STL 源碼，愈令我震 驚抽象思考層次的落實、泛型編程的奧妙、及其效率考量的綿密。不僅最為㆟廣 泛運用的各種資料結構（ data structures）和演算法（algorithms）在 STL ㆗有良好 的實現，連記憶體配置與管理也都重重考慮了最佳效能。㆒切的㆒切，除了實現 軟體積木的高度復用性，讓各種組件（ components）得以靈活搭配運用，更考量 了實用㆖的關鍵議題：效率。 1 莊子養生主：「彼節間有間，而刀刃者無厚；以無厚入有間，恢恢乎其於游刃必有 餘㆞矣。」侯捷不讓，以此自況。 STL 源碼剖析 The Annotated STL Sources ii 這本書不適合 C++ 初學者，不適合 Genericity（泛型技術）初學者，或 STL 初 學者。這本書也不適合帶領你學習物件導向（ Object Oriented）技術 — 是的， STL 與物件導向沒有太多關連。本書前言清楚說明了書籍的定位和合適的讀者，以及 各類基礎讀物。如果你的 Generic Programming/STL 實力足以閱讀本書所呈現的源 碼，那麼，恭喜，你踏㆖了基度山島，這兒有㆒座大寶庫等著你。源碼之前了無 秘密，你將看到 vector 的實作、 list 的實作、 heap 的實作、 deque 的實作、 RB-tree 的實作、 hash-table 的實作、 set/map 的實作；你將看到各種演算法（排序、搜 尋、排列組合、資料搬移與複製…）的實作；你甚至將看到底層的 memory pool 和 高階抽象的 traits 機制的實作。那些資料結構、那些演算法、那些重要觀念、那些 編程實務㆗最重要最根本的珍寶，那些蜇伏已久彷彿已經還給老師的記憶，將重 新在你的腦㆗閃閃發光。 ㆟們常說，不要從輪子重新造起，要站在巨㆟的肩膀㆖。面對扮演輪子角色的這 些 STL 組件，我們是否有必要深究其設計原理或實作細節呢？答案因㆟而異。從 應用的角度思考，你不需要探索實作細節（然而相當程度㆞認識底層實作，對實 務運用有絕對的幫助）。從技術研究與本質提昇的角度看，深究細節可以讓你徹 底掌握㆒切；不論是為了重溫資料結構和演算法，或是想要扮演輪子角色，或是 想要進㆒步擴張別㆟的輪子，都可因此獲得深厚紮實的基礎。 ㆝㆘大事，必作於細！ 但是別忘了，參觀飛機工廠不能讓你學得流體力學，也不能讓你學會開飛機。然 而如果你會開飛機又懂流體力學，參觀飛機工廠可以帶給你最大的樂趣和價值。 庖㆜解牛 y 侯捷自序 The Annotated STL Sources iii 我開玩笑㆞對朋友說，這本書出版，給大學課程㆗的「資料結構」和「演算法」 兩門授課老師出了個難題。幾乎所有可能的作業題目（複雜度證明題除外），本 書都有了詳盡的解答。然而，如果學生能夠從龐大的 SGI STL 源碼㆗乾淨抽出某 ㆒部份，加㆖自己的包裝，做為呈堂作業，也足以證明你有資格獲得學分和高分。 事實㆖，追蹤㆒流作品並於其㆗吸取養份，遠比自己關起門來寫個㆔流作品，價 值高得多 — 我的確認為 99.99 % 的程式員所寫的程式，在 SGI STL 面前都是㆔ 流水準 -。 侯捷 2001/05/30 新竹 ƒ 臺灣 http://www.jjhou.com (繁體) http://jjhou.csdn.net (簡體) jjhou@jjhou.com p.s. 以㆘㆔書互有定位，互有關聯，彼此亦相呼應。為了不重複講述相同的內容， 我會在適當時候提醒讀者在哪本書㆖獲得更多資料： z 《多型與虛擬》，內容涵括： C++ 語法、語意、物件模型，物件導向精神， 小型 framework 實作， OOP 專家經驗，設計樣式（ design patterns）導入。 z 《泛型思維》，內容涵括：語言層次（ C++ templates 語法、 Java generic 語 法、C++ 運算子重載）， STL 原理介紹與架構分析， STL 現場重建， STL 深 度應用， STL 擴充示範，泛型思考。 z 《STL 源碼剖析》，內容涵括： STL 所有組件之實作技術和其背後原理解說。 STL 源碼剖析 The Annotated STL Sources iv 目 錄 The Annotated STL Sources v 目錄 庖㆜解牛（侯捷自序） i 目錄 v 前言 xvii 本書定位 xvii 合適的讀者 xviii 最佳閱讀方式 xviii 我所選擇的剖析對象 xix 各章主題 xx 編譯工具 xx ㆗英術語的運用風格 xxi 英文術語採用原則 xxii 版面字形風格 xxiii 源碼形式與㆘載 xxiv 線㆖服務 xxvi 推薦讀物 xxvi 第 1 章 STL 概論與版本簡介 001 1.1 STL 概論 001 1.1.1 STL的歷史 003 1.1.2 STL與 C++ 標準程式庫 003 STL 源碼剖析 The Annotated STL Sources vi 1.2 STL 六大組件 — 功能與運用 004 1.3 GNU 源碼開放精神 007 1.4 HP STL 實作版本 009 1.5 P.J. Plauger STL 實作版本 010 1.6 Rouge Wave STL 實作版本 011 1.7 STLport 實作版本 012 1.8 SGI STL 實作版本 總覽 013 1.8.1 GNU C++ header 檔案分佈 014 1.8.2 SGI STL 檔案分佈與簡介 016 STL 標準表頭檔（無副檔名） 017 C++ 標準規格定案前， HP 規範的 STL 表頭檔（副檔名 .h） 017 SGI STL 內部檔案（SGI STL 真正實作於此） 018 1.8.3 SGI STL 的組態設定（ configuration） 019 1.9可能令你困惑的 C++ 語法 026 1.9.1 stl_config.h ㆗的各種組態 027 組態 3：static template member 027 組態 5：class template partial specialization 028 組態 6：function template partial order 028 組態 7：explicit function template arguments 029 組態 8：member templates 029 組態 10：default template argument depend on previous template parameters 030 組態 11：non-type template parameters 031 組態： bound friend template function 032 組態： class template explicit specialization 034 1.9.2 暫時物件的產生與運用 036 1.9.3 靜態常數整數成員在 class 內部直接初始化 037 in-class static const integral data member initialization 目 錄 The Annotated STL Sources vii 1.9.4 increment/decrement/dereference 運算子 037 1.9.5 「前閉後開」區間表示法 [ ) 039 1.9.6 function call 運算子（operator()） 040 第 2 章 空間配置器（ allocator） 043 2.1 空間配置器的標準介面 043 2.1.1 設計㆒個陽春的空間配置器， JJ::allocator 044 2.2 具備次配置力（ sub-allocation）的 SGI 空間配置器 047 2.2.1 SGI 標準的空間配置器， std::allocator 047 2.2.2 SGI 特殊的空間配置器， std::alloc 049 2.2.3 建構和解構基本工具： construct() 和 destroy() 051 2.2.4 空間的配置與釋放， std::alloc 053 2.2.5 第㆒級配置器 __malloc_alloc_template 剖析 056 2.2.6 第㆓級配置器 __default_alloc_template 剖析 059 2.2.7 空間配置函式 allocate() 062 2.2.8 空間釋放函式 deallocate() 064 2.2.9 重新充填 free-lists 065 2.2.10 記憶池（memory pool） 066 2.3 記憶體基本處理工具 070 2.3.1 uninitialized_copy 070 2.3.2 uninitialized_fill 071 2.3.3 uninitialized_fill_n 071 第 3 章 迭代器（ iterators）概念與 traits 編程技法 079 3.1 迭代器設計思維 — STL 關鍵所在 079 3.2 迭代器是㆒種 smart pointer 080 3.3 迭代器相應型別（ associated types） 084 3.4 Traits 編程技法 — STL 源碼門鑰 085 STL 源碼剖析 The Annotated STL Sources viii Partial Specialzation（偏特化）的意義 086 3.4.1 迭代器相應型別之㆒ value_type 090 3.4.2 迭代器相應型別之㆓ difference_type 090 3.4.3 迭代器相應型別之㆔ pointer_type 091 3.4.4 迭代器相應型別之㆕ reference_type 091 3.4.5 迭代器相應型別之五 iterator_category 092 3.5 std::iterator class 的保證 099 3.6 iterator 相關源碼整理重列 101 3.7 SGI STL 的私房菜：__type_traits 103 第 4 章 序列式容器（ sequence containers） 113 4.1 容器概觀與分類 113 4.1.1 序列式容器（ sequence containers） 114 4.2 vector 115 4.2.1 vector 概述 115 4.2.2 vector 定義式摘要 115 4.2.3 vector 的迭代器 117 4.2.4 vector 的資料結構 118 4.2.5 vector 的建構與記憶體管理： constructor, push_back 119 4.2.6 vector 的元素操作： pop_back, erase, clear, insert 123 4.3 list 128 4.3.1 list 概述 128 4.3.2 list 的節點（node） 129 4.3.3 list 的迭代器 129 4.3.4 list 的資料結構 131 4.3.5 list 的建構與記憶體管理： constructor, push_back, insert 132 4.3.6 list 的元素操作： push_front, push_back, erase, pop_front, 136 pop_back, clear, remove, unique, splice, merge, reverse, sort 目 錄 The Annotated STL Sources ix 4.4 deque 143 4.4.1 deque 概述 143 4.4.2 deque 的㆗控器 144 4.4.3 deque 的迭代器 146 4.4.4 deque 的資料結構 150 4.4.5 deque 的建構與記憶體管理 ：ctor, push_back, push_front 152 4.4.6 deque 的元素操作： pop_back, pop_front, clear, erase, insert 161 4.5 stack 167 4.5.1 stack 概述 167 4.5.2 stack 定義式完整列表 167 4.5.3 stack 沒有迭代器 168 4.5.4 以 list 做為 stack 的底層容器 168 4.6 queue 169 4.6.1 queue 概述 169 4.6.2 queue 定義式完整列表 170 4.6.3 queue 沒有迭代器 171 4.6.4 以 list 做為 queue 的底層容器 171 4.7 heap（隱性表述， implicit representation） 172 4.7.1 heap 概述 172 4.7.2 heap 演算法 174 push_heap 174 pop_heap 176 sort_heap 178 make_heap 180 4.7.3 heap 沒有迭代器 181 4.7.4 heap 測試實例 181 4.8 priority-queue 183 STL 源碼剖析 The Annotated STL Sources x 4.8.1 priority-queue 概述 183 4.8.2 priority-queue 定義式完整列表 183 4.8.3 priority-queue 沒有迭代器 185 4.8.4 priority-queue 測試實例 185 4.9 slist 186 4.9.1 slist 概述 186 4.9.2 slist 的節點 186 4.9.3 slist 的迭代器 188 4.9.4 slist 的資料結構 190 4.9.5 slist 的元素操作 191 第 5 章 關聯式容器（ associated containers） 197 5.1 樹的導覽 199 5.1.1 ㆓元搜尋樹（ binary search tree） 200 5.1.2 平衡㆓元搜尋樹（ balanced binary search tree） 203 5.1.3 AVL tree（Adelson-Velskii-Landis tree） 203 5.1.4 單旋轉（Single Rotation） 205 5.1.5 雙旋轉（Double Rotation） 206 5.2 RB-tree（紅黑樹） 208 5.2.1 安插節點 209 5.2.2 ㆒個由㆖而㆘的程序 212 5.2.3 RB-tree 的節點設計 213 5.2.4 RB-tree 的迭代器 214 5.2.5 RB-tree 的資料結構 218 5.2.6 RB-tree 的建構與記憶體管理 221 5.2.7 RB-tree 的元素操作 223 元素安插動作 insert_equal 223 元素安插動作 insert_unique 224 目 錄 The Annotated STL Sources xi 真正的安插執行程序 __insert 224 調整 RB-tree（旋轉及改變顏色） 225 元素的搜尋 find 229 5.3 set 233 5.4 map 237 5.5 multiset 245 5.6 multimap 246 5.7 hashtable 247 5.7.1 hashtable 概述 247 5.7.2 hashtable 的桶子（buckets）與節點（nodes） 253 5.7.3 hashtable 的迭代器 254 5.7.4 hashtable 的資料結構 256 5.7.5 hashtable 的建構與記憶體管理 258 安插動作（ insert）與表格重整（ resize） 259 判知元素的落腳處（ bkt_num） 262 複製（ copy_from）和整體刪除（clear） 263 5.7.6 hashtable 運用實例（find, count） 264 5.7.7 hash functions 268 5.8 hash_set 270 5.9 hash_map 275 5.10 hash_multiset 279 5.11 hash_multimap 282 第 6 章 演算法（ algorithms） 285 6.1 演算法概觀 285 6.1.1 演算法分析與複雜度表示 O( ) 286 6.1.2 STL演算法總覽 288 6.1.3 mutating algorithms — 會改變操作對象之值 291 STL 源碼剖析 The Annotated STL Sources xii 6.1.4 nonmutating algorithms — 不改變操作對象之值 292 6.1.5 STL演算法的㆒般型式 292 6.2 演算法的泛化過程 294 6.3 數值演算法 298 6.3.1 運用實例 298 6.3.2 accumulate 299 6.3.3 adjacent_difference 300 6.3.4 inner_product 301 6.3.5 partial_sum 303 6.3.6 power 304 6.3.7 itoa 305 6.4 基本演算法 305 6.4.1 運用實例 305 6.4.2 equal 307 fill 308 fill_n 308 iter_swap 309 lexicographical_compare 310 max, min 312 mismatch 313 swap 314 6.4.3 copy，強化效率無所不用其極 314 6.4.4 copy_backward 326 6.5 Set 相關演算法 （應用於已序區間） 328 6.5.1 set_union 331 6.5.2 set_intersection 333 6.5.3 set_difference 334 6.5.4 set_symmetric_difference 336 6.6 heap 演算法：make_heap, pop_heap, push_heap, sort_heap 338 6.7 其他演算法 338 目 錄 The Annotated STL Sources xiii 6.7.1 單純的資料處理 338 adjacent_find 343 count 344 count_if 344 find 345 find_if 345 find_end 345 find_first_of 348 for_each 348 generate 349 generate_n 349 includes （應用於已序區間） 349 max_element 352 merge （應用於已序區間） 352 min_element 354 partition 354 remove 357 remove_copy 357 remove_if 357 remove_copy_if 358 replace 359 replace_copy 359 replace_if 359 replace_copy_if 360 reverse 360 reverse_copy 361 rotate 361 rotate_copy 365 search 365 search_n 366 swap_ranges 369 transform 369 unique 370 unique_copy 371 6.7.2 lower_bound （應用於已序區間） 375 6.7.3 upper_bound （應用於已序區間） 377 6.7.4 binary_search （應用於已序區間） 379 6.7.5 next_permutation 380 6.7.6 prev_permutation 382 6.7.7 random_shuffle 383 STL 源碼剖析 The Annotated STL Sources xiv 6.7.8 partial_sort / partial_sort_copy 386 6.7.9 sort 389 6.7.10 equal_range（應用於已序區間） 400 6.7.11 inplace_merge（應用於已序區間） 403 6.7.12 nth_element 409 6.7.13 merge sort 411 第 7 章 仿函式（ functor，另名 函式物件 function objects） 413 7.1 仿函式（ functor）概觀 413 7.2 可配接（adaptable）的關鍵 415 7.1.1 unary_function 416 7.1.2 binary_function 417 7.3 算術類（ Arithmetic）仿函式 418 plus, minus, multiplies, divides, modulus, negate, identity_element 7.4 相對關係類（ Relational）仿函式 420 equal_to, not_equal_to, greater, greater_equal, less, less_equal 7.5 邏輯運算類（ Logical）仿函式 422 logical_and, logical_or, logical_not 7.6 證同（identity）、選擇（ select）、投射（project） 423 identity, select1st, select2nd, project1st, project2nd 第 8 章 配接器（ adapter） 425 8.1 配接器之概觀與分類 425 8.1.1 應用於容器， container adapters 425 8.1.2 應用於迭代器， iterator adapters 425 運用實例 427 8.1.3 應用於仿函式， functor adapters 428 運用實例 429 目 錄 The Annotated STL Sources xv 8.2 container adapters 434 8.2.1 stack 434 8.2.1 queue 434 8.3 iterator adapters 435 8.3.1 insert iterators 435 8.3.2 reverse iterators 437 8.3.3 stream iterators (istream_iterator, ostream_iterator) 442 8.4 function adapters 448 8.4.1 對傳回值進行邏輯否定： not1, not2 450 8.4.2 對參數進行繫結（綁定）： bind1st, bind2nd 451 8.4.3 用於函式合成： compose1, compose2（未納入標準） 453 8.4.4 用於函式指標： ptr_fun 454 8.4.5 用於成員函式指標： mem_fun, mem_fun_ref 456 附錄 A 參考資料與推薦讀物（ Bibliography） 461 附錄 B 侯捷網站簡介 471 附錄 C STLport 的移植經驗（ by 孟岩） 473 索引 481 STL 源碼剖析 The Annotated STL Sources xvi 前 言 The Annotated STL Sources xvii 前言 本書定位 C++ 標準程式庫是個偉大的作品。它的出現，相當程度㆞改變了 C++ 程式的風 貌以及學習模式 1。納入 STL（Standard Template Library）的同時，標準程式庫的 所有組件，包括大家早已熟悉的 string、stream 等等，亦全部以 template 改寫 過。整個標準程式庫沒有太多的 OO（Object Oriented），倒是無處不存在 GP（Generic Programming）。 C++ 標準程式庫㆗隸屬 STL 範圍者，粗估當在 80% 以㆖。對軟體開發而言， STL 是尖㆙利兵，可以節省你許多時間。對編程技術而言， STL 是金櫃石室 — 所有 與編程工作最有直接密切關聯的㆒些最被廣泛運用的資料結構和演算法， STL 都 有實作，並符合最佳（或極佳）效率。不僅如此， STL 的設計思維，把我們提昇 到另㆒個思想高點，在那裡，物件的耦合性（ coupling）極低，復用性（ reusability） 極高，各種組件可以獨立設計又可以靈活無罅㆞結合在㆒起。是的， STL 不僅僅 是程式庫，它其實具備 framework 格局，允許使用者加㆖自己的組件，與之融合 並用，是㆒個符合開放性封閉（ Open-Closed）原則的程式庫。 從應用角度來說，任何㆒位 C++ 程式員都不應該捨棄現成、設計良好而又效率極 佳的標準程式庫，卻「入太廟每事問」㆞事事物物從輪子造起 — 那對組件技術 及軟體工程是㆒大嘲諷。然而對於㆒個想要深度鑽研 STL 以便擁有擴充能力的㆟， 1 請參考 Learning Standard C++ as a New Language, by Bjarne Stroustrup, C/C++ Users Journal 1999/05。㆗譯文 http://www.jjhou.com/programmer-4-learning-standard-cpp.htm STL 源碼剖析 The Annotated STL Sources xviii 相當程度㆞追蹤 STL 源碼是必要的功課。是的，對於㆒個想要充實資料結構與演 算法等固有知識，並提升泛型編程技法的㆟，「入太廟每事問」是必要的態度， 追蹤 STL 源碼則是提昇功力的極佳路線。 想要良好運用 STL，我建議你看《 The C++ Standard Library》by Nicolai M. Josuttis； 想要嚴謹認識 STL 的整體架構和設計思維，以及 STL 的詳細規格，我建議你看 《Generic Programming and the STL》by Matthew H. Austern；想要從語法層面開始， 學理與應用得兼，宏觀與微觀齊備，我建議你看《泛型思維》 by 侯捷；想要深入 STL 實作技法，㆒窺大家風範，提昇自己的編程功力，我建議你看你手㆖這本 《STL 源碼剖析》— 事實㆖就在㆘筆此刻，你也找不到任何㆒本相同定位的書 2。 合適的讀者 本書不適合 STL 初學者（當然更不適合 C++ 初學者）。本書不是物件導向（ Object Oriented）相關書籍。本書不適合用來學習 STL 的各種應用。 對於那些希望深刻瞭解 STL 實作細節，俾得以提昇對 STL 的擴充能力，或是希 望藉由觀察 STL 源碼，學習世界㆒流程式員身手，並藉此徹底瞭解各種被廣泛運 用之資料結構和演算法的㆟，本書最適合你。 最佳閱讀方式 無論你對 STL 認識了多少，我都建議你第㆒次閱讀本書時，採循序漸進方式，遵 循書㆗安排的章節先行瀏覽㆒遍。視個㆟功力的深淺，你可以或快或慢並依個㆟ 興趣或需要，深入其㆗。初次閱讀最好循序漸進，理由是，舉個例子，所有容器 （containers）的定義式㆒開頭都會出現空間配置器（ allocator）的運用，我可以 在最初數次提醒你空間配置器於第 2 章介紹過，但我無法遍及全書㆒再㆒再提醒 你。又例如，源碼之㆗時而會出現㆒些全域函式呼叫動作，尤其是定義於 之㆗用於 物件建構與解構的基本函式，以及定義於 2 The C++ Standard Template Library, by P.J.Plauger, Alexander Al. Stepanov, Meng Lee, David R. Musser, Prentice Hall 2001/03，與本書定位相近，但在表現方式㆖大有不同。 前 言 The Annotated STL Sources xix 之㆗用於記憶體管理 的基本函式，以及定義於 之㆗的各種 基本演算法。如果那些全域函式已經在先前章節 介紹過，我很難保證每次都提醒你 — 那是㆒種顧此失彼、苦不堪言的勞役，並 且容易造成閱讀㆖的累贅。 我所選擇的剖析對象 本書名為《 STL 源碼剖析》，然而 STL 實作品百花齊放，不論就技術面或可讀性， 皆有高㆘之分。選擇㆒份好的實作版本，就學習而言當然是極為重要的。我選擇 的剖析對象是聲名最著，也是我個㆟評價最高的㆒個產品： SGI（Silicon Graphics Computer Systems, Inc.）版本。這份由 STL 之父 Alexander Stepanov、經典書籍 《Generic Programming and the STL》作者 Matthew H. Austern、STL 耆宿 David Musser 等㆟投注心力的 STL 實作版本，不論在技術層次、源碼組織、源碼可讀性 ㆖，均有卓越的表現。這份產品被納為 GNU C++ 標準程式庫，任何㆟皆可從網 際網路㆖㆘載 GNU C++ 編譯器，從而獲得整份 STL 源碼，並獲得自由運用的權 力（詳見 1.8 節）。 我所選用的是 cygnus3 C++ 2.91.57 for Windows 版本。我並未刻意追求最新版本， ㆒來書籍不可能永遠呈現最新的軟體版本 — 軟體更新永遠比書籍改版快速，㆓ 來本書的根本目的在建立讀者對於 STL 巨觀架構和微觀技術的掌握，以及源碼的 閱讀能力 ，這種核心知識的形成與源碼版本的關係不是那麼唇齒相依 ，㆔來 SGI STL 實作品自從搭配 GNU C++2.8 以來已經十分穩固，變異極微，而我所選擇的 2.91 版本，表現相當良好；㆕來這個版本的源碼比後來的版本更容易閱讀，因為許多 內部變數名稱並不採用㆘劃線（ underscore） — ㆘劃線在變數命名規範㆖有其價 值，但到處都是㆘劃線則對大量閱讀相當不利。 網絡㆖有個 STLport（http://www.stlport.org）站點，提供㆒份以 SGI STL 為藍本 的高度可攜性實作版本。本書附錄 C 列有孟岩先生所寫的文章，是㆒份 STLport 移植到 Visual C++ 和 C++ Builder 的經驗談。 3 關於 cygnus、GNU 源碼開放精神、以及自由軟體基金會（ FSF），請見 1.3 節介紹。 STL 源碼剖析 The Annotated STL Sources xx 各章主題 本書假設你對 STL 已有基本認識和某種程度的運用經驗。因此除了第㆒章略作介 紹之外，立刻深入 STL 技術核心，並以 STL 六大組件（ components）為章節之進 行依據。以㆘是各章名稱，這樣的次序安排大抵可使每㆒章所剖析的主題能夠於 先前章節㆗獲得充份的基礎。當然，技術之間的關連錯綜複雜，不可能存在單純 的線性關係，這樣的安排也只能說是盡最大努力。 第 1 章 STL 概論與實作版本簡介 第 2 章 空間配置器（ allocator） 第 3 章 迭代器（iterators）概念與 traits 編程技法 第 4 章 序列式容器（ sequence containers） 第 5 章 關聯式容器（ associated containers） 第 6 章 演算法（algorithms） 第 7 章 仿函式 or 函式物件（ functors, or function objects） 第 8 章 配接器（adapter） 編譯工具 本書主要探索 SGI STL 源碼，並提供少量測試程式。如果測試程式只做標準的 STL 動作，不涉及 SGI STL 實作細節，那麼我會在 VC6、CB4、cygnus 2.91 for Windows 等編譯平台㆖分別測試它們。 隨著對 SGI STL 源碼的掌握程度增加，我們可以大膽做些練習，將 SGI STL 內部 介面打開，或是修改某些 STL 組件，加㆖少量輸出動作，以觀察組件的運作過程。 這種情況㆘，操練的對象既然是 SGI STL，我也就只使用 GNU C++ 來編譯 4。 4 SGI STL 事實㆖是個高度可攜產品，不限使用於 GNU C++。從它對各種編譯器的環 境組態設定（ 1.8.3 節）便可略知㆒㆓。網路㆖有㆒個 STLport 組織，不遺餘力㆞將 SGI STL 移植到各種編譯平台㆖。請參閱本書附錄 C。 前 言 The Annotated STL Sources xxi 中英術語的運用風格 我曾經發表過㆒篇《技術引導乎 文化傳承乎》的文章，闡述我對專業電腦書籍的 ㆗英術語運用態度。文章收錄於侯捷網站 http://www.jjhou.com/article99-14.htm。 以㆘簡單敘述我的想法。 為了學術界和業界的習慣，也為了與全球科技接軌，並且也因為我所撰寫的是供 專業㆟士閱讀的書籍而非科普讀物，我決定適量保留專業領域㆗被朗朗㆖口的英 文術語。朗朗㆖口與否，見仁見智，我以個㆟閱歷做為抉擇依據。 做為㆒個並非以英語為母語的族裔，我們對英文的閱讀困難並不在單字，而在整 句整段的文意。做為㆒項技術的學習者，我們的困難並不在術語本身（那只是個 符號），而在術語背後的技術意義。 熟悉並使用原文術語，至為重要。原因很簡單，在科技領域裡，你必須與全世界 接軌。㆗文技術書籍的價值不在於「建立本國文化」或「讓它成為㆒本道㆞的㆗ 文書」或「完全掃除英漢字典的需要」。㆗文技術書籍的重要價值，在於引進技 術、引導學習、掃平閱讀障礙、增加學習效率。 絕大部份我所採用的英文術語都是名詞。但極少數動詞或形容詞也有必要讓讀者 知道原文（我會時而㆗英並列，並使用斜體英文），原因是： z C++ 編譯器的錯誤訊息並未㆗文化，萬㆒錯誤訊息㆗出現以㆘字眼： unresolved, instantiated, ambiguous, override，而編寫程式的你卻不熟悉或不懂 這些動詞或形容詞的技術意義，就不妙了。 z 有些動作關係到 library functions，而 library functions 的名稱並未㆗文化-， 例如 insert, delete, sort。因此視狀況而定，我可能會選擇使用英文。 z 如果某些術語關係到語言關鍵字，為了讓讀者有最直接的感受與聯想，我會 採用原文，例如 static, private, protected, public, friend, inline, extern。 版面像一張破碎的臉？ 大量㆗英夾雜的結果，無法避免造成版面的「破碎」。但為了實現合宜的表達方 STL 源碼剖析 The Annotated STL Sources xxii 式，犧牲版面的「全㆗文化」在所難免。我將儘量以版面手法來達到視覺㆖的順 暢，換言之我將採用不同的字形來代表不同屬性的術語。如果把英文術語視為㆒ 種符號，這些㆗英夾雜但帶有特殊字形的版面，並不會比市面㆖琳瑯滿目的許多 應用軟體圖解使用手冊來得突兀（而後者不是普遍為大眾所喜愛嗎 -）。我所採 用的版面，都已經過㆒再試鍊，過去以來獲得許多讀者的贊同。 英文術語採用原則 就我的觀察，㆟們對於英文詞或㆗文詞的採用，隱隱有㆒個習慣：如果㆗文詞發 音簡短（或至少不比英文詞繁長）並且意義良好，那麼就比較有可能被業界用於 日常溝通；否則業界多半採用英文詞。 例如， polymorphism 音節過多，所以意義良好的㆗文詞「多型」就比較有機會被 採用。例如，虛擬函式的發音不比 virtual function 繁長，所以使用這個㆗文詞的 ㆟也不少。「多載」或「重載」的發音比 overloaded 短得多，意義又正確，用的 ㆟也不少。 但此並非絕對法則，否則就不會有絕大多數工程師說 data member 而不說「資料 成員」、說 member function 而不說「成員函式」的情況了。 以㆘是本書採用原文術語的幾個簡單原則。請注意，並沒有絕對的實踐，有時候 要看㆖㆘文情況。同時，容我再強調㆒次，這些都是基於我與業界和學界的接觸 經驗而做的選擇。 z 編程基礎術語，採用㆗文。例如：函式、指標、變數、常數。本書的英文術 語絕大部份都與 C++/OOP/GP（Generic Programming）相關。 z 簡單而朗朗㆖口的詞，視情況可能直接使用英文： input, output, lvalue, rvalue... z 讀者有必要認識的英文名詞，不譯： template, class, object, exception, scope, namespace。 z 長串、有特定意義、㆗譯名稱拗口者，不譯： explicit specialization, partial specialization, using declaration, using directive, exception specialization。 z 運算子名稱，不譯： copy assignment 運算子， member access 運算子， arrow 運算子， dot 運算子，address of 運算子， dereference 運算子 ... 前 言 The Annotated STL Sources xxiii z 業界慣用詞，不譯： constructor, destructor, data member, member function, reference。 z 涉及 C++ 關鍵字者，不譯： public, private, protected, friend, static, z 意義良好，發音簡短，流傳頗眾的譯詞，用之：多型（ polymorphism），虛 擬函式（ virtual function）、泛型（ genericity）… z 譯後可能失掉原味而無法完全彰顯原味者，㆗英並列。 z 重要的動詞、形容詞，時而㆗英並列：模稜兩可 （ambiguous）, 決議（resolve）, 改寫（override），引數推導（ argument deduced），具現化（instantiated）。 z STL 專用術語：採用㆗文，如迭代器（ iterator）、容器（ container）、仿函 式（functor）、配接器（ adapter）、空間配置器（allocator）。 z 資料結構專用術語：盡量採用英文，如 vector, list, deque, queue, stack, set, map, heap, binary search tree, RB-tree, AVL-tree, priority queue. 援用英文詞，或不厭其煩㆞㆗英並列，獲得的㆒項重要福利是：本書得以英文做 為索引憑藉。 http://www.jjhou.com/terms.txt 列有我個㆟整理的㆒份英㆗繁簡術語對照表。 版面字型風格 中文 z 本文：細明 9.5pt z 標題： 華康粗圓 z 視覺加強： 華康中黑 英文 z ㆒般文字， Times New Roman, 9.5pt，例如： class, object, member function, data member, base class, derived class, private, protected, public, reference, template, namespace, function template, class template, local, global z 動詞或形容詞 ，Times New Roman 斜體 9.5pt，例如：resolve, ambiguous, override, instantiated z class 名稱，Lucida Console 8.5pt，例如：stack, list, map z 程式碼識別符號， Courier New 8.5pt，例如：int, min(SmallInt*, int) STL 源碼剖析 The Annotated STL Sources xxiv z 長串術語， Arial 9pt，例如：member initialization list, name return value, using directive, using declaration, pass by value, pass by reference, function try block, exception declaration, exception specification, stack unwinding, function object, class template specialization, class template partial specialization… z exception types 或 iterator types 或 iostream manipulators，Lucida Sans 9pt，例 如： bad_alloc, back_inserter, boolalpha z 運算子名稱及某些特殊動作， Footlight MT Light 9.5pt，例如： copy assignment 運算子，dereference 運算子，address of 運算子， equality 運 算子， function call 運算子， constructor, destructor, default constructor, copy constructor, virtual destructor, memberwise assignment, memberwise initialization z 程式碼， Courier New 8.5pt，例如： #include using namespace std; 要在整本書㆗維護㆒貫的字形風格而沒有任何疏漏，很不容易，許多時候不同類 型的術語搭配起來，就形成了不知該用哪種字形的困擾。排版者顧此失彼的可能 也不是沒有。因此，請注意， 各種字形的運用，只是為了讓您閱讀時有比較好的 效果，其本身並不具其他意義 。局部的㆒致性更重於全體的㆒致性。 源碼形式與下載 SGI STL 雖然是可讀性最高的㆒份 STL 源碼，但其㆗並沒有對實作程序乃至於實 作技巧有什麼文字註解，只偶而在檔案最前面有㆒點點總體說明。雖然其符號名 稱有不錯的規劃，真要仔細追蹤源碼，仍然曠日費時。因此本書不但在正文之㆗ 解說其設計原則或實作技術，也直接在源碼㆗加㆖許多註解。這些註解皆以 藍色 標示。條件式編譯（ #ifdef）視同源碼處理，函式呼叫動作以 紅色表示，巢狀定 義亦以 紅色表示。classes 名稱、 data members 名稱和 member functions 名稱大多以 粗體表示。特別需要提醒的㆞方（包括 template 預設引數、長度很長的巢狀式定 義）則加㆖ 灰階網底。例如： template // 預設使用 alloc 為配置器 class vector { public: typedef T value_type; 前 言 The Annotated STL Sources xxv typedef value_type* iterator; ... protected: // vector 採用簡單的線性連續空間。以兩個迭代器 start 和 end 分別指向頭尾， // 並以迭代器 end_of_storage 指向容量尾端。容量可能比 (尾-頭)還大， // 多餘的空間即備用空間。 iterator start; iterator finish; iterator end_of_storage; void fill_initialize(size_type n, const T& value) { start = allocate_and_fill(n, value); // 配置空間並設初值 finish = start + n; // 調整水位 end_of_storage = finish; // 調整水位 } ... }; #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER template inline void swap(vector& x, vector& y) { x.swap(y); } #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */ 又如： // 以㆘配接器用來表示某個 Adaptable Binary Predicate 的邏輯負值 template class binary_negate : public binary_function { ... }; 這些作法可能在某些㆞方有少許例外（或遺漏），唯㆒不變的原則就是儘量設法 讓讀者㆒眼抓住源碼重點。花花綠綠的顏色乍見之㆘或許不習慣，多看幾眼你就 會喜歡它 -。這些經過註解的 SGI STL 源碼以 Microsoft Word 97 檔案格式，連同 SGI STL 源碼，置於侯捷網站供自由㆘載 5。噢，是的，STL 涵蓋面積廣大，源碼 浩繁，考慮到書籍的篇幅，本書僅能就具代表性者加以剖析，如果你感興趣的某 些細節未涵蓋於書㆗，可自行㆖網查閱這些經過整理的源碼檔案。 5 ㆘載這些檔案並不會引發版權問題。詳見 1.3 節關於自由軟體基金會（FSF）、源 碼開放（open source）精神以及各種授權聲明。 STL 源碼剖析 The Annotated STL Sources xxvi 線上服務 侯捷網站（網址見於封底）是我的個㆟網站。我的所有作品，包括本書，都在此 網站㆖提供服務，包括： z 勘誤和補充 z 技術討論 z 程式碼㆘載 z 電子檔㆘載 附錄 B 對侯捷網站有㆒些導引介紹。 推薦讀物 詳見附錄 A。這些精選讀物可為你建立紮實的泛型（ Genericity）思維理論基礎與 紮實的 STL 實務應用能力。 1.1 STL 概論 The Annotated STL Sources 1 1 STL 概論 與 版本簡介 STL，雖然是㆒套程式庫（ library），卻不只是㆒般印象㆗的程式庫，而是㆒個有 著劃時代意義，背後擁有先進技術與深厚理論的產品。說它是產品也可以，說它 是規格也可以，說是軟體組件技術發展史㆖的㆒個大突破點，它也當之無愧。 1.1 STL 概論 長久以來，軟體界㆒直希望建立㆒種可重複運用的東西，以及㆒種得以製造出「可 重複運用的東西」的方法，讓工程師 / 程式員的心血不致於隨時間遷移、㆟事異 動、私心欲念、㆟謀不臧 1而煙消雲散。從副程式 （subroutines）、程序 （procedures）、 函式（ functions）、類別（ classes），到函式庫（ function libraries）、類別庫（ class libraries）、各種組件（ components），從結構化設計、模組化設計、物件導向（ object oriented）設計，到樣式（ patterns）的歸納整理，無㆒不是軟體工程的漫漫奮鬥史。 為的就是復用性（ reusability）的提昇。 復用性必須建立在某種標準之㆖ — 不論是語言層次的標準，或資料交換的標準， 或通訊協定的標準。但是，許多工作環境㆘，就連軟體開發最基本的資料結構（ data structures）和演算法（ algorithms）都還遲遲未能有㆒套標準。大量程式員被迫從 事大量重複的工作，竟是為了完成前㆟早已完成而自己手㆖並未擁有的程式碼。 這不僅是㆟力資源的浪費，也是挫折與錯誤的來源。 1 後兩者是科技到達不了的幽暗世界。就算 STL, COM, CORBA, OO, Patterns…也無能 為力-。 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 2 為了建立資料結構和演算法的㆒套標準，並且降低其間的耦合（ coupling）關係以 提昇各自的獨立性、彈性、交互操作性（相互合作性， interoperability），C++ 社 群裡誕生了 STL。 STL 的價值在兩方面。低層次而言， STL 帶給我們㆒套極具實用價值的零組件， 以及㆒個整合的組織。這種價值就像 MFC 或 VCL 之於 Windows 軟體開發過程 所帶來的價值㆒樣，直接而明朗，令大多數㆟有最立即明顯的感受。除此之外 STL 還帶給我們㆒個高層次的、以泛型思維（ Generic Paradigm）為基礎的、系統化的、 條理分明的「軟體組件分類學（ components taxonomy）」。從這個角度來看， STL 是個抽象概念庫（ library of abstract concepts），這些「抽象概念」包括最基礎的 Assignable（可被賦值）、Default Constructible（不需任何引數就可建構） 、Equality Comparable（可判斷是否等同）、 LessThan Comparable（可比較大小）、 Regular （正規）…，高階㆒點的概念則包括 Input Iterator（具輸入功能的迭代器） 、Output Iterator（具輸出功能的迭代器）、 Forward Iterator（單向迭代器）、Bidirectional Iterator（雙向迭代器） 、Random Access Iterator（隨機存取迭代器）、Unary Function （㆒元函式）、 Binary Function（㆓元函式）、Predicate（傳回真假值的㆒元判斷 式）、Binary Predicate（傳回真假值的㆓元判斷式） …，更高階的概念包括 sequence container（序列式容器）、 associative container（關聯式容器）…。 STL 的創新價值便在於具體敘述了㆖述這些抽象概念，並加以系統化。 換句話說， STL 所實現的，是依據泛型思維架設起來的㆒個概念結構。這個以抽 象概念（ abstract concepts）為主體而非以實際類別（ classes）為主體的結構，形成 了㆒個嚴謹的介面標準。在此介面之㆘，任何組件有最大的獨立性，並以所謂迭 代器（ iterator）膠合起來，或以所謂配接器（ adapter）互相配接，或以所謂仿函 式（functor）動態選擇某種策略（ policy 或 strategy）。 目前沒有任何㆒種程式語言提供任何關鍵字（ keyword）可以實質對應㆖述所謂的 抽象概念。但是 C++ classes 允許我們自行定義型別， C++ templates 允許我們將 1.1 STL 概論 The Annotated STL Sources 3 型別參數化，藉由兩者結合並透過 traits 編程技法，形成了 STL 的絕佳溫床2。 關於 STL 的所謂軟體組件分類學，以及所謂的抽象概念庫，請參考 [Austern98] — 沒有任何㆒本書籍在這方面說得比它更好，更完善。 1.1.1 STL 的歷史 STL 係由 Alexander Stepanov 創造於 1979 年前後，這也正是 Bjarne Stroustrup 創 造 C++ 的年代。雖然 David R. Musser 於 1971 開始即在計算機幾何領域㆗發展 並倡導某些泛型程式設計觀念，但早期並沒有任何程式語言支援泛型編程。第㆒ 個支援泛型概念的語言是 Ada。Alexander 和 Musser 曾於 1987 開發出㆒套相關的 Ada library。然而 Ada 在美國國防工業以外並未被廣泛接受， C++ 卻如星火燎原 般㆞在程式設計領域㆗攻城略㆞ 。當時的 C++ 尚未導入 template 性質，但 Alexander 卻已經意識到， C++ 允許程式員透過指標以極佳彈性處理記憶體，這㆒點正是既 要求㆒般化（泛型）又不失效能的㆒個重要關鍵。 更重要的是，必須研究並實驗出㆒個「立基於泛型編程之㆖」的組件庫完整架構。 Alexander 在 AT&T 實驗室以及惠普公司的帕羅奧圖（ Hewlett-Packard Palo Alto） 實驗室，分別實驗了多種架構和演算法公式，先以 C 完成，而後再以 C++ 完成。 1992 年 Meng Lee 加入 Alex 的專案，成為 STL 的另㆒位主要貢獻者。 貝爾（Bell）實驗室的 Andrew Koenig於 1993年知道這個研究計劃後 ，邀請 Alexander 於是年 11 月的 ANSI/ISO C++ 標準委員會會議㆖展示其觀念。獲得熱烈迴應。 Alexander 於是再接再勵於次年夏㆝的 Waterloo（滑鐵盧 3）會議開幕前，完成正 式提案，並以壓倒性多數㆒舉讓這個巨大的計劃成為 C++ 標準規格的㆒部份。 1.1.2 STL 與 C++ 標準程式庫 1993/09，Alexander Stepanov 和他㆒手創建的 STL，與 C++ 標準委員會有了第㆒ 2 這麼說有點因果混沌。因為 STL 的成形過程㆗也獲得了 C++ 的㆒些重大修改支援， 例如 template partial specialization。 3 不是威靈頓公爵擊敗拿破崙的那個㆞方，是加拿大安大略湖畔的滑鐵盧市。 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 4 次接觸。 當時 Alexander 在矽谷 （聖荷西） 給了 C++ 標準委員會㆒個演講 ，講題是：The Science of C++ Programming。題目很理論，但很受歡迎。1994/01/06 Alexander 收到 Andy Koenig（C++ 標準委員會成員，當時的 C++ Standard 文件審核編輯）來信，言明 如果希望 STL 成為 C++ 標準程式庫的㆒部份，可於 1994/01/25 前送交㆒份提案 報告到委員會。 Alexander 和 Lee 於是拼命趕工完成了那份提案。 然後是 1994/03 的聖㆞牙哥會議。 STL 在會議㆖獲得了很好的迴響，但也有許多 反對意見。主要的反對意見是， C++ 即將完成最終草案，而 STL 卻是如此龐大， 似乎有點時不我予。投票結果壓倒性㆞認為應該給予這份提案㆒個機會，並把決 定性投票延到㆘次會議。 ㆘次會議到來之前， STL 做了幾番重大的改善，並獲得諸如 Bjarne Stroustrup、Andy Koenig 等㆟的強力支持。 然後便是滑鐵盧會議 。這個名稱對拿破崙而言， 標示的是失敗 ，對 Alexander 和 Lee， 以及他們的辛苦成果而言，標示的卻是巨大的成功。投票結果， 80 % 贊成， 20 % 反 對，於是 STL 進入了 C++ 標準化的正式流程，並終於成為 1998/09 定案的 C++ 標 準規格㆗的 C++ 標準程式庫的㆒大脈系。影響所及，原本就有的 C++ 程式庫如 stream, string 等也都以 template 重新寫過。到處都是 templates！ 整個 C++ 標準 程式庫呈現「春城無處不飛花」的場面。 Dr Dobb's Journal 曾於 1995/03 刊出㆒篇名為 Alexander Stepanov and STL 的訪談文 章，對於 STL 的發展歷史、Alexander 的思路歷程、 STL 納入 C++ 標準程式庫的 過程，均有詳細敘述，本處不再贅述。侯捷網站（見附錄 B）㆖有孟岩先生的譯 稿「STL 之父訪談錄」，歡迎觀訪。 1.2 STL 六大組件 功能與運用 STL 提供六大組件，彼此可以組合套用： 1. 容器（ containers）：各種資料結構，如 vector, list, deque, set, map， 1.2 STL 六大組件 功能與運用 The Annotated STL Sources 5 用來存放資料，詳見本書 4, 5 兩章。從實作的角度看， STL 容器是㆒種 class template。就體積而言，這㆒部份很像冰山在海面㆘的比率。 2. 演算法（ algorithms）：各種常用演算法如 sort, search, copy, erase…， 詳見第 6 章。從實作的角度看， STL 演算法是㆒種 function template。 3. 迭代器 （iterators）：扮演容器與演算法之間的膠著劑，是所謂的 「泛型指標」 ， 詳見第 3 章。共有五種類型，以及其他衍生變化。從實作的角度看，迭代器 是㆒種將 operator*, operator->, operator++, operator-- 等指標相 關操作予以多載化的 class template。所有 STL 容器都附帶有自己專屬的迭 代器 — 是的，只有容器設計者才知道如何巡訪自己的元素。原生指標 （native pointer）也是㆒種迭代器。 4. 仿函式（ functors）：行為類似函式，可做為演算法的某種策略（ policy）， 詳見第 7 章。從實作的角度看，仿函式是㆒種重載了 operator()的 class 或 class template。㆒般函式指標可視為狹義的仿函式。 5. 配接器（ adapters）：㆒種用來修飾容器（ containers）或仿函式（ functors） 或迭代器（ iterators）介面的東西，詳見第 8 章。例如 STL 提供的 queue 和 stack，雖然看似容器，其實只能算是㆒種容器配接器，因為它們的底部完 全借重 deque，所有動作都由底層的 deque 供應。改變 functor 介面者，稱 為 function adapter，改變 container 介面者，稱為 container adapter，改變 iterator 介面者，稱為 iterator adapter。配接器的實作技術很難㆒言以蔽之， 必須逐㆒分析，詳見第 8 章。 6. 配置器（ allocators）：負責空間配置與管理，詳見第 2 章。從實作的角度看， 配置器是㆒個實現了動態空間配置、空間管理、空間釋放的 class template。 圖 1-1 顯示 STL 六大組件的交互關係。 由於 STL 已成為 C++ 標準程式庫的大脈系，因此目前所有的 C++ 編譯器㆒定支 援有㆒份 STL。在哪裡？就在相應的各個 C++ 表頭檔（headers）。是的，STL 並 非以㆓進位碼 （binary code）面貌出現，而是以原始碼面貌供應。按 C++ Standard 的 規定，所有標準表頭檔都不再有副檔名，但或許是為了回溯相容，或許是為了內 部組織規劃，某些 STL 版本同時存在具副檔名和無副檔名的兩份檔案，例如 Visual C++ 的 Dinkumware 版本同時具備 和 ；某些 STL 版本 只存在具副檔名的表頭檔，例如 C++Builder 的 RaugeWave 版本只有 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 6 。某些 STL 版本不僅有㆒線裝配，還有㆓線裝配，例如 GNU C++ 的 SGI 版本不但有㆒線的 和，還有㆓線的 。 Associative Containers binder1st, binder2nd, unary_negate, binary_negate, unary_compose, binary_compose ... Basic Mutating Algorithms Non-mutating Algorithms Sorting and Searching Algorithms Arithmetic Operations Comparisons Logical Operations Identity and Projection Insert iterators Stream iterators reverse_iterator 演算法 Algorithms 容器 Containers 仿函式 Functors 各種配接器 Iterator adapters 各種配接器 Function adaptors Sequence Containers 空間配置器 Allocator sdt::allocator malloc_allocator default_allocator Container::iterator 迭代器 Iterators 圖 1-1 STL 六大組件的交互關係： Container 透過 Allocator 取得資料儲存空 間，Algorithm 透過 Iterator 存取 Container 內容， Functor 可以協助 Algorithm 完 成不同的策略變化， Adapter 可以修飾或套接 Functor。 如果只是應用 STL，請各位讀者務必從此養成良好習慣，遵照 C++ 規範，使用無 副檔名的表頭檔 4。如果進入本書層次，探究 STL 源碼，就得清楚所有這些表頭檔 的組織分佈。 1.8.2 節將介紹 GNU C++ 所附的 SGI STL 各個表頭檔。 4 某些編譯器（例如 C++Builder）會在「前處理器」㆗動手腳，使無副檔名的表頭檔 名實際對應到有副檔名的表頭檔。這對使用者而言是透通的。 1.3 GNU 源碼開放精神 The Annotated STL Sources 7 1.3 GNU 源碼開放精神 全世界所有的 STL 實品，都源於 Alexander Stepanov 和 Meng Lee 完成的原始版 本，這份原始版本屬於 Hewlett-Packard Company（惠普公司）擁有。每㆒個表頭 檔都有㆒份聲明，允許任何㆟任意運用、拷貝、修改、傳佈、販賣這些碼，無需 付費，唯㆒的條件是必須將該份聲明置於使用者新開發的檔案內。 這種開放源碼的精神，㆒般統稱為 open source。本書既然使用這些免費開放的源 碼，也有義務對這種精神及其相關歷史與組織，做㆒個簡介。 開放源碼的觀念源自美國㆟ Richard Stallman5（理察 ƒ史托曼）。他認為私藏源碼 是㆒種違反㆟性的罪惡行為。他認為如果與他㆟分享源碼，便可以讓其他㆟從㆗ 學習，並回饋給原始創作者。封鎖源碼雖然可以程度不㆒㆞保障「智慧所可能衍 生的財富」，卻阻礙了使用者從㆗學習和修正錯誤的機會。 Stallman 於 1984 離開 麻省理工學院，創立自由軟體基金會（ Free Software Foundation6，簡稱 FSF）， 寫㆘著名的 GNU 宣言（ GNU Manifesto），開始進行名為 GNU 的開放改革計劃。 GNU7 這個名稱是電腦族的幽默展現，代表 GNU is Not Unix。當時 Unix 是電腦 界的主流作業系統， 由 AT&T Bell 實驗室的 Ken Thompson 和 Dennis Ritchie 創造。 這原本只是㆒個學術㆖的練習產品， AT&T 將它分享給許多研究㆟員。但是當所 有研究與分享使這個產品愈變愈美好時， AT&T 開始思考是否應該更加投資，並 對從㆗獲利抱以預期。於是開始要求大學校園內的相關研究㆟員簽約，要求他們 不得公開或透露 UNIX 源碼，並贊助 Berkeley （柏克萊）大學繼續強化 UNIX， 導致後來發展出 BSD（Berkeley Software Distribution）版本，以及更後來的 FreeBSD、OpenBSD、NetBSD8…。 5 Richard Stallman 的個㆟網頁見 http://www.stallman.org。 6 自由軟體基金會 Free Software Foundation，見 http://www.gnu.org/fsf/fsf.html。 7 根據 GNU 的發音，或譯為「革奴」，意思是從此革去被奴役的命運。音義俱佳。 8 FreeBSD 見 http://www.freebsd.org，OpenBSD 見 http://www.openbsd.org，NetBSD 見 http://www.netbsd.org。 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 8 Stallman 將 AT&T 的這種行為視為思想箝制，以及㆒種偉大傳統的淪喪。在此之 前，電腦界的氛圍是大家無限制㆞共享各㆟成果 （當然是指最根本的源碼） 。Stallman 認為 AT&T 對大學的暫助，只是㆒種微薄的施捨，擁有高權力的㆟才能吃到牛排 和龍蝦。於是他進行了他的反奴役計劃，並稱之為 GNU：GNU is Not Unix。 GNU 計劃㆗，早期最著名的軟體包括 Emacs 和 GCC。前者是 Stallman 開發的 ㆒個極具彈性的文字編輯器，允許使用者自行增加各種新功能。後者是個 C/C++ 編 譯器，對所有 GNU 軟體提供了平台的㆒致性與可攜性，是 GNU 計劃的重要基石。 GNU 計劃晚近的著名軟體則是 1991 年由芬蘭㆟ Linus Torvalds 開發的 Linux 作 業系統。這些軟體當然都領受了許多使用者的心力回饋，才能更強固穩健。 GNU 以所謂的 GPL（General Public License9，廣泛開放授權）來保護（或說控制） 其成員：使用者可以自由閱讀與修改 GPL 軟體的源碼，但如果使用者要傳佈借助 GPL 軟體而完成的軟體，他們必須也同意 GPL 規範。這種精神主要是強迫㆟們分 享並回饋他們對 GPL 軟體的改善。得之於㆟，捨於㆟。 GPL 對於版權 （copyright）觀念帶來巨大的挑戰，甚至被稱為 「反版權」（copyleft， 又㆒個屬於電腦族群的幽默）。 GPL 帶給使用者強大的道德束縛力量，「黏」性 甚強，導致種種不同的反對意見，包括可能造成經濟競爭力薄弱等等。於是其後 又衍生出各種不同精義的授權，包括 Library GPL, Lesser GPL, Apache License, Artistic License, BSD License, Mozilla Public License, Netscape Public License。這些 授權的共同原則就是「開放源碼」。然而各種授權的擁護群眾所滲雜的本位主義， 加㆖精英份子難以妥協的個性，使「開放源碼」陣營㆗的各個分支，意見紛歧甚 至互相對立。其㆗最甚者為 GNU GPL 和 BSD License 的擁護者。 1998 年，自由軟體社群企圖創造出㆒個新名詞 open source 來整合各方。他們組 成了㆒個非財團法㆟的組織，註冊㆒個標記，並設立網站。 open source 的定義共 有 9 條10，任何軟體只要符合這 9 條，就可稱呼自己為 open source 軟體。 9 GPL 的詳細內容見 http://www.opensource.org/licenses/gpl-license.html。 10見 http://www.opensource.org/docs/definition_plain.html。 1.4 HP 實作版本 The Annotated STL Sources 9 本書所採用的 GCC 套件是 Cygnus C++2.91 for Windows，又稱為 EGCS 1.1。GCC 和 Cygnus、EGCS 之間的關係常常令㆟混淆。 Cygnus 是㆒家商業公司，包裝並 出售自由軟體基金會所建構的軟體工具，並販售各種服務。他們協助晶片廠商調 整 GCC，在 GPL 的精神和規範㆘將 GCC 原始碼的修正公佈於世；他們提供 GCC 運作資訊，並提昇其運作效率，並因此成為 GCC 技術領域的最佳諮詢對象。 Cygnus 公司之於 GCC，㆞位就像 Red Hat（紅帽）公司之於 Linux。雖然 Cygnus 持續㆞ 技術回饋並經濟贊助 GCC，他們並不控制 GCC。GCC 的最終控制權仍然在 GCC 指導委員會（ GCC Steering Committee）身㆖。 當 GCC 的發展進入第㆓版時，為了統㆒事權， GCC 指導委員會開始考慮整合 1997 成立的 EGCS（Experimental/Enhanced GNU Compiler System）計劃。這個計劃採 用比較開放的開發態度，比標準 GCC 涵蓋更多優化技術和更多 C++ 語言性質。 實驗結果非常成功，因此 GCC 2.95 版反過頭接納了 EGCS 碼。從那個時候開始， GCC 決定採用和 EGCS ㆒樣的開發方式。自 1999 年起，EGCS 正式成為唯㆒的 GCC 官方維護機構。 1.4 HP 實作版本 HP 版本是所有 STL 實作版本的濫觴。每㆒個 HP STL 表頭檔都有如㆘㆒份聲明， 允許任何㆟免費使用、拷貝、修改、傳佈、販賣這份軟體及其說明文件，唯㆒需 要遵守的是，必須在所有檔案㆗加㆖ HP 的版本聲明和運用權限聲明。這種授權 並不屬於 GNU GPL 範疇，但屬於 open source 範疇。 /* * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 10 1.5 P. J. Plauger 實作版本 P.J. Plauger 版本由 P.J. Plauger 發展，本書後繼章節皆以 PJ STL 稱呼此㆒版本。 PJ 版本承繼 HP 版本，所以它的每㆒個表頭檔都有 HP 的版本聲明，此外還加㆖ P.J. Plauger 的個㆟版權聲明： /* * Copyright (c) 1995 by P.J. Plauger. ALL RIGHTS RESERVED. * Consult your license regarding permissions and restrictions. */ 這個產品既不屬於 open source 範疇，更不是 GNU GPL。這麼做是合法的，因為 HP 的版權聲明並非 GPL，並沒有強迫其衍生產品必須開放源碼。 P.J. Plauger 版本被 Visual C++ 採用，所以當然你可以在 Visual C++ 的 "include" 子目錄㆘（例如 C:\msdev\VC98\Include）找到所有 STL 表頭檔，但是不能公 開它或修改它或甚至販售它。以我個㆟的閱讀經驗及測試經驗，我對這個版本的 可讀性評價極低，主要因為其㆗的符號命名極不講究，例如： // TEMPLATE FUNCTION find template inline _II find(_II _F, _II _L, const _Ty& _V) {for (; _F != _L; ++_F) if (*_F == _V) break; return (_F); } 由於 Visual C++ 對 C++ 語言特性的支援不甚理想 11，導致 PJ 版本的表現也受影 響。 這項產品目前由 Dinkumware 12公司提供服務。 11 我個㆟對此有㆒份經驗整理：http://www.jjhou.com/qa-cpp-primer-27.txt 12 詳見 http://www.dinkumware.com 1.6 Rouge Wave 實作版本 The Annotated STL Sources 11 1.6 Rouge Wave 實作版本 RougeWave 版本由 Rouge Wave 公司開發，本書後繼章節皆以 RW STL 稱呼此㆒ 版本。 RW 版本承繼 HP 版本，所以它的每㆒個表頭檔都有 HP 的版本聲明，此 外還加㆖ Rouge Wave 的公司版權聲明： /********************************************************************* * (c) Copyright 1994, 1998 Rogue Wave Software, Inc. * ALL RIGHTS RESERVED * * The software and information contained herein are proprietary to, and * comprise valuable trade secrets of, Rogue Wave Software, Inc., which * intends to preserve as trade secrets such software and information. * This software is furnished pursuant to a written license agreement and * may be used, copied, transmitted, and stored only in accordance with * the terms of such license and with the inclusion of the above copyright * notice. This software and information or any other copies thereof may * not be provided or otherwise made available to any other person. * * Notwithstanding any other lease or license that may pertain to, or * accompany the delivery of, this computer software and information, the * rights of the Government regarding its use, reproduction and disclosure * are as set forth in Section 52.227-19 of the FARS Computer * Software-Restricted Rights clause. * * Use, duplication, or disclosure by the Government is subject to * restrictions as set forth in subparagraph (c)(1)(ii) of the Rights in * Technical Data and Computer Software clause at DFARS 252.227-7013. * Contractor/Manufacturer is Rogue Wave Software, Inc., * P.O. Box 2328, Corvallis, Oregon 97339. * * This computer software and information is distributed with "restricted * rights." Use, duplication or disclosure is subject to restrictions as * set forth in NASA FAR SUP 18-52.227-79 (April 1985) "Commercial * Computer Software-Restricted Rights (April 1985)." If the Clause at * 18-52.227-74 "Rights in Data General" is specified in the contract, * then the "Alternate III" clause applies. * *********************************************************************/ 這份產品既不屬於 open source 範疇，更不是 GNU GPL。這麼做是合法的，因為 HP 的版權聲明並非 GPL，並沒有強迫其衍生產品必須開放源碼。 Rouge Wave 版本被 C++Builder 採用，所以當然你可以在 C++Builder 的 "include" 子目錄㆘（例如 C:\Inprise\CBuilder4\Include）找到所有 STL 表頭檔，但是 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 12 不能公開它或修改它或甚至販售它。就我個㆟的閱讀經驗及測試經驗，我要說， 這個版本的可讀性還不錯，例如： template InputIterator find (InputIterator first, InputIterator last, const T& value) { while (first != last && *first != value) ++first; return first; } 但是像這個例子（ class vector 的內部定義），源碼㆗夾雜特殊的常數，對閱讀 的順暢性是㆒大考驗： #ifndef _RWSTD_NO_CLASS_PARTIAL_SPEC typedef _RW_STD::reverse_iterator const_reverse_iterator; typedef _RW_STD::reverse_iterator reverse_iterator; #else typedef _RW_STD::reverse_iterator const_reverse_iterator; typedef _RW_STD::reverse_iterator reverse_iterator; #endif 此外，㆖述定義方式也不夠清爽（請與稍後的 SGI STL 比較）。 C++Builder 對 C++ 語言特性的支援相當不錯，連帶㆞給予了 RW 版本正面的影 響。 1.7 STLport 實作版本 網絡㆖有個 STLport 站點，提供㆒個以 SGI STL 為藍本的高度可攜性實作版本。 本書附錄 C 列有孟岩先生所寫的㆒篇文章， 介紹 STLport 移植到 Visual C++ 和 C++ Builder 的經驗。SGI STL（㆘節介紹）屬於開放源碼組織的㆒員，所以 STLport 有權利那麼做。 1.8 SGI STL 實作版本 The Annotated STL Sources 13 1.8 SGI STL 實作版本 SGI 版本由 Silicon Graphics Computer Systems, Inc. 公司發展，承繼 HP 版本。所 以它的每㆒個表頭檔也都有 HP 的版本聲明。此外還加㆖ SGI 的公司版權聲明。 從其聲明可知，它屬於 open source 的㆒員，但不屬於 GNU GPL（廣泛開放授權） 。 /* * Copyright (c) 1996-1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ SGI 版本被 GCC 採用。你可以在 GCC 的 "include" 子目錄㆘（例如 C:\cygnus\ cygwin-b20\include\g++）找到所有 STL 表頭檔，並獲准自由公開它或修改它 或甚至販售它。就我個㆟的閱讀經驗及測試經驗，我要說，不論是在符號命名或 編程風格㆖，這個版本的可讀性非常高，例如： template InputIterator find(InputIterator first, InputIterator last, const T& value) { while (first != last && *first != value) ++first; return first; } ㆘面是對應於先前所列之 RW 版本的源碼實例（class vector 的內部定義），也 顯得十分乾淨： #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION typedef reverse_iterator const_reverse_iterator; typedef reverse_iterator reverse_iterator; #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ typedef reverse_iterator const_reverse_iterator; typedef reverse_iterator reverse_iterator; #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 14 GCC 對 C++ 語言特性的支援相當良好，在 C++ 主流編譯器㆗表現耀眼，連帶㆞ 給予了 SGI STL 正面影響。事實㆖ SGI STL 為了高度移植性，已經考量了不同編 譯器的不同的編譯能力，詳見 1.9.1 節。 SGI STL 也採用某些 GPL（廣泛性開放授權）檔案，例如 , , , 。這些檔案都 有如㆘的聲明： // This file is part of the GNU ANSI C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to the Free // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. // As a special exception, if you link this library with files // compiled with a GNU compiler to produce an executable, this does not cause // the resulting executable to be covered by the GNU General Public License. // This exception does not however invalidate any other reasons why // the executable file might be covered by the GNU General Public License. // Written by Jason Merrill based upon the specification in the 27 May 1994 // C++ working paper, ANSI document X3J16/94-0098. 1.8.1 GNU C++ headers 檔案分佈（按字母排序） 我手㆖的 Cygnus C++ 2.91 for Windows 安裝於磁碟目錄 C:\cygnus。圖 1-2 是這個 版本的所有表頭檔，置於 C:\cygnus\cygwin-b20\include\g++，共 128 個檔案， 773,042 bytes： algo.h algobase.h algorithm alloc.h builtinbuf.h bvector.h cassert cctype cerrno cfloat ciso646 climits 1.8 SGI STL 實作版本 The Annotated STL Sources 15 clocale cmath complex complex.h csetjmp csignal cstdarg cstddef cstdio cstdlib cstring ctime cwchar cwctype defalloc.h deque deque.h editbuf.h floatio.h fstream fstream.h function.h functional hashtable.h hash_map hash_map.h hash_set hash_set.h heap.h indstream.h iolibio.h iomanip iomanip.h iosfwd iostdio.h iostream iostream.h iostreamP.h istream.h iterator iterator.h libio.h libioP.h list list.h map map.h memory multimap.h multiset.h numeric ostream.h pair.h parsestream.h pfstream.h PlotFile.h procbuf.h pthread_alloc pthread_alloc.h queue rope rope.h ropeimpl.h set set.h SFile.h slist slist.h stack stack.h [std] stdexcept stdiostream.h stl.h stl_algo.h stl_algobase.h stl_alloc.h stl_bvector.h stl_config.h stl_construct.h stl_deque.h stl_function.h stl_hashtable.h stl_hash_fun.h stl_hash_map.h stl_hash_set.h stl_heap.h stl_iterator.h stl_list.h stl_map.h stl_multimap.h stl_multiset.h stl_numeric.h stl_pair.h stl_queue.h stl_raw_storage_iter.h stl_relops.h stl_rope.h stl_set.h stl_slist.h stl_stack.h stl_tempbuf.h stl_tree.h stl_uninitialized.h stl_vector.h stream.h streambuf.h strfile.h string strstream strstream.h tempbuf.h tree.h type_traits.h utility vector vector.h 子目錄 [std] 內有 8 個檔案， 70,669 bytes： bastring.cc bastring.h complext.cc complext.h dcomplex.h fcomplex.h ldcomplex.h straits.h 圖 1-2 Cygnus C++ 2.91 for Windows 的所有表頭檔 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 16 ㆘面是以檔案總管觀察 Cygnus C++ 的檔案分佈： 1.8.2 SGI STL 檔案分佈與簡介 ㆖㆒小節所呈現的眾多表頭檔㆗，概略可分為五組： z C++ 標準規範㆘的 C 表頭檔 （無副檔名），例如 cstdio, cstdlib, cstring… z C++ 標準程式庫㆗不屬於 STL 範疇者，例如 stream, string…相關檔案。 z STL 標準表頭檔（無副檔名） ，例如 vector, deque, list, map, algorithm, functional … z C++ Standard 定案前，HP 所規範的 STL 表頭檔，例如 vector.h, deque.h, list.h, map.h, algo.h, function.h … 1.8 SGI STL 實作版本 The Annotated STL Sources 17 z SGI STL 內部檔案（STL 真正實作於此），例如 stl_vector.h, stl_deque.h, stl_list.h, stl_map.h, stl_algo.h, stl_function.h … 其㆗前兩組不在本書討論範圍內。後㆔組表頭檔詳細列表於㆘。 (1) STL 標準表頭檔（無副檔名） 請注意，各檔案之「本書章節」欄如未列出章節號碼，表示其實際功能由「說明」 欄㆗的 stl_xxx 取代，因此實際剖析內容應觀察對應之 stl_xxx 檔案所在章 節，見稍後之第㆔列表。 檔名（按字母排序） bytes 本書章節 說明 algorithm 1,337 ref. deque 1,350 ref. functional 762 ref. hash_map 1,330 ref. hash_set 1,330 ref. iterator 1,350 ref. list 1,351 ref. map 1,329 ref. memory 2,340 3.2 定義 auto_ptr，並含入 , , , , , numeric 1,398 ref. pthread_alloc 9,817 N/A 與 Pthread 相關的 node allocator queue 1,475 ref. rope 920 ref. set 1,329 ref. slist 807 ref. stack 1,378 ref. utility 1,301 含入 , vector 1,379 ref. (2) C++ Standard 定案前，HP 規範的 STL 表頭檔（副檔名 .h） 請注意，各檔案之「本書章節」欄如未列出章節號碼，表示其實際功能由「說明」 欄㆗的 stl_xxx 取代，因此實際剖析內容應觀察對應之 stl_xxx 檔案所在章節， 見稍後之第㆔列表。 第 1 章 STL 概論與版本簡介 The Annotated STL Sources 18 檔名（按字母排序） bytes 本書章節 說明 complex.h 141 N/A 複數，含入 stl.h 305 含入 STL 標準表頭檔 , , , , ,