關聯式容器

C++STL包含了序列式容器和關聯式容器：

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

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

樹形結構與哈希結構

根據應用場景的不同，C++STL總共實現了兩種不同結構的關聯式容器：樹型結構和哈希結構。

其中，樹型結構容器中的元素是一個有序的序列，而哈希結構容器中的元素是一個無序的序列。

鍵值對

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

比如我們若是要建立一個英譯漢的字典，那么該字典中的英文單詞與其對應的中文含義就是一一對應的關系，即通過單詞可以找到與其對應的中文含義。

在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，但在底層實際存放的是由構成的鍵值對，因此在set容器中插入元素時，只需要插入value即可，不需要構造鍵值對。

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

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

6. set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但set容器允許根據順序對元素進行直接迭代。

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

set的定義方式

方式一： 構造一個某類型的空容器。

set<int> s1; //構造int類型的空容器

方式二： 拷貝構造某類型set容器的復制品。

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

方式三： 使用迭代器拷貝構造某一段內容。

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

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

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

set的使用

set當中常用的成員函數如下：

set當中迭代器相關函數如下：

使用示例：

#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的元素個數	cout << s.count(2) << endl; //1	//容器大小	cout << s.size() << endl; //2	//清空容器	s.clear();	//容器判空	cout << s.empty() << endl; //1	//交換兩個容器的數據	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容器的底層實現一樣，都是平衡搜索樹（紅黑樹），其次，multiset容器和set容器所提供的成員函數的接口都是基本一致的，這里就不再列舉了，multiset容器和set容器的唯一區別就是，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容器允許鍵值冗余，因此兩個容器中成員函數find和count的意義也有所不同：

map

map的介紹

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

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

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

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

5. map容器通過鍵值key訪問單個元素的速度通常比unordered_map容器慢，但map容器允許根據順序對元素進行直接迭代。

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

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

map的定義方式

方式一： 指定key和value的類型構造一個空容器。

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

方式二： 拷貝構造某同類型容器的復制品。

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

方式三： 使用迭代器拷貝構造某一段內容。

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

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

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

map的插入

map的插入函數的函數原型如下：

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

insert函數的參數

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

typedef pair<const Key, T> value_type;

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

方式一： 構造匿名對象插入。

#include #include #include using namespace std;int main(){	map<int, string> m;	//方式一：調用pair的構造函數，構造一個匿名對象插入	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;}

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

方式二： 調用make_pair函數模板插入。
在庫當中提供以下make_pair函數模板：

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

我們只需向make_pair函數傳入key和value，該函數模板會根據傳入參數類型進行自動隱式推導，最終構造并返回一個對應的pair對象。

#include #include #include using namespace std;int main(){	map<int, string> m;	//方式二：調用函數模板make_pair，構造對象插入	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函數的返回值

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

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

map的查找

map的查找函數的函數原型如下：

iterator find (const key_type& k);

map的查找函數是根據所給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的刪除函數的函數原型如下：

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

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

#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值進行刪除	m.erase(3);	//方式二：根據迭代器進行刪除	map<int, string>::iterator pos = m.find(2);	if (pos != m.end())	{		m.erase(pos);	}	return 0;}

map的[ ]運算符重載

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

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

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

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

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

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

對應分解代碼如下：

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

那么這個函數的價值體現在哪里呢？我們來看看下面這段代碼：

#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"為例說明，通過[ ]運算符重載函數的三個步驟后，不管是調用insert函數插入的也好，是容器當中本來就已經存在的也好，反正無論如何map容器當中都已經有了一個key值為2的元素。而[ ]運算符重載函數的返回值就是這個key值為2的元素的value的引用，因此我們對該函數的返回值做修改，實際上就是對鍵值為2的元素的value做修改。

總結一下：

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

map的迭代器遍歷

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"));	//用正向迭代器進行遍歷	map<int, string>::iterator it = m.begin();	while (it != m
                 

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