三、關(guān)聯(lián)容器

關(guān)聯(lián)容器與序列容器有著根本性的不同,，序列容器的元素是按照在容器中的位置來順序保存和訪問的,，而關(guān)聯(lián)容器的元素是按關(guān)鍵元素來保存和訪問的。關(guān)聯(lián)容器支持高效的關(guān)鍵字查找與訪問,。兩個(gè)主要的關(guān)聯(lián)容器類型是map與set,。

1.set

1.1 簡介：set里面每個(gè)元素只存有一個(gè)key,，它支持高效的關(guān)鍵字查詢操作。set對(duì)應(yīng)數(shù)學(xué)中的“集合”,。

1.2 特點(diǎn)：

• 儲(chǔ)存同一類型的數(shù)據(jù)元素（這點(diǎn)和vector,、queue等其他容器相同）
• 每個(gè)元素的值都唯一（沒有重復(fù)的元素）
• 根據(jù)元素的值自動(dòng)排列大小（有序性）
• 無法直接修改元素
• 高效的插入刪除操作

1.3 聲明：set<T> a

set<int> a;

1.4 常用函數(shù)

以下設(shè) set<T> a,其中a是T類型的set容器,。

1.6 插入元素：

• a.insert(x) :其中a為set<T>型容器,，x為T型變量

	set<int> a={0,1,2,9};
	a.insert(6);
	for(auto it = a.begin();it != a.end();it++)	cout << *it;//輸出01269

• a.insert(first,second):其中first為指向區(qū)間左側(cè)的迭代器，second為指向右側(cè)的迭代器,。作用是將first到second區(qū)間內(nèi)元素插入到a（左閉右開）,。

set<int> a = {0,1,2,9};
set<int> b = {3,4,5};
auto first = b.begin();
auto second = b.end();
a.insert(first,second);
for(auto it = a.begin();it != a.end();it++)	cout << *it;

插入元素會(huì)自動(dòng)插入到合適的位置，使整個(gè)集合有序

1.7 刪除元素：

• a.erase(x)：刪除建值為x的元素
• a.erase(first,second)：刪除first到second區(qū)間內(nèi)的元素（左閉右開）
• a.erase(iterator):刪除迭代器指向的元素
• set中的刪除操作是不進(jìn)行任何的錯(cuò)誤檢查的,，比如定位器的是否合法等等,，所以用的時(shí)候自己一定要注意。

1.8 lower_bound 和 upper_bound 迭代器：

• lower_bound（x1）:返回第一個(gè)不小于鍵參數(shù)x1的元素的迭代器
• upper_bound（x2）:返回最后一個(gè)大于鍵參數(shù)x2的元素的迭代器
• 由以上倆個(gè)函數(shù),，可以得到一個(gè)目標(biāo)區(qū)間,，即包含集合中從'x1'到'x2'的所有元素

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
	set<int> a = {0,1,2,5,9};
	auto it2 = a.lower_bound(2);//返回指向第一個(gè)大于等于x的元素的迭代器
	auto it = a.upper_bound(2);//返回指向第一個(gè)大于x的元素的迭代器
	cout << *it2 << endl;//輸出為2
	cout << *it << endl;//輸出為5
	return 0;
} 

1.9 set_union() 與 set_intersection()

set_union():對(duì)集合取并集

set_union()函數(shù)接受5個(gè)迭代器參數(shù)。前兩個(gè)迭代器定義了第一個(gè)集合的區(qū)間,，接下來的倆個(gè)迭代器定義了第二個(gè)集合的區(qū)間,，最后一個(gè)迭代器是輸出迭代器，指出將結(jié)果集合復(fù)制到什么位置,。例如：要將A與B的集合復(fù)制到C中,，可以這樣寫：

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
	set<int> A = {1,2,3}, B= {2,4,5},C;
	set_union(A.begin(),A.end(),B.begin(),B.end(),
			insert_iterator<set<int> >(C,C.begin()));
	for(auto it = C.begin();it != C.end();it++)
		cout << *it <<" ";
	return 0;
} 

注意：

其中第五個(gè)參數(shù)不能寫C.begin(),原因有兩個(gè)：首先，關(guān)聯(lián)集合將建看作常量,，所以C.begin()返回的迭代器是常量迭代器,，不能作為輸出迭代器(詳情請(qǐng)參考迭代器相關(guān)概念)。其次,，與copy()相同,，set_union()將覆蓋容器中已有的數(shù)據(jù)，并且要求容器用足夠的空間容納新信息,，而C不滿足,，因?yàn)樗强盏摹?/p>

解決方法：可以創(chuàng)建一個(gè)匿名的insert_iterator,將信息復(fù)制給C。如上述代碼所為,。另一種方法如下：

