一、基本概念
1.1 泛型程序設計
C++ 語言的核心優勢之一就是便於軟件的重用，重用在兩個方面有體現：
面向對象的思想：繼承和多態，標准類庫 泛型程序設計(generic programming) 的思想： 模板機制，以及標准模板庫 STL
簡單地說就是使用模板的程序設計法。將一些常用的數據結構(比如鏈表，數組，二叉樹)和算法(比如排序，查找)寫成模板，以後則不論數據結構裡放的是什麼對象，算法針對什麼樣的對象，則都不必重新實現數據結構，重新編寫算法。
標准模板庫 (Standard Template Library) 就是一些常用數據結構和算法的模板的集合。有了STL，不必再寫大多的標准數據結構和算法，並且可獲得非常高的性能。
1.2 STL中基本的概念
容器： 可容納各種數據類型的通用數據結構,是類模板
迭代器： 可用於依次存取容器中元素，類似於指針
算法： 用來操作容器中的元素的函數模板
二、容器概述
容器指可以用於存放各種類型的數據( 基本類型的變量，對象等)的數據結構，都是類模版,分為三種：
順序容器
vector, deque,list 關聯容器
set, multiset, map, multimap 容器適配器
stack, queue, priority_queue
對象被插入容器中時，被插入的是對象的一個復制品。許多算法，比如排序，查找，要求對容器中的元素進行比較，有的容器本身就是排序的，所以，放入容器的對象所屬的類，往往還應該重載 == 和 < 運算符。
2.1 順序容器
順序容器並非指容器內的元素是排序的，元素的插入位置同元素的值無關。有vector，deque，list 三種。
vector 指動態數組。元素在內存連續存放。隨機存取任何元素都能在常數時間完成，在尾端增刪元素具有較佳的性能(大部分情況下是常數時間)。頭文件是< vector>
deque指雙向隊列。元素在內存連續存放。隨機存取任何元素都能在常數時間完成(但次於vector)。在兩端增刪元素具有較佳的性能(大部分情況下是常數時間)。
list指雙向鏈表。元素在內存不連續存放。在任何位置增刪元素都能在常數時間完成。 不支持隨機存取。
2.2 關聯容器
關聯容器有以下幾個特點：
元素是排序的 插入任何元素，都按相應的排序規則來確定其位置 在查找時具有非常好的性能 通常以平衡二叉樹方式實現， 插入和檢索的時間都是 O(log(N))
有兩類：
set/multiset(頭文件 < set>)
set 即集合。 set中不允許相同元素， multiset中允許存在相同的元素。
map/multimap(頭文件 < map>)
map與set的不同在於map中存放的元素有且僅有兩個成員變量，一個名為first,另一個名為second, map根據first值對元素進行從小到大排序，並可快速地根據first來檢索元素。
map同multimap的不同在於是否允許相同first值的元素
2.3 容器適配器
容器適配器有3類：stack、queue、priority_queue。
stack指棧。是項的有限序列，並滿足序列中被刪除、檢索和修改的項只能是最近插入序列的項(棧頂的項)。 後進先出。頭文件是< stack>
queue指隊列。插入只可以在尾部進行，刪除、檢索和修改只允許從頭部進行。 先進先出。頭文件是< queue>。
priority_queue指優先級隊列。最高優先級元素總是第一個出列。頭文件是< queue>。
2.4 成員函數
順序容器和關聯容器中都有的成員函數：
begin 返回指向容器中第一個元素的迭代器
end 返回指向容器中最後一個元素後面的位置的迭代器
rbegin 返回指向容器中最後一個元素的迭代器
rend 返回指向容器中第一個元素前面的位置的迭代器
erase 從容器中刪除一個或幾個元素
clear 從容器中刪除所有元素
front :返回容器中第一個元素的引用
back : 返回容器中最後一個元素的引用
push_back : 在容器末尾增加新元素
pop_back : 刪除容器末尾的元素
erase :刪除迭代器指向的元素(可能會使該迭代器失效)，或刪除一個區間，返回被刪除元素後面的那個元素的迭代器
三、迭代器
3.1 基本概念
迭代器用於指向順序容器和關聯容器中的元素，用法和指針類似，有const 和非 const兩種。通過迭代器可以讀取它指向的元素，通過非const迭代器還能修改其指向的元素。
定義一個容器類的迭代器的方法可以是：
容器類名::iterator 變量名;
容器類名::const_iterator 變量名;
訪問一個迭代器指向的元素：
* 迭代器變量名
迭代器上可以執行 ++ 操作, 以使其指向容器中的下一個元素。如果迭代器到達了容器中的最後一個元素的後面，此時再使用它，就會出錯，類似於使用NULL或未初始化的指針一樣。
3.2 迭代器示例
#include
#include
using namespace std;
int main() {
vector v; //一個存放int元素的數組，一開始裡面沒有元素
v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4);
vector::const_iterator i; //常量迭代器
for( i = v.begin();i != v.end();++i )
cout << * i << ",";
cout << endl;
vector::reverse_iterator r; //反向迭代器
for( r = v.rbegin();r != v.rend();r++ )
cout << * r << ",";
cout << endl;
vector::iterator j; //非常量迭代器
for( j = v.begin();j != v.end();j ++ )
* j = 100;
for( i = v.begin();i != v.end();i++ )
cout << * i << ",";
}
輸出：
1,2,3,4,
4,3,2,1,
100,100,100,100,
3.3 迭代器類別
3.3.1 雙向迭代器
若p和p1都是雙向迭代器，則可對p、 p1可進行以下操作：
++p, p++ 使p指向容器中下一個元素
--p, p-- 使p指向容器中上一個元素
* p 取p指向的元素
p = p1 賦值
p == p1 , p!= p1 判斷是否相等、不等
3.3.2 隨機訪問迭代器
若p和p1都是隨機訪問迭代器，則可對p、 p1可進行以下操作：
雙向迭代器的所有操作
p += i 將p向後移動i個元素
p -= i 將p向向前移動i個元素
p + i 值為: 指向 p 後面的第i個元素的迭代器
p - i 值為: 指向 p 前面的第i個元素的迭代器
p[i] 值為: p後面的第i個元素的引用
p < p1, p <= p1, p > p1, p>= p1
3.3.3 容器和迭代器
容器容器對應的迭代器
vector隨機訪問
deque隨機訪問
list雙向
set/multiset雙向
map/multimap雙向
stack不支持迭代器
queue不支持迭代器
priotiry_queue不支持迭代器
四、算法簡介
4.1 基本概念
算法就是一個個函數模板, 大多數在< algorithm> 中定義。
STL中提供能在各種容器中通用的算法，比如查找，排序等算法通過迭代器來操縱容器中的元素。許多算法可以對容器中的一個局部區間進行操作，因此需要兩個參數，一個是起始元素的迭代器，一個是終止元素的後面一個元素的迭代器。比如，排序和查找。有的算法返回一個迭代器。比如 find() 算法，在容器中查找一個元素，並返回一個指向該元素的迭代器。
算法可以處理容器，也可以處理普通數組。
4.2 算法示例
template
InIt find(InIt first, InIt last, const T& val);
first 和 last 這兩個參數都是容器的迭代器，它們給出了容器中的查找區間起點和終點[first,last)。區間的起點是位於查找范圍之中的，而終點不是。 find在[first,last)查找等於val的元素用 == 運算符判斷相等。
函數返回值是一個迭代器。如果找到，則該迭代器指向被找到的元素。如果找不到，則該迭代器等於last。
五、STL中“大”、“小”、“相等”的概念
5.1 基本概念
關聯容器內部的元素是從小到大排序的
有些算法要求其操作的區間是從小到大排序的，稱為“ 有序區間算法”
例： binary_search 有些算法會對區間進行從小到大排序，稱為“排序算法”
例： sort 還有一些其他算法會用到“大”，“小”的概念
使用STL時，在缺省的情況下，以下三個說法等價：
x比y小 表達式“ x < y”為真 y比x大
關於“相等”：
有時，“ x和y相等”等價於“ x==y為真”
例：在未排序的區間上進行的算法，如順序查找find
…… 有時“ x和y相等”等價於“ x小於y和y小於x同時為假”
例：
有序區間算法，如binary_search
關聯容器自身的成員函數find
……
5.2 程序示例
#include
#include
using namespace std;
class A
{
int v;
public:
A(int v):v(v) { }
bool operator<(const A &a) const{
cout<
輸出：
3<9?
2<9?
1<9?
9<1?
1
折半查找，最後找到1沒有更多的可以找了。比較9是否小於1，結果為假;比較1是否小於9，結果為假;這時候認為9==1，輸出1。
六、小結
STL 三個基本概念：容器、迭代器、算法 容器分為順序容器、關聯容器、容器適配器 順序容器分為vector(動態數組)、deque(雙向隊列)、list(雙向鏈表) 關聯容器分為set/multiset、map/multimap 容器適配器stack、queue、priority_queue 迭代器分為雙向迭代器、隨機訪問迭代器，不同的容器可以使用的迭代器類別不同 算法就是一個個函數模板, 大多數在< algorithm> 中定義 STL 中的”大“、”小“、”相等“等概念可以自己定義，可能和常規意義上的概念不同。
