【STL】set, map, multiset, multimap的介紹及使用

@TOC

關聯式容器

樹形結構與哈希結構

鍵值對

set

set的定義方式

set的使用

multiset

map

map的介紹

map的定義方式

map的插入

insert函數的參數

insert函數的返回值

map的查找

map的刪除

map的[ ]運算符重載

map的迭代器遍歷

map的其他成員函數

multimap

關聯式容器

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

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

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

樹形結構與哈希結構

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

關聯式容器	容器結構	底層實現
set、map、multiset、multimap	樹形結構	平衡搜索樹（紅黑樹）
unordered_set、unordered_map、unordered_multiset、unordered_multimap	哈希結構	哈系數

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

鍵值對

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

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

考慮到“鍵值對”并不是普通類型數據，C++ STL?標準庫提供了?pair 類模板，其專門用來將 2 個普通元素 first 和 second（可以是 C++ 基本數據類型、結構體、類自定的類型）創建成一個新元素<first, second>。通過其構成的元素格式不難看出，使用 pair 類模板來創建“鍵值對”形式的元素，再合適不過。

注意，pair 類模板定義在<utility>頭文件中，所以在使用該類模板之前，需引入此頭文件。另外值得一提的是，在 C++ 11 標準之前，pair 類模板中提供了以下 3 種構造函數：

#1) 默認構造函數，即創建空的 pair 對象
pair();
#2) 直接使用 2 個元素初始化成 pair 對象
pair (const first_type& a, const second_type& b);
#3) 拷貝（復制）構造函數，即借助另一個 pair 對象，創建新的 pair 對象
template<class U, class V> pair (const pair<U,V>& pr);

在 C++ 11 標準中，在引入右值引用的基礎上，pair 類模板中又增添了如下 2 個構造函數：

#4) 移動構造函數
template<class U, class V> pair (pair<U,V>&& pr);
#5) 使用右值引用參數，創建 pair 對象
template<class U, class V> pair (U&& a, V&& b);

下面程序演示了以上幾種創建 pair 對象的方法：

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {// 調用構造函數 1，也就是默認構造函數pair <string, double> pair1;// 調用第 2 種構造函數pair <string, string> pair2("蘋果","apple");  // 調用拷貝構造函數pair <string, string> pair3(pair2);//調用移動構造函數pair <string, string> pair4(make_pair("蘋果", "apple"));// 調用第 5 種構造函數pair <string, string> pair5(string("蘋果"), string("apple"));  cout << "pair1: " << pair1.first << " " << pair1.second << endl;cout << "pair2: "<< pair2.first << " " << pair2.second << endl;cout << "pair3: " << pair3.first << " " << pair3.second << endl;cout << "pair4: " << pair4.first << " " << pair4.second << endl;cout << "pair5: " << pair5.first << " " << pair5.second << endl;return 0;
}

上面程序在創建 pair4 對象時，調用了 make_pair() 函數，它也是 <utility> 頭文件提供的，其功能是生成一個 pair 對象。因此，當我們將 make_pair() 函數的返回值（是一個臨時對象）作為參數傳遞給 pair() 構造函數時，其調用的是移動構造函數，而不是拷貝構造函數。

<utility>頭文件中除了提供創建 pair 對象的方法之外，還為 pair 對象重載了 <、<=、>、>=、==、!= 這 6 的運算符，其運算規則是：對于進行比較的 2 個 pair 對象，先比較 pair.first 元素的大小，如果相等則繼續比較 pair.second 元素的大小。

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;int main() {pair <string, int> pair1("蘋果", 20);pair <string, int> pair2("梨", 20);pair <string, int> pair3("柚子", 30);//pair1和pair2的key不同，value相同if (pair1 != pair2) {cout << "pair != pair2" << endl;}//pair2和pair3的key相同，value不同if (pair2 != pair3) {cout << "pair2 != pair3" << endl;}return 0;
}

最后需要指出的是，pair類模板還提供有一個 swap() 成員函數，能夠互換 2 個 pair 對象的鍵值對，其操作成功的前提是這 2 個 pair 對象的鍵和值的類型要相同。例如：

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {pair <string, int> pair1("pair", 10);                   pair <string, int> pair2("pair2", 20);//交換 pair1 和 pair2 的鍵值對pair1.swap(pair2);cout << "pair1: " << pair1.first << " " << pair1.second << endl;cout << "pair2: " << pair2.first << " " << pair2.second << endl;return 0;
}

set

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

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

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

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

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

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

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

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當中常用的成員函數如下：

成員函數	功能
insert	插入指定元素
erase	刪除指定元素
find	查找指定元素
size	獲取容器中元素的個數
empty	判斷容器是否為空
clear	清空容器
swap	交換兩個容器中的數據
count	獲取容器中指定元素值的元素個數

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

成員函數	功能
begin	獲取容器中第一個元素的正向迭代器
end	獲取容器中最后一個元素下一個位置的正向迭代器
rbegin	獲取容器中最后一個元素的反向迭代器
rend	獲取容器中第一個元素前一個位置的反向迭代器

