STL實(shí)踐指南 Practical Guide to STL
作者：Jeff Bogan
翻譯：周翔
（接上篇）
另一種容器——集合（set）
這是微軟幫助文檔中對集合（set）的解釋?zhuān)?#8220;描述了一個(gè)控制變長(cháng)元素序列的對象（注：set中的key和value是Key類(lèi)型的，而map中的key和value是一個(gè)pair結構中的兩個(gè)分量）的模板類(lèi)，每一個(gè)元素包含了一個(gè)排序鍵（sort key）和一個(gè)值(value)。對這個(gè)序列可以進(jìn)行查找、插入、刪除序列中的任意一個(gè)元素，而完成這些操作的時(shí)間同這個(gè)序列中元素個(gè)數的對數成比例關(guān)系，并且當游標指向一個(gè)已刪除的元素時(shí)，刪除操作無(wú)效。”
而一個(gè)經(jīng)過(guò)更正的和更加實(shí)際的定義應該是：一個(gè)集合（set）是一個(gè)容器，它其中所包含的元素的值是唯一的。這在收集一個(gè)數據的具體值的時(shí)候是有用的。集合中的元素按一定的順序排列，并被作為集合中的實(shí)例。如果你需要一個(gè)鍵/值對（pair）來(lái)存儲數據，map是一個(gè)更好的選擇。一個(gè)集合通過(guò)一個(gè)鏈表來(lái)組織，在插入操作和刪除操作上比向量（vector）快，但查找或添加末尾的元素時(shí)會(huì )有些慢。
下面是一個(gè)例子：
//程序：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
//注意：輸出的集合中的元素是按字母大小順序排列的，而且每個(gè)值都不重復。
如果你感興趣的話(huà)，你可以將輸出循環(huán)用下面的代碼替換：
copy(strset.begin(), strset.end(), ostream_iterator<string>(cout, " "));
.集合（set）雖然更強大，但我個(gè)人認為它有些不清晰的地方而且更容易出錯，如果你明白了這一點(diǎn)，你會(huì )知道用集合（set）可以做什么。
所有的STL容器
容器（Container）的概念的出現早于模板（template），它原本是一個(gè)計算機科學(xué)領(lǐng)域中的一個(gè)重要概念，但在這里，它的概念和STL混合在一起了。下面是在STL中出現的7種容器：
vector（向量）——STL中標準而安全的數組。只能在vector 的“前面”增加數據。
deque（雙端隊列double-ended queue）——在功能上和vector相似，但是可以在前后兩端向其中添加數據。
list（列表）——游標一次只可以移動(dòng)一步。如果你對鏈表已經(jīng)很熟悉，那么STL中的list則是一個(gè)雙向鏈表（每個(gè)節點(diǎn)有指向前驅和指向后繼的兩個(gè)指針）。
set（集合）——包含了經(jīng)過(guò)排序了的數據，這些數據的值(value)必須是唯一的。
map（映射）——經(jīng)過(guò)排序了的二元組的集合，map中的每個(gè)元素都是由兩個(gè)值組成，其中的key（鍵值，一個(gè)map中的鍵值必須是唯一的）是在排序或搜索時(shí)使用，它的值可以在容器中重新獲??；而另一個(gè)值是該元素關(guān)聯(lián)的數值。比如，除了可以ar[43] = "overripe"這樣找到一個(gè)數據，map還可以通過(guò)ar["banana"] = "overripe"這樣的方法找到一個(gè)數據。如果你想獲得其中的元素信息，通過(guò)輸入元素的全名就可以輕松實(shí)現。
multiset（多重集）——和集合（set）相似，然而其中的值不要求必須是唯一的（即可以有重復）。
multimap（多重映射）——和映射（map）相似，然而其中的鍵值不要求必須是唯一的（即可以有重復）。
注意：如果你閱讀微軟的幫助文檔，你會(huì )遇到對每種容器的效率的陳述。比如：log(n*n)的插入時(shí)間。除非你要處理大量的數據，否則這些時(shí)間的影響是可以忽略的。如果你發(fā)現你的程序有明顯的滯后感或者需要處理時(shí)間攸關(guān)（time critical）的事情，你可以去了解更多有關(guān)各種容器運行效率的話(huà)題。
怎樣在一個(gè)map中使用類(lèi)？
Map是一個(gè)通過(guò)key（鍵）來(lái)獲得value(值)的模板類(lèi)。
另一個(gè)問(wèn)題是你希望在map中使用自己的類(lèi)而不是已有的數據類(lèi)型，比如現在已經(jīng)用過(guò)的int。建立一個(gè)“為模板準備的（template-ready）”類(lèi)，你必須確保在該類(lèi)中包含一些成員函數和重載操作符。下面的一些成員是必須的：
你應該重載盡可能多的運算符來(lái)滿(mǎn)足特定模板的需要，比如，如果你想定義一個(gè)類(lèi)作為 map中的鍵（key），你必須重載相關(guān)的運算符。但在這里不對重載運算符做過(guò)多討論了。
//程序：映射自定義的類(lèi)。
//目的：說(shuō)明在map中怎樣使用自定義的類(lèi)。
#include <string>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
class CStudent
{
public :
int nStudentID;
int nAge;
public :
//缺省構造函數——通常為空
CStudent() { }
// 完整的構造函數
CStudent(int nSID, int nA) { nStudentID=nSID; nAge=nA; }
//拷貝構造函數
CStudent(const CStudent& ob)
{ nStudentID=ob.nStudentID; nAge=ob.nAge; }
// 重載“=”
void operator = (const CStudent& ob)
{ nStudentID=ob.nStudentID; nAge=ob.nAge; }
};
int main(int argc, char* argv[])
{
map <string, CStudent> mapStudent;
mapStudent["Joe Lennon"] = CStudent(103547, 22);
mapStudent["Phil McCartney"] = CStudent(100723, 22);
mapStudent["Raoul Starr"] = CStudent(107350, 24);
mapStudent["Gordon Hamilton"] = CStudent(102330, 22);
// 通過(guò)姓名來(lái)訪(fǎng)問(wèn)Cstudent類(lèi)中的成員
cout << "The Student number for Joe Lennon is " <<
(mapStudent["Joe Lennon"].nStudentID) << endl;
return 0;
}
TYPEDEF
如果你喜歡使用typedef關(guān)鍵字，下面是個(gè)例子：
typedef set <int> SET_INT;
typedef SET_INT::iterator SET_INT_ITER
編寫(xiě)代碼的一個(gè)習慣就是使用大寫(xiě)字母和下劃線(xiàn)來(lái)命名數據類(lèi)型。
ANSI / ISO字符串
ANSI/ISO字符串在STL容器中使用得很普遍。這是標準的字符串類(lèi)，并得到了廣泛地提倡，然而在缺乏格式聲明的情況下就會(huì )出問(wèn)題。你必須使用“<<”和輸入輸出流（iostream）代碼（如dec, width等）將字符串串聯(lián)起來(lái)。
可在必要的時(shí)候使用c_str()來(lái)重新獲得字符指針。
（待續）
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=30374
聯(lián)系客服
