關聯(lián)式容器

C++STL包含了序列式容器和關聯(lián)式容器：

1. 序列式容器里面存儲的是元素本身，其底層為線性序列的數(shù)據(jù)結(jié)構(gòu)。比如：vector，list，deque，forward_list(C++11)等。
2. 關聯(lián)式容器里面存儲的是結(jié)構(gòu)的鍵值對，在數(shù)據(jù)檢索時比序列式容器效率更高。比如：set、map、unordered_set、unordered_map等。

注意： C++STL當中的stack、queue和priority_queue屬于容器適配器，它們默認使用的基礎容器分別是deque、deque和vector。

樹形結(jié)構(gòu)與哈希結(jié)構(gòu)

根據(jù)應用場景的不同，C++STL總共實現(xiàn)了兩種不同結(jié)構(gòu)的關聯(lián)式容器：樹型結(jié)構(gòu)和哈希結(jié)構(gòu)。

其中，樹型結(jié)構(gòu)容器中的元素是一個有序的序列，而哈希結(jié)構(gòu)容器中的元素是一個無序的序列。

鍵值對

鍵值對是用來表示具有一一對應關系的一種結(jié)構(gòu)，該結(jié)構(gòu)中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息。

比如我們?nèi)羰且⒁粋€英譯漢的字典，那么該字典中的英文單詞與其對應的中文含義就是一一對應的關系，即通過單詞可以找到與其對應的中文含義。

在SGI-STL中關于鍵值對的定義如下：

template <class T1, class T2>struct pair{	typedef T1 first_type;	typedef T2 second_type;	T1 first;	T2 second;	pair() : first(T1()), second(T2())	{}	pair(const T1& a, const T2& b) : first(a), second(b)	{}};

set

set的介紹

1. set是按照一定次序存儲元素的容器，使用set的迭代器遍歷set中的元素，可以得到有序序列。

2. set當中存儲元素的value都是唯一的，不可以重復，因此可以使用set進行去重。

3. 與map/multimap不同，map/multimap中存儲的是真正的鍵值對，set中只放value，但在底層實際存放的是由構(gòu)成的鍵值對，因此在set容器中插入元素時，只需要插入value即可，不需要構(gòu)造鍵值對。

4. set中的元素不能被修改，因為set在底層是用二叉搜索樹來實現(xiàn)的，若是對二叉搜索樹當中某個結(jié)點的值進行了修改，那么這棵樹將不再是二叉搜索樹。

5. 在內(nèi)部，set中的元素總是按照其內(nèi)部比較對象所指示的特定嚴格弱排序準則進行排序。當不傳入內(nèi)部比較對象時，set中的元素默認按照小于來比較。

6. set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但set容器允許根據(jù)順序?qū)υ剡M行直接迭代。

7. set在底層是用平衡搜索樹（紅黑樹）實現(xiàn)的，所以在set當中查找某個元素的時間復雜度為$logN$。

set的定義方式

方式一： 構(gòu)造一個某類型的空容器。

set<int> s1; //構(gòu)造int類型的空容器

方式二： 拷貝構(gòu)造某類型set容器的復制品。

set<int> s2(s1); //拷貝構(gòu)造int類型s1容器的復制品

方式三： 使用迭代器拷貝構(gòu)造某一段內(nèi)容。

string str("abcdef");set<char> s3(str.begin(), str.end()); //構(gòu)造string對象某段區(qū)間的復制品

方式四： 構(gòu)造一個某類型的空容器，比較方式指定為大于。

set < int, greater<int>> s4; //構(gòu)造int類型的空容器，比較方式指定為大于

set的使用

set當中常用的成員函數(shù)如下：

set當中迭代器相關函數(shù)如下：

使用示例：

#include #include using namespace std;int main(){	set<int> s;	//插入元素（去重）	s.insert(1);	s.insert(4);	s.insert(3);	s.insert(3);	s.insert(2);	s.insert(2);	s.insert(3);	//遍歷容器方式一（范圍for）	for (auto e : s)	{		cout << e << " ";	}	cout << endl; //1 2 3 4	//刪除元素方式一	s.erase(3);	//刪除元素方式二	set<int>::iterator pos = s.find(1); //查找值為1的元素	if (pos != s.end())	{		s.erase(pos);	}	//遍歷容器方式二（正向迭代器）	set<int>::iterator it = s.begin();	while (it != s.end())	{		cout << *it << " ";		it++;	}	cout << endl; //2 4	//容器中值為2的元素個數(shù)	cout << s.count(2) << endl; //1	//容器大小	cout << s.size() << endl; //2	//清空容器	s.clear();	//容器判空	cout << s.empty() << endl; //1	//交換兩個容器的數(shù)據(jù)	set<int> tmp{ 11, 22, 33, 44 };	s.swap(tmp);	//遍歷容器方式三（反向迭代器）	set<int>::reverse_iterator rit = s.rbegin();	while (rit != s.rend())	{		cout << *rit << " ";		rit++;	}	cout << endl; //44 33 22 11	return 0;}

