Standard Template Library(STL)主要由兩種組件構成1：一是容器(container)，包括vector、list、set、map等；另一種組件是用以操作這些容器的所謂泛型演算法(generic algorithm)，包括find()、sort()、replace()、mer... ...
基礎知識
array與vector是連續存儲空間，可以用指針的算術運算實現對容器的訪問。list也是一個容器，不同的是，list的元素以一組指針相互鏈接(linked)：前向(forward)指針指向下一個(next)元素，後向(backward)指針指向上一個(preceding)元素。因此，指針的算術運算並不適用於list。解決這個問題的辦法是，在底層指針的行為之上提供一層抽象，取代程式原本的“指針直接操作”方式。我們把底層指針的處理通通放在此抽象層中，讓用戶無須直接面對指針操作，iterator（泛型指針）應運而生。
泛型演算法提供了許多可作用於容器類及類型上的操作。這些演算法之所以稱之為泛型(generic)，是因為它們和它們想要操作的元素類型無關。泛型算符系通過function template技術，達到“與操作對象的類型相互獨立”的目的。
利用istream_iterator從標準輸入設備讀取字元串，我們需要一對iterator：first和last，用來標示元素範圍。以下定義：
istream_iterator<string> is(cin);
為我們提供了一個first iterator，它將is定義為一個“綁至標準輸入設備”的istream_iterator。我們還需要一個last_iterator，表示“要讀取的最後一個元素的下一個位置”。對於不標準輸入設備而言，end-of-file即代表last。只要在定義istream_iterator時不為它指定istream對象，它便代表了end-of-file，例如：
istream_iterator<string> eof;所有容器的共通操作
equality（==）和inequality（!=）運算符，返回ture或false。
assignment（=）運算符，將某個容器複製給另一個容器。
empty()會在容器無任何元素時返回true，否則返回false。
size()返回容器內目前持有的元素個數。
clear()刪除所有元素
每個容器都提供了begin()和end()兩個函數，分別返回指向容器的第一個元素和最後一個元素的下一位置的iterator。通常我們在容器身上進行的迭代操作都是始於begin()而終於end()。
所有容器都提供insert ()用以插入元素，以及erase()用以刪除元素。
insert()將單一或某個範圍內的元素插入容器內。
erase()將容器內的單一元素或某個範圍內的元素刪除。
insert()和erase()的行為視容器本身為順序性(sequential)容器或關聯(associative)容器而有所不同。
順序性容器
順序性容器用來維護一組排列有序、類型相同的元素。這裡介紹三種主要的順序性容器vector、list和deque。
vector以一塊連續記憶體來存放元素。對vector進行隨機訪問(random access)——例如先取其第5個元素，再取其第17個元素，然後取其第九個元素——頗有效率；vector內的每個元素都被儲存在距離起始點的固定偏移位置上。如果將元素插入任意位置，而此位置不是vector的末端，那麼效率將很低，因為插入位置右端的每個元素，都必須被覆制一份，依次向右移動。同樣道理，刪除vector內最後一個元素以外的任意元素，同樣缺乏效率。
list系以雙向鏈接(double-linked)而非連續記憶體來存儲內容，因此可以執行前進或後退操作。list中的每個元素都包含三個欄位：value、back指針（指向前一個元素）、front指針（指向下一個元素）。在list的任意位置進行元素的插入或刪除操作，都頗具效率，因為list本身只需適當設定back指針和front指針即可。但是如果要對list進行隨機訪問，則效率不彰。
第三種順序性容器是所謂的deque(讀作deck)。deque的行為和vector頗為相似——都以連續記憶體儲存元素。和vector不同的是，deque對於最前端元素的插入和刪除操作，效率更高；末端元素亦同。（標準庫的queue便是以deque實現，也就是說，以deque作為底部儲存元素。）
定義順序性容器對象的方式有五種：
1. 產生空的容器：
list<string> slist; vector<int> ivec;2. 產生特定大小的容器。每個元素都以其預設值作為初值：
list<int> ilist(1024); vector<string> svec(32);3. 產生特定大小的容器，併為每個元素指定初值：
vector<int> ivec(10, -1); list<string> slist(16, "unassigned");4. 通過一對iterator產生容器，這對iterator用來標示一整組作為初值的元素的範圍：
int ia[8] = { 1,1,2,3,5,8,13,21 }; vector<int> fib(ia, ia + 8);5. 根據某個容器產生出新容器，複製原容器內的元素，作為新容器的初值：
list<string> slist; list<string> slist2(slist);
有兩個特別的操作函數，允許我們在容器的末尾進行插入和刪除操作：push_back()和pop_back()。push_back()會在末端插入一個元素，pop_back()會刪除最後一個元素。除此之外，list和deque（但不包括vector）還提供了push_front()和pop_front()，允許在容器前端進行插入和刪除操作。
關聯容器
關聯容器可以讓我們快速查找容器中的元素值。
map是一對對的key/value 組合。key用於查找，value用來標示我們要儲存或取出的數據。舉例來說，電話號碼即可以用map輕鬆表示，電話用戶名便是key，而value與電話號碼產生關聯。
set，僅包含有key。我們對它進行查詢操作，為的是判斷某值是否存在於其中。如果我們想要建立一組索引表，用來記錄出現於新聞、故事中的字眼，我們可能會希望將一些中性字眼如the、an、but排除掉。在讓某個字眼進入索引表之前，我們要先查詢exclude_word這麼一個set，如果這個字眼在裡面，我們便忽略它不再計較；反之則將它加入索引表。
練習題答案
練習3.1 寫一個讀取文本文件的程式，將文件中的每個單字存入map。map的key便是剛纔所說的單字，map的value則是該單字在文本文件中的出現次數。再定義一份由“排除字眼”組成的set，其中包含諸如a，an，or，the、and和but之類的單字。將某個單字放入map之前，先確定該單字並不在“排除字集”中。一旦文本文件讀取完畢，請顯示一份單字清單，並顯示各單字的出現次數。你甚至可以再加以擴展，在顯示單字之前，允許用戶查詢某個單字是否出現於文本文件中。
#include <map> #include <set> #include <string> #include <iostream> #include <fstream> using namespace std; void initialize_exclusion_set(set<string>&); void process_file(map<string, int>&, const set<string>&, ifstream&); void user_query(const map<string, int>&); void display_word_count(const map<string, int>&, ofstream&); int main() { ifstream ifile("1.txt"); ofstream ofile("2.txt"); if (!ifile || !ofile) { cerr << "Unable to open file -- bailling out!\n"; return -1; } set<string> exclude_set; initialize_exclusion_set(exclude_set); map<string, int> word_count; process_file(word_count, exclude_set, ifile); user_query(word_count); display_word_count(word_count, ofile); return 0; } void initialize_exclusion_set(set<string>& exs) { static string _excluded_words[25] = { "the","and","but","that","then","are","been", "can","a","could","did","for","of", "had","have","him","his","her","its","is", "were","which","when","with","would" }; exs.insert(_excluded_words, _excluded_words + 25); } void process_file(map<string, int>& word_count, const set<string>& exclude_set, ifstream& ifile) { string word; while (ifile >> word) { if (exclude_set.count(word)) continue; word_count[word]++; } } void user_query(const map<string, int>& word_map) { string search_word; cout << "Please enter a word to search( q to quit ): "; cin >> search_word; while (search_word.size() && search_word != "q") { map<string, int>::const_iterator it; if ((it = word_map.find(search_word)) != word_map.end()) cout << "Found! " << it->first << " occurs " << it->second << " times.\n"; else cout << search_word << " was not fount in text.\n"; cout << "\nAnother search?( q to quit) "; cin >> search_word; } } void display_word_count(const map<string, int>& word_map, ofstream& os) { map<string, int>::const_iterator iter = word_map.begin(), end_it = word_map.end(); while (iter != end_it) { os << iter->first << " ( " << iter->second << " ) " << endl; ++iter; } os << endl; }
練習3.2 讀取文本文件內容——和練習3.1一樣——並將內容儲存於vector。以字元串長度為依據，對vector進行排序。定義一個function object並傳給sort()；這一function object接受兩個字元串，當第一字元串的長度小於第二字元串的長度時，就返回true。最後，列印排序後的vector內容。
#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; class LessThan { public: bool operator()(const string& s1, const string& s2) { return s1.size() < s2.size(); } }; template <typename elemType> void display_vector(const vector<elemType>& vec, ostream& os = cout, int len = 8) { vector<elemType>::const_iterator iter = vec.begin(), end_it = vec.end(); int elem_cnt = 1; while (iter != end_it) { os << *iter++ << (!(elem_cnt ++ % len) ? '\n' : ' '); } os << endl; } int main() { ifstream ifile("1.txt"); ofstream ofile("2.txt"); if (!ifile || !ifile) { cerr << "Unable to open file -- bailing out!\n"; return -1; } vector<string> text; string word; while (ifile >> word) text.push_back(word); sort(text.begin(), text.end(), LessThan()); display_vector(text, ofile); return 0; }
練習3.3 定義一個map，以家庭姓氏為key，value則是家庭所有小孩的名字。另此map至少容納六筆數據。允許用戶根據姓氏來查詢，並得以列印map內的每一筆數據。
#include <iostream> #include <vector> #include <map> #include <fstream> #include <string> using namespace std; typedef vector<string> vstring; void populate_map(ifstream& nameFile, map<string, vstring>& families) { string textline; while (getline(nameFile, textline)) { string fam_name; vector<string> child; string::size_type pos = 0, prev_pos = 0, text_size = textline.size(); //找出以空格分隔開來的所有單字 while ((pos = textline.find_first_of(' ', pos)) != string::npos) //string::npos表示直到字元串結束 { //計算所有自字元串的終點 string::size_type end_pos = pos - prev_pos; //倘若prev_pos並未設置（或說其值為0），那麼讀到的單字就是家庭姓氏，否則我們就一一讀取孩子們的名字 if (!prev_pos) fam_name = textline.substr(prev_pos, end_pos); else child.push_back(textline.substr(prev_pos, end_pos)); prev_pos = ++pos; } //現在處理最後一個孩子的名字 if (prev_pos < text_size) child.push_back(textline.substr(prev_pos, pos - prev_pos)); if (!families.count(fam_name)) families[fam_name] = child; else cerr << "Oops! We already hava a " << fam_name << " family in our map!\n"; } } void display_map(const map<string, vstring>& families, ostream& os) { map<string, vstring>::const_iterator it = families.begin(), end_it = families.end(); while (it != end_it) { os << "The " << it->first << " family "; if (it->second.empty()) os << "has no children\n"; else { os << "has " << it->second.size() << " children: "; vector<string>::const_iterator iter = it->second.begin(), end_iter = it->second.end(); while (iter != end_iter) { os << *iter << " "; ++iter; } os << endl; } ++it; } } void query_map(const string& family, const map<string, vstring>& families) { map<string, vstring>::const_iterator it = families.find(family); if (it == families.end()) { cout << "Sorry. The " << family << " is not currently entered.\n"; return; } cout << "The " << family; if (!it->second.size()) cout << " has no children.\n"; else { cout << " has " << it->second.size() << " children: "; vector<string>::const_iterator iter = it->second.begin(), end_iter = it->second.end(); while (iter != end_iter) { cout << *iter << " "; ++iter; } cout << endl; } } int main() { map<string, vstring> families; ifstream nameFile("1.txt"); if (!nameFile) { cerr << "Unable to find the file. bailling out!\n"; return -1; } populate_map(nameFile, families); string family_name; while (1) { cout << "Please enter a family name or q to quit "; cin >> family_name; if (family_name == "q") break; query_map(family_name, families); } display_map(families, cout); return 0; }
練習3.4 編寫一個程式，利用istream_iterator從標準輸入設備讀取一連串整數。利用ostream_iterator將其中的奇數寫至某個文件，每個數值皆以空格分隔。再利用ostream_iterator將偶數寫到另一個文件，每個數值單獨放在一行中。
#include <iterator> #include <vector> #include <iostream> #include <algorithm> #include <fstream> using namespace std; class even_elem { public: bool operator()(int elem) { return elem % 2 ? false : true; } }; int main() { vector<int> input; istream_iterator<int> in(cin), eos; ofstream even_file("even.file.txt"), odd_file("odd_file.txt"); if (!even_file || !odd_file) { cerr << "arghh! unable to open the output files. bailling out!"; return -1; } //將ostream_iterator綁定至相應的ofstream對象上，第二參數代表每個元素輸出時的分隔符。 ostream_iterator<int> even_iter(even_file, "\n"), odd_iter(odd_file, " "); copy(in, eos, back_inserter(input)); vector<int>::iterator division = partition(input.begin(), input.end(), even_elem()); copy(input.begin(), division, even_iter); copy(division, input.end(), odd_iter); return 0; }end。
“有志者，事竟成，破釜沉舟，百二秦關終屬楚。”