set_union(A.begin(),A.end(),B.begin(),B.end(),
		inserter(C,C.begin()));//調(diào)用inserter

set_intersection():對(duì)集合取交集,，它的接口與set_union()相同。

附：使用set_union()和set_intersection()還有另一種技巧,。由于需要五個(gè)迭代器,，看起來會(huì)很累贅和麻煩，如果多次使用會(huì)增加出錯(cuò)的幾率,，所以我們可以試試用宏定義的方法來簡化代碼,。如下：

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
int main()
{
	set<int> A = {1,2,3}, B= {2,4,5},C;
	set_union(ALL(A),ALL(B),INS(C));
	for(auto it = C.begin();it != C.end();it++)
		cout << *it <<" ";
	return 0;
} 

其中使用到了宏定義,。

1.10 set的幾個(gè)問題：

（1）為何map和set的插入刪除效率比用其他序列容器高？

因?yàn)閷?duì)于關(guān)聯(lián)容器來說,，不需要做內(nèi)存拷貝和內(nèi)存移動(dòng),。set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來存儲(chǔ)，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多,，指向父節(jié)點(diǎn)和子節(jié)點(diǎn),。因此插入的時(shí)候只需要稍做變換，把節(jié)點(diǎn)的指針指向新的節(jié)點(diǎn)就可以了,。刪除的時(shí)候類似,，稍做變換后把指向刪除節(jié)點(diǎn)的指針指向其他節(jié)點(diǎn)也OK了。這里的一切操作就是指針換來換去,，和內(nèi)存移動(dòng)沒有關(guān)系,。

（2）為何每次insert之后，以前保存的iterator不會(huì)失效,？

iterator這里就相當(dāng)于指向節(jié)點(diǎn)的指針,，內(nèi)存沒有變，指向內(nèi)存的指針怎么會(huì)失效呢(當(dāng)然被刪除的那個(gè)元素本身已經(jīng)失效了),。相對(duì)于vector來說，每一次刪除和插入,，指針都有可能失效,，調(diào)用push_back在尾部插入也是如此。因?yàn)闉榱吮ＷC內(nèi)部數(shù)據(jù)的連續(xù)存放,，iterator指向的那塊內(nèi)存在刪除和插入過程中可能已經(jīng)被其他內(nèi)存覆蓋或者內(nèi)存已經(jīng)被釋放了,。即使時(shí)push_back的時(shí)候，容器內(nèi)部空間可能不夠,，需要一塊新的更大的內(nèi)存,，只有把以前的內(nèi)存釋放，申請(qǐng)新的更大的內(nèi)存,，復(fù)制已有的數(shù)據(jù)元素到新的內(nèi)存,，最后把需要插入的元素放到最后，那么以前的內(nèi)存指針自然就不可用了,。特別時(shí)在和find等算法在一起使用的時(shí)候,，牢記這個(gè)原則：不要使用過期的iterator。

（3）當(dāng)數(shù)據(jù)元素增多時(shí),，set的插入和搜索速度變化如何,？

如果你知道log2的關(guān)系你應(yīng)該就徹底了解這個(gè)答案。在set中查找是使用二分查找,，也就是說,，如果有16個(gè)元素,，最多需要比較4次就能找到結(jié)果，有32個(gè)元素,，最多比較5次,。那么有10000個(gè)呢？最多比較的次數(shù)為log10000,，最多為14次,，如果是20000個(gè)元素呢？最多不過15次,?？匆娏税桑?dāng)數(shù)據(jù)量增大一倍的時(shí)候,，搜索次數(shù)只不過多了1次,，多了1/14的搜索時(shí)間而已。你明白這個(gè)道理后,，就可以安心往里面放入元素了,。

2.map

2.1 簡介：如果說set對(duì)應(yīng)數(shù)學(xué)中的“集合”，那么map對(duì)應(yīng)的就是“映射”,。map是一種key-value型容器,，其中key是關(guān)鍵字，起到索引作用,，而value就是其對(duì)應(yīng)的值,。與set不同的是它支持下標(biāo)訪問。頭文件是<map>

2.2 特點(diǎn)：

• 增加和刪除節(jié)點(diǎn)對(duì)迭代器的影響很小(高效的插入與刪除)
• 快速的查找（同set）
• 自動(dòng)建立key-value的對(duì)應(yīng),，key和value可以是任何你需要的類型
• 可以根據(jù)key修改value的記錄
• 支持下標(biāo)[]操作

2.3 聲明：map<T1,T2> m

其中T1是key類型,，T2是value類型，m就是一個(gè)T1-T2的key-value,。

map<string,int> m;//聲明一個(gè)key為string,，value為int的map型容器

