STL簡介

STL (標準模版庫，Standard Template Library)是當今每個從事C++編程的人需要掌握的一項不錯的技術。我覺得每一個初學STL的人應該花費一段時間來熟悉它，比如，學習STL時會有急劇升降的學習曲線，并且有一些命名是不太容易憑直覺就能夠記住的（也許是好記的名字已經(jīng)被用光了），然而如果一旦你掌握了STL，你就不會覺得頭痛了。和MFC相比，STL更加復雜和強大。
STL有以下的一些優(yōu)點：

可以方便容易地實現(xiàn)搜索數(shù)據(jù)或對數(shù)據(jù)排序等一系列的算法；

調試程序時更加安全和方便；

即使是人們用STL在UNIX平臺下寫的代碼你也可以很容易地理解（因為STL是跨平臺的）。

背景知識

寫這一部分是讓一些初學計算機的讀者在富有挑戰(zhàn)性的計算機科學領域有一個良好的開端，而不必費力地了解那無窮無盡的行話術語和沉悶的規(guī)則，在這里僅僅把那些行話和規(guī)則當作STLer們用于自娛的創(chuàng)造品吧。

使用代碼
本文使用的代碼在STL實踐中主要具有指導意義。

一些基礎概念的定義

模板（Template）——類（以及結構等各種數(shù)據(jù)類型和函數(shù)）的宏（macro）。有時叫做甜餅切割機（cookie cutter），正規(guī)的名稱應叫做范型（generic）——一個類的模板叫做范型類（generic class），而一個函數(shù)的模板也自然而然地被叫做范型函數(shù)（generic function）。
STL——標準模板庫，一些聰明人寫的一些模板，現(xiàn)在已成為每個人所使用的標準C++語言中的一部分。
容器（Container）——可容納一些數(shù)據(jù)的模板類。STL中有vector，set，map，multimap和deque等容器。
向量（Vector）——基本數(shù)組模板，這是一個容器。
游標（Iterator）——這是一個奇特的東西，它是一個指針，用來指向STL容器中的元素，也可以指向其它的元素。

Hello World程序

我愿意在我的黃金時間在這里寫下我的程序：一個hello world程序。這個程序將一個字符串傳送到一個字符向量中，然后每次顯示向量中的一個字符。向量就像是盛放變長數(shù)組的花園，大約所有STL容器中有一半是基于向量的，如果你掌握了這個程序，你便差不多掌握了整個STL的一半了。


//程序：vector演示一
//目的：理解STL中的向量

// #include "stdafx.h" -如果你使用預編譯的頭文件就包含這個頭文件
#include <vector>  // STL向量的頭文件。這里沒有".h"。
#include <iostream>  // 包含cout對象的頭文件。
using namespace std;  //保證在程序中可以使用std命名空間中的成員。

char* szHW = "Hello World";  
//這是一個字符數(shù)組，以”\0”結束。

int main(int argc, char* argv[])
{
  vector <char> vec;  //聲明一個字符向量vector (STL中的數(shù)組) 

  //為字符數(shù)組定義一個游標iterator。
  vector <char>::iterator vi;

  //初始化字符向量，對整個字符串進行循環(huán)，
  //用來把數(shù)據(jù)填放到字符向量中，直到遇到”\0”時結束。
  char* cptr = szHW;  // 將一個指針指向“Hello World”字符串
  while (*cptr != '\0')
  {  vec.push_back(*cptr);  cptr++;  }
  // push_back函數(shù)將數(shù)據(jù)放在向量的尾部。

  // 將向量中的字符一個個地顯示在控制臺
  for (vi=vec.begin(); vi!=vec.end(); vi++)  
  // 這是STL循環(huán)的規(guī)范化的開始——通常是 "!=" ， 而不是 "<"
  // 因為"<" 在一些容器中沒有定義。 
  // begin()返回向量起始元素的游標（iterator），end()返回向量末尾元素的游標（iterator）。
  {  cout << *vi;  }  // 使用運算符 “*” 將數(shù)據(jù)從游標指針中提取出來。
  cout << endl;  // 換行

  return 0;
}


