STL set 常用操作簡(jiǎn)介

[size=4][color=Black]這是微軟幫助文檔中對(duì)集合（set）的解釋： “描述了一個(gè)控制變長(zhǎng)元素序列的對(duì)象（注：set中的key和value是Key類型的，而map中的key和value是一個(gè)pair結(jié)構(gòu)中的兩個(gè)分 量）的模板類，每一個(gè)元素包含了一個(gè)排序鍵（sort key）和一個(gè)值(value)。對(duì)這個(gè)序列可以進(jìn)行查找、插入、刪除序列中的任意一個(gè)元素，而完成這些操作的時(shí)間同這個(gè)序列中元素個(gè)數(shù)的對(duì)數(shù)成比例關(guān) 系，并且當(dāng)游標(biāo)指向一個(gè)已刪除的元素時(shí)，刪除操作無效。”
而一個(gè)經(jīng)過更正的和更加實(shí)際的定義應(yīng)該是：一個(gè)集合（set）是一個(gè)容器，它其中所包含的元素的值是唯一的。這在收集一個(gè)數(shù)據(jù)的具體值的時(shí)候是有用的。集 合中的元素按一定的順序排列，并被作為集合中的實(shí)例。如果你需要一個(gè)鍵/值對(duì)（pair）來存儲(chǔ)數(shù)據(jù)，map是一個(gè)更好的選擇。一個(gè)集合通過一個(gè)鏈表來組 織，在插入操作和刪除操作上比向量（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è)值都不重復(fù)。

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

copy(strset.begin(), strset.end(), ostream_iterator＜string＞(cout, " "));

.集合（set）雖然更強(qiáng)大，但我個(gè)人認(rèn)為它有些不清晰的地方而且更容易出錯(cuò)，如果你明白了這一點(diǎn)，你會(huì)知道用集合（set）可以做什么。

所有的STL容器

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

vector（向量）——STL中標(biāo)準(zhǔn)而安全的數(shù)組。只能在vector 的“前面”增加數(shù)據(jù)。

deque（雙端隊(duì)列double-ended queue）——在功能上和vector相似，但是可以在前后兩端向其中添加數(shù)據(jù)。

list（列表）——游標(biāo)一次只可以移動(dòng)一步。如果你對(duì)鏈表已經(jīng)很熟悉，那么STL中的list則是一個(gè)雙向鏈表（每個(gè)節(jié)點(diǎn)有指向前驅(qū)和指向后繼的兩個(gè)指針）。

set（集合）——包含了經(jīng)過排序了的數(shù)據(jù)，這些數(shù)據(jù)的值(value)必須是唯一的。

map（映射）——經(jīng)過排序了的二元組的集合，map中的每個(gè)元素都是由兩個(gè)值組成，其中的key（鍵值，一個(gè)map中的鍵值必須是唯一的）是在排序 或搜索時(shí)使用，它的值可以在容器中重新獲取；而另一個(gè)值是該元素關(guān)聯(lián)的數(shù)值。比如，除了可以ar[43] = "overripe"這樣找到一個(gè)數(shù)據(jù)，map還可以通過ar["banana"] = "overripe"這樣的方法找到一個(gè)數(shù)據(jù)。如果你想獲得其中的元素信息，通過輸入元素的全名就可以輕松實(shí)現(xiàn)。

multiset（多重集）——和集合（set）相似，然而其中的值不要求必須是唯一的（即可以有重復(fù)）。

multimap（多重映射）——和映射（map）相似，然而其中的鍵值不要求必須是唯一的（即可以有重復(fù)）。
注意：如果你閱讀微軟的幫助文檔，你會(huì)遇到對(duì)每種容器的效率的陳述。比如：log(n*n)的插入時(shí)間。除非你要處理大量的數(shù)據(jù)，否則這些時(shí)間的影響是可 以忽略的。如果你發(fā)現(xiàn)你的程序有明顯的滯后感或者需要處理時(shí)間攸關(guān)（time critical）的事情，你可以去了解更多有關(guān)各種容器運(yùn)行效率的話題。

怎樣在一個(gè)map中使用類？

Map是一個(gè)通過key（鍵）來獲得value(值)的模板類。

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

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

拷貝構(gòu)造函數(shù)

重載的”=”運(yùn)算符

你應(yīng)該重載盡可能多的運(yùn)算符來滿足特定模板的需要，比如，如果你想定義一個(gè)類作為 map中的鍵（key），你必須重載相關(guān)的運(yùn)算符。但在這里不對(duì)重載運(yùn)算符做過多討論了。

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

#include ＜string＞
#include ＜iostream＞
#include ＜vector＞
#include ＜map＞
using namespace std;

class CStudent
{
public :
int nStudentID;
int nAge;
public :
//缺省構(gòu)造函數(shù)——通常為空
CStudent() { }
// 完整的構(gòu)造函數(shù)
CStudent(int nSID, int nA) { nStudentID=nSID; nAge=nA; }
//拷貝構(gòu)造函數(shù)
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);

// 通過姓名來訪問Cstudent類中的成員
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

編寫代碼的一個(gè)習(xí)慣就是使用大寫字母和下劃線來命名數(shù)據(jù)類型。

ANSI / ISO字符串

ANSI/ISO字符串在STL容器中使用得很普遍。這是標(biāo)準(zhǔn)的字符串類，并得到了廣泛地提倡，然而在缺乏格式聲明的情況下就會(huì)出問題。你必須使用“＜＜”和輸入輸出流（iostream）代碼（如dec, width等）將字符串串聯(lián)起來。

可在必要的時(shí)候使用c_str()來重新獲得字符指針。[/color][/size]