multiset

multiset容器與set容器的底層實現(xiàn)一樣，都是平衡搜索樹（紅黑樹），其次，multiset容器和set容器所提供的成員函數(shù)的接口都是基本一致的，這里就不再列舉了，multiset容器和set容器的唯一區(qū)別就是，multiset允許鍵值冗余，即multiset容器當中存儲的元素是可以重復的。

#include #include using namespace std;int main(){	multiset<int> ms;	//插入元素（允許重復）	ms.insert(1);	ms.insert(4);	ms.insert(3);	ms.insert(3);	ms.insert(2);	ms.insert(2);	ms.insert(3);	for (auto e : ms)	{		cout << e << " ";	}	cout << endl; //1 2 2 3 3 3 4	return 0;}

由于multiset容器允許鍵值冗余，因此兩個容器中成員函數(shù)find和count的意義也有所不同：

map

map的介紹

1. map是關聯(lián)式容器，它按照特定的次序（按照key來比較）存儲鍵值key和值value組成的元素，使用map的迭代器遍歷map中的元素，可以得到有序序列。

2. 在map中，鍵值key通常用于排序和唯一地標識元素，而值value中存儲與此鍵值key關聯(lián)的內(nèi)容。鍵值key和值value的類型可能不同，并且在map的內(nèi)部，key與value通過成員類型value_type綁定在一起，并取別名為pair。

3. map容器中元素的鍵值key不能被修改，但是元素的值value可以被修改，因為map底層的二叉搜索樹是根據(jù)每個元素的鍵值key進行構(gòu)建的，而不是值value。

4. 在內(nèi)部，map中的元素總是按照鍵值key進行比較排序的。當不傳入內(nèi)部比較對象時，map中元素的鍵值key默認按照小于來比較。

5. map容器通過鍵值key訪問單個元素的速度通常比unordered_map容器慢，但map容器允許根據(jù)順序?qū)υ剡M行直接迭代。

6. map容器支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。

7. map在底層是用平衡搜索樹（紅黑樹）實現(xiàn)的，所以在map當中查找某個元素的時間復雜度為$logN$。

map的定義方式

方式一： 指定key和value的類型構(gòu)造一個空容器。

map<int, double> m1; //構(gòu)造一個key為int類型，value為double類型的空容器

方式二： 拷貝構(gòu)造某同類型容器的復制品。

map<int, double> m2(m1); //拷貝構(gòu)造key為int類型，value為double類型的m1容器的復制品

方式三： 使用迭代器拷貝構(gòu)造某一段內(nèi)容。

map<int, double> m3(m2.begin(), m2.end()); //使用迭代器拷貝構(gòu)造m2容器某段區(qū)間的復制品

方式四： 指定key和value的類型構(gòu)造一個空容器，key比較方式指定為大于。

map<int, double, greater<int>> m4; //構(gòu)造一個key為int類型，value為double類型的空容器，key比較方式指定為大于

map的插入

map的插入函數(shù)的函數(shù)原型如下：

pair<iterator,bool> insert (const value_type& val);

insert函數(shù)的參數(shù)

insert函數(shù)的參數(shù)顯示是value_type類型的，實際上value_type就是pair類型的別名：

typedef pair<const Key, T> value_type;

因此，我們向map容器插入元素時，需要用key和value構(gòu)造一個pair對象，然后再將pair對象作為參數(shù)傳入insert函數(shù)。

方式一： 構(gòu)造匿名對象插入。

#include #include #include using namespace std;int main(){	map<int, string> m;	//方式一：調(diào)用pair的構(gòu)造函數(shù)，構(gòu)造一個匿名對象插入	m.insert(pair<int, string>(2, "two"));	m.insert(pair<int, string>(1, "one"));	m.insert(pair<int, string>(3, "three"));	for (auto e : m)	{		cout << "<" << e.first << "," << e.second << ">" << " ";	}	cout << endl; //<1,one> <2,two> <3,three>	return 0;}

但是這種方式會使得我們的代碼變得很長，尤其是沒有直接展開命名空間的情況下，因此我們最常用的是方式二。

方式二： 調(diào)用make_pair函數(shù)模板插入。
在庫當中提供以下make_pair函數(shù)模板：

template <class T1, class T2>pair<T1, T2> make_pair(T1 x, T2 y){	return (pair<T1, T2>(x, y));}

我們只需向make_pair函數(shù)傳入key和value，該函數(shù)模板會根據(jù)傳入?yún)?shù)類型進行自動隱式推導，最終構(gòu)造并返回一個對應的pair對象。

#include #include #include using namespace std;int main(){	map<int, string> m;	//方式二：調(diào)用函數(shù)模板make_pair，構(gòu)造對象插入	m.insert(make_pair(2, "two"));	m.insert(make_pair(1, "one"));	m.insert(make_pair(3, "three"));	for (auto e : m)	{		cout << "<" << e.first << "," << e.second << ">" << " ";	}	cout << endl; //<1,one> <2,two> <3,three>	return 0;}

insert函數(shù)的返回值