push_back是將數(shù)據(jù)放入vector（向量）或deque（雙端隊列）的標準函數(shù)。Insert是一個與之類似的函數(shù)，然而它在所有容器中都可以使用，但是用法更加復雜。end()實際上是取末尾加一（取容器中末尾的前一個元素），以便讓循環(huán)正確運行——它返回的指針指向最靠近數(shù)組界限的數(shù)據(jù)。就像普通循環(huán)中的數(shù)組，比如for (i=0; i<6; i++) {ar[i] = i;} ——ar[6]是不存在的，在循環(huán)中不會達到這個元素，所以在循環(huán)中不會出現(xiàn)問題。

STL的煩惱之一——初始化

STL令人煩惱的地方是在它初始化的時候。STL中容器的初始化比C/C++數(shù)組初始化要麻煩的多。你只能一個元素一個元素地來，或者先初始化一個普通數(shù)組再通過轉化填放到容器中。我認為人們通?？梢赃@樣做：


//程序：初始化演示
//目的：為了說明STL中的向量是怎樣初始化的。

#include <cstring>  // <cstring>和<string.h>相同
#include <vector>
using namespace std;

int ar[10] = {  12, 45, 234, 64, 12, 35, 63, 23, 12, 55  };
char* str = "Hello World";

int main(int argc, char* argv[])
{
  vector <int> vec1(ar, ar+10);
  vector <char> vec2(str, str+strlen(str));
  return 0;
}



在編程中，有很多種方法來完成同樣的工作。另一種填充向量的方法是用更加熟悉的方括號，比如下面的程序：

//程序：vector演示二
//目的：理解帶有數(shù)組下標和方括號的STL向量

#include <cstring>
#include <vector>
#include <iostream>
using namespace std;

char* szHW = "Hello World";
int main(int argc, char* argv[])
{
  vector <char> vec(strlen(sHW)); //為向量分配內存空間
  int i, k = 0;
  char* cptr = szHW;
  while (*cptr != '\0')
  {  vec[k] = *cptr;  cptr++;  k++;  }
  for (i=0; i<vec.size(); i++)
  {  cout << vec[i];  }
  cout << endl;
  return 0;
}


這個例子更加清晰，但是對游標（iterator）的操作少了，并且定義了額外的整形數(shù)作為下標，而且，你必須清楚地在程序中說明為向量分配多少內存空間。

命名空間（Namespace）

與STL相關的概念是命名空間（namespace）。STL定義在std命名空間中。有3種方法聲明使用的命名空間：

1．用using關鍵字使用這個命名空間，在文件的頂部，但在聲明的頭文件下面加入：
using namespace std;
這對單個工程來說是最簡單也是最好的方法，這個方法可以把你的代碼限定在std命名空間中。

2．使用每一個模板前對每一個要使用的對象進行聲明（就像原形化）：
using std::cout;
using std::endl;
using std::flush;
using std::set;
using std::inserter;
盡管這樣寫有些冗長，但可以對記憶使用的函數(shù)比較有利，并且你可以容易地聲明并使用其他命名空間中的成員。

3．在每一次使用std命名空間中的模版時，使用std域標識符。比如：
typedef std::vector VEC_STR;
這種方法雖然寫起來比較冗長，但是是在混合使用多個命名空間時的最好方法。一些STL的狂熱者一直使用這種方法，并且把不使用這種方法的人視為異類。一些人會通過這種方法建立一些宏來簡化問題。

除此之外，你可以把using namespace std加入到任何域中，比如可以加入到函數(shù)的頭部或一個控制循環(huán)體中。

一些建議

為了避免在調試模式（debug mode）出現(xiàn)惱人的警告，使用下面的編譯器命令：

#pragma warning(disable: 4786)

另一條需要注意的是，你必須確保在兩個尖括號之間或尖括號和名字之間用空格隔開，因為是為了避免同“>>”移位運算符混淆。比如
vector <list<int>> veclis;
這樣寫會報錯，而這樣寫：
vector <list <int> > veclis;
就可以避免錯誤。


另一種容器——集合（set）

這是微軟幫助文檔中對集合（set）的解釋：“描述了一個控制變長元素序列的對象（注：set中的key和value是Key類型的，而map中的key和value是一個pair結構中的兩個分量）的模板類，每一個元素包含了一個排序鍵（sort key）和一個值(value)。對這個序列可以進行查找、插入、刪除序列中的任意一個元素，而完成這些操作的時間同這個序列中元素個數(shù)的對數(shù)成比例關系，并且當游標指向一個已刪除的元素時，刪除操作無效?！?而一個經(jīng)過更正的和更加實際的定義應該是：一個集合（set）是一個容器，它其中所包含的元素的值是唯一的。這在收集一個數(shù)據(jù)的具體值的時候是有用的。集合中的元素按一定的順序排列，并被作為集合中的實例。如果你需要一個鍵/值對（pair）來存儲數(shù)據(jù)，map是一個更好的選擇。一個集合通過一個鏈表來組織，在插入操作和刪除操作上比向量（vector）快，但查找或添加末尾的元素時會有些慢。
下面是一個例子：