使用示例：

#include <iostream>
#include <set>
#include <utility>
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 11return 0;
}

multiset

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

#include <iostream>
#include <set>
#include <utility>
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 4return 0;
}

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

成員函數find	功能
set對象	返回值為val的元素的迭代器
multiset對象	返回底層搜索樹中序的第一個值為val的元素的迭代器

成員函數count	功能
set對象	值為val的元素存在則返回1，不存在則返回0（find成員函數可代替）
multiset對象	返回值為val的元素個數（find成員函數不可代替）

map

map的介紹

map是關聯式容器，它按照特定的次序（按照key來比較）存儲鍵值key和值value組成的元素，使用map的迭代器遍歷map中的元素，可以得到有序序列。
在map中，鍵值key通常用于排序和唯一地標識元素，而值value中存儲與此鍵值key關聯的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，并取別名為pair。
map容器中元素的鍵值key不能被修改，但是元素的值value可以被修改，因為map底層的二叉搜索樹是根據每個元素的鍵值key進行構建的，而不是值value。
在內部，map中的元素總是按照鍵值key進行比較排序的。當不傳入內部比較對象時，map中元素的鍵值key默認按照小于來比較。
map容器通過鍵值key訪問單個元素的速度通常比unordered_map容器慢，但map容器允許根據順序對元素進行直接迭代。
map容器支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。
map在底層是用平衡搜索樹（紅黑樹）實現的，所以在map當中查找某個元素的時間復雜度為log(N)。

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 <iostream>
#include <string>
#include <map>
#include <utility>
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 <iostream>
#include <string>
#include <utility>
#include <map>
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 <iostream>
#include <string>
#include <utility>
#include <map>
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的刪除函數的函數原型如下：

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

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

#include <iostream>
#include <string>
#include <map>
#include <utility>
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

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

調用insert函數插入鍵值對。
拿出從insert函數獲取到的迭代器。
返回該迭代器位置元素的值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、返回該迭代器位置元素的值valuereturn it->second;
}

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

#include <iostream>
#include <utility>
#include <string>
#include <map>
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] = "蘋果"; //修改key值為2的元素的value為"蘋果"m[6] = "柚子"; //插入鍵值對<6, "柚子">for (auto e : m){cout << "<" << e.first << "," << e.second << ">" << " ";}cout << endl; //<1,one> <2,"蘋果"> <3,three> <6,"柚子">return 0;
}

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

總結一下：

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

map的迭代器遍歷

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

成員函數	功能
begin	獲取容器中第一個元素的正向迭代器
end	獲取容器中最后一個元素下一個位置的正向迭代器
rbegin	獲取容器中最后一個元素的反向迭代器
rend	獲取容器中第一個元素前一個位置的反向迭代器

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

//用正向迭代器進行遍歷map<int, string>::iterator it = m.begin();while (it != m.end()){cout << "<" << it->first << "," << it->second << ">" << " ";it++;}

遍歷方式二：?用反向迭代器進行遍歷。

//用反向迭代器進行遍歷map<int, string>::reverse_iterator rit = m.rbegin();while (rit != m.rend()){cout << "<" << rit->first << "," << rit->second << ">" << " ";rit++;}

遍歷方式三：?用范圍for進行遍歷。

//用范圍for進行遍歷for (auto e : m){cout << "<" << e.first << "," << e.second << ">" << " ";}

注意：?編譯器在編譯時會自動將范圍for替換為迭代器的形式，因此支持了迭代器實際上就支持了范圍for。

map的其他成員函數

除了上述成員函數外，set當中還有如下成員函數

成員函數	功能
size	獲取容器中元素的個數
empty	判斷容器是否為空
clear	清空容器
swap	交換兩個容器中的數據
count	獲取容器中指定key值的元素個數

使用方法和set差不多。

multimap

multimap容器與map容器的底層實現一樣，也都是平衡搜索樹（紅黑樹），其次，multimap容器和map容器所提供的成員函數的接口都是基本一致的，這里也就不再列舉了，multimap容器和map容器的區別與multiset容器和set容器的區別一樣，multimap允許鍵值冗余，即multimap容器當中存儲的元素是可以重復的。
由于multimap容器允許鍵值冗余，因此兩個容器中成員函數find和count的意義也有所不同：

成員函數find	功能
map對象	返回值為鍵值為key的元素的迭代器
multimap對象	返回底層搜索樹中序的第一個鍵值為key的元素的迭代器

成員函數count	功能
map對象	鍵值為key的元素存在則返回1，不存在則返回0（find成員函數可代替）
multimap對象	返回鍵值為key的元素個數（find成員函數不可代替）

其次，由于multimap容器允許鍵值冗余，調用[ ]運算符重載函數時，應該返回鍵值為key的哪一個元素的value的引用存在歧義，因此在multimap容器當中沒有實現[ ]運算符重載函數。