insert函數(shù)的返回值也是一個pair對象，該pair對象中第一個成員的類型是map的迭代器類型，第二個成員的類型的一個bool類型，具體含義如下：

• 若待插入元素的鍵值key在map當中不存在，則insert函數(shù)插入成功，并返回插入后元素的迭代器和true。
• 若待插入元素的鍵值key在map當中已經(jīng)存在，則insert函數(shù)插入失敗，并返回map當中鍵值為key的元素的迭代器和false。

map的查找

map的查找函數(shù)的函數(shù)原型如下：

iterator find (const key_type& k);

map的查找函數(shù)是根據(jù)所給key值在map當中進行查找，若找到了，則返回對應元素的迭代器，若未找到，則返回容器中最后一個元素下一個位置的正向迭代器。

#include #include #include using namespace std;int main(){	map<int, string> m;	m.insert(make_pair(2, "two"));	m.insert(make_pair(1, "one"));	m.insert(make_pair(3, "three"));	//獲取key值為2的元素的迭代器	map<int, string>::iterator pos = m.find(2);	if (pos != m.end())	{		cout << pos->second << endl; //two	}	return 0;}

map的刪除

map的刪除函數(shù)的函數(shù)原型如下：

//刪除函數(shù)1size_type erase (const key_type& k);//刪除函數(shù)2void erase(iterator position);

也就是說，我們既可以根據(jù)key值刪除指定元素，也可以根據(jù)迭代器刪除指定元素，若是根據(jù)key值進行刪除，則返回實際刪除的元素個數(shù)。

#include #include #include using namespace std;int main(){	map<int, string> m;	m.insert(make_pair(2, "two"));	m.insert(make_pair(1, "one"));	m.insert(make_pair(3, "three"));	//方式一：根據(jù)key值進行刪除	m.erase(3);	//方式二：根據(jù)迭代器進行刪除	map<int, string>::iterator pos = m.find(2);	if (pos != m.end())	{		m.erase(pos);	}	return 0;}

map的[ ]運算符重載

map的[ ]運算符重載函數(shù)的函數(shù)原型如下：

mapped_type& operator[] (const key_type& k);

[ ]運算符重載函數(shù)的參數(shù)就是一個key值，而這個函數(shù)的返回值如下：

(*((this->insert(make_pair(k, mapped_type()))).first)).second

就這樣看著不太好理解，我們整理一下，實際上[ ]運算符重載實現(xiàn)的邏輯實際上就是以下三個步驟：

1. 調(diào)用insert函數(shù)插入鍵值對。
2. 拿出從insert函數(shù)獲取到的迭代器。
3. 返回該迭代器位置元素的值value。

對應分解代碼如下：

mapped_type& operator[] (const key_type& k){	//1、調(diào)用insert函數(shù)插入鍵值對	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));	//2、拿出從insert函數(shù)獲取到的迭代器	iterator it = ret.first;	//3、返回該迭代器位置元素的值value	return it->second;}

那么這個函數(shù)的價值體現(xiàn)在哪里呢？我們來看看下面這段代碼：

#include #include #include using namespace std;int main(){	map<int, string> m;	m.insert(make_pair(2, "two"));	m.insert(make_pair(1, "one"));	m.insert(make_pair(3, "three"));	m[2] = "dragon"; //修改key值為2的元素的value為dragon	m[6] = "six"; //插入鍵值對<6, "six">	for (auto e : m)	{		cout << "<" << e.first << "," << e.second << ">" << " ";	}	cout << endl; //<1,one> <2,dragon> <3,three> <6,six>	return 0;}

以代碼中的m[2] = "dragon"為例說明，通過[ ]運算符重載函數(shù)的三個步驟后，不管是調(diào)用insert函數(shù)插入的也好，是容器當中本來就已經(jīng)存在的也好，反正無論如何map容器當中都已經(jīng)有了一個key值為2的元素。而[ ]運算符重載函數(shù)的返回值就是這個key值為2的元素的value的引用，因此我們對該函數(shù)的返回值做修改，實際上就是對鍵值為2的元素的value做修改。

總結(jié)一下：

1. 如果k不在map中，則先插入鍵值對，然后返回該鍵值對中V對象的引用。
2. 如果k已經(jīng)在map中，則返回鍵值為k的元素對應的V對象的引用。

map的迭代器遍歷

map當中迭代器相關函數(shù)如下：

遍歷方式一： 用正向迭代器進行遍歷。

#include #include #include using namespace std;int main(){	map<int, string> m;	m.insert(make_pair(2, "two"));	m.insert(make_pair(1, "one"));	m.insert(make_pair(3, "three"));	//用正向迭代器進行遍歷	map<int, string>::iterator it = m.begin();	while (it != m
                 

                                                                                                                    
                         GPU云服務器
                                             
                         云服務器
                                                                                                                                                 
                                      
                     
                    
                                                                                               map集合的使用
                                                                                                           linux的安裝及使用
                                                                                                           變量及數(shù)據(jù)詳解
                                                                                                           python字符串的使用詳解