STL--概述：
標準模板庫（StandardTemplateLibrary，STL），是C++程序設計語言標準模板庫。STL是由Alexander Stepanov、Meng Lee和David R Musser在惠普實驗室工作時所開發出來的。雖然它主要出現在C++中，但在被引入C++之前該技術就已經存在了很長的一段時間。
STL是所有C++編譯器和所有操作系統平臺都支持的一種庫，包含了很多在計算機科學領域里所常用的基本數據結構和基本算法，為廣大C++程序員提供了一個可擴展的應用框架，高度體現了軟件的可復用性。
對所有的編譯器來說，提供給C++程序設計者的接口都是一樣的。也就是說同一段STL代碼在不同編譯器和操作系統平臺上運行的結果都是相同的，但是底層實現可以是不同的，使用者并不需要了解它的底層實現。
使用STL的應用程序保證得到的實現在處理速度和內存利用方面都是高效的，因為STL設計者們已經考慮好了。
使用STL編寫的代碼更容易修改和閱讀。因為代碼更短，很多基礎工作代碼已經被組件化了；使用簡單，雖然內部實現很復雜。
STL是建立在模板函數和模板類基礎之上的功能強大的庫。
模板函數可以實現一般化的常用算法（如統計、排序、查找等）
模板類可以實現支持幾乎所有類型的容器，用來實現常用的數據結構（如鏈表、棧、隊列、平衡二叉樹等）
STL 頭文件一覽表：
|
頭文件
|
內容
|
頭文件
|
內容
|
|
<iterator>
|
迭代器
|
<vector>
|
向量
|
|
<utility>
|
輔助功能
|
<deque>
|
雙頭隊列
|
|
<memory>
|
內存管理
|
<list>
|
鏈表
|
|
<algorithm>
|
算法
|
<set>
|
集合與多重集合
|
|
<functional>
|
函數對象
|
<map>
|
映射與多重映射
|
|
<numeric>
|
數值運算
|
<stack>
|
棧
|
| |
|
<queue>
|
隊列與優先隊列
|
迭代器的定義和種類：
n迭代器(iterator)實際上是一種一般化的指針類型，是對指針類型的抽象。
n根據所支持操作的不同，迭代器被分為五大類：
¨輸出迭代器(input iterator)
¨輸入迭代器(output iterator)
¨前向迭代器(forward iterator)
¨雙向迭代器(bidirectional iterator)
¨隨機迭代器(random access iterator)
各種迭代器的功能
|
迭代器類型
|
輸出迭代器
|
輸入迭代器
|
前向迭代器
|
雙向迭代器
|
隨機迭代器
|
|
縮寫
|
Out
|
In
|
For
|
Bi
|
Ran
|
|
讀取
|
不支持
|
x = *p
|
x = *p
|
x = *p
|
x = *p
|
|
操作
|
不支持
|
p->x
|
p->x
|
p->x
|
p->x p[i]
|
|
寫入
|
*p = x
|
不支持
|
*p = x
|
*p = x
|
*p = x
|
|
迭代
|
++
|
++
|
++
|
++ --
|
++ -- + - += -=
|
|
比較
|
不支持
|
== !=
|
== !=
|
== !=
|
== != < > <= >=
|
更多關于迭代器的信息：
指針類型就是一種特殊的隨機迭代器類型。
對于一般的迭代器，這些功能都是通過操作符重載來實現的。
各種迭代器類型之間的關系：
輸出迭代器
隨機迭代器---》雙向迭代器---》向前迭代器---》
輸入迭代器
迭代器的作用
¨訪問元素
¨算法與容器之間的紐帶
與算法有關的知識：
算法(algorithm)
¨每個算法都是一個或者一組模板函數，用來完成一項特定的操作。
序列(sequence)
¨序列用兩個迭代器來描述，表示一組連續的元素；其中，第一個迭代器指向序列中的第一個元素，第二個迭代器指向序列最后一個元素的后一個位置。
函數對象(function object)
¨函數對象重載了函數調用操作符(operator ())，可以像普通函數一樣被使用。
謂詞(predicate)
¨返回值類型為bool的函數對象
常用函數對象：
STL在頭文件<functional>中提供了一些常用運算的函數對象。
|
類名
|
類型
|
作用
|
|
equal_to
|
雙目
|
arg1 == arg2
|
|
not_equal_to
|
雙目
|
arg1 != arg2
|
|
greater
|
雙目
|
arg1 > arg2
|
|
less
|
雙目
|
arg1 < arg2
|
|
greater_equal
|
雙目
|
arg1 >= arg2
|
|
less_equal
|
雙目
|
arg1 <= arg2
|
|
logical_and
|
雙目
|
arg1 && arg2
|
|
logical_or
|
雙目
|
arg1 || arg2
|
|
logical_not
|
單目
|
!arg
|
|
plus
|
雙目
|
arg1 + arg2
|
|
minus
|
雙目
|
arg1 - arg2
|
|
multiplies
|
雙目
|
arg1 * arg2
|
|
divides
|
雙目
|
arg1 / arg2
|
|
modulus
|
雙目
|
arg1 % arg2
|
|
negate
|
單目
|
-arg
|
STL算法一覽：
訪問元素類
¨for_each(), transform()
順序查找類
¨find(), find_if(), find_first_of(), adjacent_find(), search(), find_end(), search_n()
統計類
¨count(), count_if()
比較類
¨mismatch(), equal(), lexicographical_compare()
復制類
¨copy(), copy_backward()
交換類
¨swap(), iter_swap(), swap_ranges()
替換類
¨replace(), replace_if(), replace_copy(), replace_copy_if()
填充發生類
¨fill(), fill_n(), generate(), generate_n()
刪除類
¨remove(), remove_if(), remove_copy(), remove_copy_if
去重類
¨unique(), unique_copy()
反轉類
¨reverse(), reverse_copy()
旋轉類
¨rotate(), rotate_copy()
隨機打亂類
¨random_shuffle()
排序類
¨sort(), stable_sort(), partial_sort(), partial_sort_copy(), nth_element()
二分查找類
¨lower_bound(), upper_bound(), equal_range(), binary_search()
合并類
¨merge(), inplace_merge()
¨partition(), stable_partition()
集合運算類
¨includes(), set_union(), set_intersection(), set_difference(), set_symmetric_difference()
堆操作類
¨make_heap(), push_heap(), pop_heap(), sort_heap()
最大最小類
¨min(), max(), min_element(), max_element()
排列類
¨next_permutation(), prev_permutation()
數值運算類
¨accumulate(), inner_product(), partial_sum(), adjacent_difference()
常用STL容器
|
名稱
|
描述
|
所在頭文件
|
迭代器類型
|
|
vector
|
向量
|
<vector>
|
隨機迭代器
|
|
deque
|
雙頭隊列
|
<deque>
|
隨機迭代器
|
|
list
|
鏈表
|
<list>
|
雙向迭代器
|
|
stack
|
棧
|
<stack>
|
不提供迭代器
|
|
queue
|
隊列
|
<queue>
|
不提供迭代器
|
|
priority_queue
|
優先隊列
|
<queue>
|
不提供迭代器
|
|
set
|
集合
|
<set>
|
雙向迭代器
|
|
multiset
|
多重集合
|
<set>
|
雙向迭代器
|
|
map
|
映射
|
<map>
|
雙向迭代器
|
|
multimap
|
多重映射
|
<map>
|
雙向迭代器
|
一般容器：
vector deque list
容器適配器：
棧stack
隊列queue
優先隊列priority_queue
關聯容器：
元素有序
用平衡二叉樹實現
類名：set, multiset, map, multimap
分類
¨按元素構成來分
集合：元素本身就是關鍵字，直接參與排序
映射：元素由關鍵字和被映射的值構成，只有關鍵字參與排序
¨按關鍵字能否重復來分
普通：關鍵字不能重復
多重：關鍵字允許重復
關聯容器的特殊成員函數：
查找類
¨find()
¨lower_bound()
¨upper_bound()
¨equal_range()
復合類
¨operator []()
STL的優缺點：
優點：
¨降低編程復雜度
¨提高代碼的正確率
缺點：
¨編譯時會出各種錯誤
¨給動態調試增加難度
給幾條建議吧：
多用STL的算法
優先使用內置數組
多用靜態查錯
動態查錯時向屏幕輸出
小節：
STL以面向對象的程序設計和一般化編程為基礎，提供了功能強大的算法和容器，并通過迭代器把這兩部分有機地結合起來
留言列表