下述代碼更清楚的解釋了map容器的特點(diǎn)：

#include<iostream>
#include<map> 
using namespace std;
int main()
{
	map<string,int> m;
	m["abc"] = 5;
	m["cdf"] = 6;
	m["b"] = 1;
	for(auto it = m.begin();it != m.end();it++)
		cout << it->first <<" " << it->second << endl;
	return 0;
} 

在上述代碼中，m容器被按照key的字典序升序排列了,，而且我們可以通過將key當(dāng)作索引來獲取value的值,。（同時(shí)這也是一種插入方法）

2.4 插入元素：

• 使用insert()函數(shù)插入pair類型的元素
• 使用下標(biāo)操作向map容器中插入元素

map<string,int> m;
	m.insert(make_pair("b",6));//insert插入
	m["a"] = 5;//使用下標(biāo)插入

2.5 刪除元素：

• erase(key):刪除鍵為key的元素
• erase(it):刪除迭代器it所指向的元素

#include<iostream>
#include<map> 
using namespace std;
int main()
{
	map<string,int> m;
	m.insert(make_pair("b",6));
	m["a"] = 5;
	m["c"] = 5;
	m["d"] = 5;
	m["e"] = 5;
	m.erase("d");
	auto pr = m.begin();
	m.erase(pr);
	for(auto it = m.begin();it != m.end();it++)
		cout << it->first <<" " << it->second << endl;
	return 0;
} 

2.6 map容器的遍歷：

• 使用迭代器遍歷（代碼如上）

注：使用迭代器遍歷map容器，其中每一個(gè)元素可以看成是pair類型的,，訪問第一個(gè)位置的key值可以用it->first訪問,，第二個(gè)位置value的值可以用it->second訪問，其中it是指向該元素的迭代器,。

2.7 常用函數(shù)：

下表中m為map類型的容器,，it為和m同類型的迭代器，key表示該類型的一個(gè)鍵,。

3.重要例題：

題目來自UVa12096

有一個(gè)專門為了集合運(yùn)算而設(shè)計(jì)的“集合棧”計(jì)算機(jī),。該機(jī)器有一個(gè)初始為空的棧,，并且支持以下操作：

• PUSH：空集“{}”入棧
• DUP：把當(dāng)前棧頂元素復(fù)制一份后再入棧
• UNION：出棧兩個(gè)集合，然后把二者的并集入棧
• INTERSECT：出棧兩個(gè)集合,，然后把二者交集入棧
• ADD：出棧兩個(gè)集合,，然后把先出棧的集合加入到后出棧的集合中，把結(jié)果入棧

每次操作后,，輸出棧頂集合的大?。丛貍€(gè)數(shù)）。例如,，棧頂元素是A={ {},，{ {} } }，,，下一個(gè)元素是B= { {},，  { { {} } }  }，則：

• UNION操作將得到{ {},，{ {} },，{ { {} } }  }，輸出3
• INTERSECT操作將得到{ {} },，輸出1
• ADD操作將得到{ {},{ { {} } } ,{ {},{ {} } }  },輸出3

輸出不超過2000個(gè)操作,，并且保證操作均能順利進(jìn)行（不需要對(duì)空棧執(zhí)行出棧操作）

#include<cstdio>
#include<iostream>
#include<algorithm>//set_union等函數(shù)定義在這里 
#include<vector>
#include<set>
#include<map>
#include<stack>
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin()) //注意宏的括號(hào)和inserter 
using namespace std;
typedef set<int> Set;
map<Set,int> IDCache;
vector<Set> setCache;
int t,n;
char cmd[10];
int getID(Set s){
    if(IDCache.count(s))return IDCache[s];
    setCache.push_back(s);  //將新集合加入Setcache 
    return IDCache[s]=setCache.size()-1;//將ID加入map ，同時(shí)返回新分配的ID值 
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
//            setCache.clear(); 
        stack<int> s;
        while(n--){
            scanf(" %s",&cmd);
            if(cmd[0]=='P')s.push(getID(Set()));
            else if(cmd[0]=='D')s.push(s.top());
            else{
                Set s1=setCache[s.top()];s.pop();
                Set s2=setCache[s.top()];s.pop();
                Set x;
                if(cmd[0]=='U')set_union(ALL(s1),ALL(s2),INS(x));
                if(cmd[0]=='I')set_intersection(ALL(s1),ALL(s2),INS(x));
                if(cmd[0]=='A'){ x=s2; x.insert(getID(s1)); }
                s.push(getID(x));
            }
            printf("%d\n",setCache[s.top()].size());
        }
        puts("***");
    }
}

代碼出自：《算法競(jìng)賽入門經(jīng)典（第二版）》——?jiǎng)⑷昙?/p>