//程序：set演示
//目的：理解STL中的集合（set）

#include <string>
#include <set>
#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
  set <string> strset;
  set <string>::iterator si;
  strset.insert("cantaloupes");
  strset.insert("apple");
  strset.insert("orange");
  strset.insert("banana");
  strset.insert("grapes");
  strset.insert("grapes");  
  for (si=strset.begin(); si!=strset.end(); si++)  
  {  cout << *si << " ";  }
  cout << endl;
  return 0;
}

// 輸出： apple banana cantaloupes grapes orange
//注意：輸出的集合中的元素是按字母大小順序排列的，而且每個值都不重復。


如果你感興趣的話，你可以將輸出循環(huán)用下面的代碼替換：

copy(strset.begin(), strset.end(), ostream_iterator<string>(cout, " "));

.集合（set）雖然更強大，但我個人認為它有些不清晰的地方而且更容易出錯，如果你明白了這一點，你會知道用集合（set）可以做什么。

所有的STL容器

容器（Container）的概念的出現(xiàn)早于模板（template），它原本是一個計算機科學領域中的一個重要概念，但在這里，它的概念和STL混合在一起了。下面是在STL中出現(xiàn)的7種容器：

vector（向量）——STL中標準而安全的數(shù)組。只能在vector 的“前面”增加數(shù)據(jù)。
deque（雙端隊列double-ended queue）——在功能上和vector相似，但是可以在前后兩端向其中添加數(shù)據(jù)。 
list（列表）——游標一次只可以移動一步。如果你對鏈表已經(jīng)很熟悉，那么STL中的list則是一個雙向鏈表（每個節(jié)點有指向前驅和指向后繼的兩個指針）。
set（集合）——包含了經(jīng)過排序了的數(shù)據(jù)，這些數(shù)據(jù)的值(value)必須是唯一的。
map（映射）——經(jīng)過排序了的二元組的集合，map中的每個元素都是由兩個值組成，其中的key（鍵值，一個map中的鍵值必須是唯一的）是在排序或搜索時使用，它的值可以在容器中重新獲?。欢硪粋€值是該元素關聯(lián)的數(shù)值。比如，除了可以ar[43] = "overripe"這樣找到一個數(shù)據(jù)，map還可以通過ar["banana"] = "overripe"這樣的方法找到一個數(shù)據(jù)。如果你想獲得其中的元素信息，通過輸入元素的全名就可以輕松實現(xiàn)。
multiset（多重集）——和集合（set）相似，然而其中的值不要求必須是唯一的（即可以有重復）。
multimap（多重映射）——和映射（map）相似，然而其中的鍵值不要求必須是唯一的（即可以有重復）。
注意：如果你閱讀微軟的幫助文檔，你會遇到對每種容器的效率的陳述。比如：log(n*n)的插入時間。除非你要處理大量的數(shù)據(jù)，否則這些時間的影響是可以忽略的。如果你發(fā)現(xiàn)你的程序有明顯的滯后感或者需要處理時間攸關（time critical）的事情，你可以去了解更多有關各種容器運行效率的話題。

怎樣在一個map中使用類？

Map是一個通過key（鍵）來獲得value(值)的模板類。
另一個問題是你希望在map中使用自己的類而不是已有的數(shù)據(jù)類型，比如現(xiàn)在已經(jīng)用過的int。建立一個“為模板準備的（template-ready）”類，你必須確保在該類中包含一些成員函數(shù)和重載操作符。下面的一些成員是必須的：

缺省的構造函數(shù)（通常為空）

拷貝構造函數(shù)

重載的”=”運算符
 
你應該重載盡可能多的運算符來滿足特定模板的需要，比如，如果你想定義一個類作為 map中的鍵（key），你必須重載相關的運算符。但在這里不對重載運算符做過多討論了。

//程序：映射自定義的類。
//目的：說明在map中怎樣使用自定義的類。

#include <string>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

class CStudent