【C++】set、multiset與map、multimap的使用

一、關聯式容器
二、鍵值對
三、樹形結構的關聯式容器
- 3.1 set
- - 3.1.1 模板參數列表
  - 3.1.2 構造
  - 3.1.3 迭代器
  - 3.1.4 容量
  - 3.1.5 修改操作
- 3.2 multiset
- 3.3 map
- - 3.3.1 模板參數列表
  - 3.3.2 構造
  - 3.3.3 迭代器
  - 3.3.4 容量
  - 3.3.5 修改操作
  - 3.3.6 operator[]
- 3.4 multimap

一、關聯式容器

談到關聯式容器，先來說說序列式容器，以前學習的vector、list、deque等就是序列式容器，它們的特點是底層為線性序列的數據結構，存儲的是元素本身。關聯式容器也是存儲數據的，不同的是，里面存儲的是<key, value>結構的鍵值對，在數據檢索時比序列式容器效率更高。

二、鍵值對

鍵值對是用來表示一一對應關系的結構，該結構中一般只包含兩個成員變量key和value，key代表鍵值，value表示與key對應的信息，比如漢英互譯字典，查中文就可以找到對應的英文，是有對應關系的。

鍵值對的定義：

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)
{}
};

三、樹形結構的關聯式容器

STL總共有兩種結構的關聯式容器，分別是哈希結構和樹形結構。樹形結構主要有4種：set、multiset、map、multimap，它們的共同點是底層是平衡搜索樹即紅黑樹實現的，且容器中的元素是一個有序的序列。

3.1 set

特點：

遍歷set中的元素，可以得到一個有序序列，因為它的底層實現是紅黑樹，再底層是二叉搜索樹，遍歷方式是中序遍歷。
set中的元素不可以重復，因此可以用set去重。
與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放value，但在底層實際存放的是由<value, value>構成的鍵值對。
set中插入元素時，只需要插入value即可，不需要構造鍵值對。
set中的元素默認按照小于來比較。
set中查找某個元素，時間復雜度為：logN，即最多高度次。
在內部，set中的元素總是按照其內部比較對象(類型比較)所指示的特定嚴格弱排序準則進行排序。
set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對子集進行直接迭代。
set中的元素不允許修改，因為修改了其中的一個元素會改變內部的結構，從而影響有序性。
set在底層是用二叉搜索樹(紅黑樹)實現的。

3.1.1 模板參數列表

在這里插入圖片描述

T: set中存放元素的類型，實際在底層存儲<value, value>的鍵值對。
Compare：set中元素默認按照小于來比較。
Alloc：set中元素空間的管理方式，使用STL提供的空間配置器管理。

3.1.2 構造

1??構造空的set：

set<int> s;

2??用迭代器區間構造：

set<int> s1(s.begin(), s.end());

3??拷貝構造：

set<int> s2(s);

3.1.3 迭代器

1??begin+end
正向遍歷

	set<int> s;s.insert(1);s.insert(3);s.insert(3);s.insert(3);s.insert(5);s.insert(2);set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;

這里順便檢驗下是否去重且有序：
在這里插入圖片描述

2??rbegin+rend
與上面類似，只不過是反向遍歷

	set<int>::reverse_iterator rit = s.rbegin();while (rit != s.rend()){cout << *rit << " ";++rit;}cout << endl;

在這里插入圖片描述

3.1.4 容量

1??empty
判斷set是否為空，空返回true，否則返回true

	set<int> s;cout << s.empty() << endl;//1

2??size
返回set中有效元素的個數

set<int> s;
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(3);
s.insert(5);
s.insert(2);
cout << s.size() << endl;//4

3.1.5 修改操作

1??insert

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

在set中插入元素x，實際插入的是<x, x>構成的鍵值對，如果插入成功，返回<該元素在set中的位置，true>,如果插入失敗，說明x在set中已經存在，返回<x在set中的位置，false>。

set<int> s;
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto& e : s)
{cout << e << " ";
}
cout << endl;

在這里插入圖片描述

2??erase
刪除有三種方式：

刪除set中position位置上的元素

void erase ( iterator position )

set<int> s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto& e : s)
{cout << e << " ";
}
cout << endl;
set<int>::iterator pos = s.begin();
s.erase(pos);
for (auto& e : s)
{cout << e << " ";
}

在這里插入圖片描述

刪除set中值為x的元素，返回刪除的元素的個數

size_type erase ( const key_type& x )

set<int> s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto& e : s)
{cout << e << " ";
}
cout << endl;
s.erase(3);
for (auto& e : s)
{cout << e << " ";
}

在這里插入圖片描述

刪除set中[?rst, last)區間中的元素

void erase ( iterator ?rst, iterator last )

set<int> s;
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
for (auto& e : s)
{cout << e << " ";
}
cout << endl;
s.erase(s.begin(), s.end());
for (auto& e : s)
{cout << e << " ";
}

在這里插入圖片描述

3??swap
交換set中的元素

void swap ( set<Key,Compare,Allocator>& st );

	set<int> s1;s1.insert(1);s1.insert(3);s1.insert(5);for (auto& e : s1){cout << e << " ";//1 3 5}cout << endl;set<int> s2;s2.insert(7);s2.insert(8);s2.insert(6);for (auto& e : s2){cout << e << " "; //6 7 8}cout << endl;s2.swap(s1);for (auto& e : s1){cout << e << " ";//6 7 8}cout << endl;for (auto& e : s2){cout << e << " ";//1 3 5}

4??clear
將set中的元素清空

void clear ( )

set<int> s1;
s1.insert(1);
s1.insert(3);
s1.insert(5);
s1.clear();
for (auto& e : s1)
{cout << e << " ";// 空
}

5??find
找到了，返回set中值為x的元素的位置，如果每找到，返回最后一個元素的下一個位置

iterator ?nd ( const key_type& x ) const

set<int> s1;
s1.insert(1);
s1.insert(3);
s1.insert(5);
//s1.clear();
set<int>::iterator pos = s1.find(3);
if (pos != s1.end())cout << "找到了" << endl;//找到了
elsecout << "沒找到" << endl;

6??count
返回set中值為x的元素的個數，因為set是去重的，所以存在返回1，不存在返回0

size_type count ( const key_type& x ) const

set<int> s1;
s1.insert(1);
s1.insert(3);
s1.insert(5);
cout << s1.count(3) << endl;//1
cout << s1.count(33) << endl;//0

3.2 multiset

multiset與set的區別是存儲的元素可以重復

void test_set8()
{multiset<int> s;s.insert(1);s.insert(3);s.insert(3);s.insert(5);s.insert(5);s.insert(5);s.insert(2);for (auto& e : s){cout << e << " ";//1 2 3 3 5 5 5}
}

還有接口與set的不同，分別是find和count

set的find與multiset的find
set不能有重復元素，所以找到了返回該元素的位置；multiset有重復元素，找到了返回該元素的第一個的位置。找不到都是返回end()

multiset<int> s;
s.insert(1);
s.insert(3);
s.insert(3);
multiset<int>::iterator pos = s.find(3);//返回第一個3的位置
while (pos != s.end())
{cout << *pos << " ";// 3 3++pos;
}
cout << endl;
}

set的count與multiset的count
set沒有重復元素，所以存在的元素返回1，不存在返回0；multiset有重復元素，所以存在返回該元素的個數，不存在返回0

multiset<int> s;
s.insert(1);
s.insert(3);
s.insert(3);
s.insert(3);
s.insert(3);
cout << s.count(3) << endl;//4

3.3 map

與sert一樣，map可以使容器的元素有序且去重
特點：

map中的元素是鍵值對，由key和value組成
在map中，鍵值key通常用于排序和惟一地標識元素，而值value中存儲與此鍵值key關聯的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，為其取別名稱為pair—— typedef pair<const key, T> value_type;
在內部，map中的元素總是按照鍵值key進行比較排序的
map中的key是唯一的，并且不能修改
map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據順序對元素進行直接迭代(即對map中的元素進行迭代時，可以得到一個有序的序列)。
map支持下標訪問符，可以進行插入、查找和修改
map的底層為平衡搜索樹(紅黑樹)

3.3.1 模板參數列表

在這里插入圖片描述

key: 鍵值對中key的類型
T：鍵值對中value的類型
Compare: 比較器的類型，map中的元素是按照key來比較的，缺省情況下按照小于來比較，一般情況下(內置類型元素)該參數不需要傳遞，如果無法比較時(自定義類型)，需要用戶自己顯式傳遞比較規則(一般情況下按照函數指針或者仿函數來傳遞)
Alloc：通過空間配置器來申請底層空間，不需要用戶傳遞，除非用戶不想使用標準庫提供的空間配置器

3.3.2 構造

1??構造空的map

map<string, string> m;

2??用迭代器區間進行構造

map<string, string> m1(m.begin(), m.end());

3??拷貝構造

map<string, string> m2(m);

3.3.3 迭代器

1??begin和end
正向遍歷

map<string, string> m;
m.insert(pair<string, string>("sort", "排序"));
m.insert(pair<string, string>("apple", "蘋果"));
m.insert(pair<string, string>("left", "左邊"));
map<string, string>::iterator it = m.begin();
while (it != m.end())
{cout << *it << " ";//錯誤寫法，編譯報錯++it;
}

因為map的每個元素是鍵值對，由key和value組成，即pair，而且它們的類型不一定相同，所以要用 . 或者 -> 指向對應的成員

map<string, string> m;
m.insert(pair<string, string>("sort", "排序"));
m.insert(pair<string, string>("sort", "排序"));
m.insert(pair<string, string>("sort", "排序"));
m.insert(pair<string, string>("apple", "蘋果"));
m.insert(pair<string, string>("left", "左邊"));
map<string, string>::iterator it = m.begin();
while (it != m.end())
{//cout << (*it).first << "：" << (*it).second << endl;cout << it->first << "：" << it->second << endl;++it;
}

在這里插入圖片描述

2??rbegin和rend
反向遍歷

map<string, string>::reverse_iterator rit = m.rbegin();
while (rit != m.rend())
{//cout << (*rit).first << "：" << (*rit).second << endl;cout << rit->first << "：" << rit->second << endl;++rit;
}

在這里插入圖片描述

3.3.4 容量

1??empty
檢測map中的元素是否為空，是返回true，否則返回false

map<string, string> m;
cout << m.empty() << endl;//1

2??size
返回map中有效元素的個數

m.insert(pair<string, string>("left", "左邊"));
cout << m.size() << endl;//1

3.3.5 修改操作

1??insert

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

在map中插入的是鍵值對，返回值也是鍵值對，如果插入成功，則返回當前元素(鍵值對)的位置和true，插入失敗，則返回原來已有的元素的位置和false

插入的方式有三種寫法：

map<string, string> m;
m.insert(pair<string, string>("sort", "排序"));//C++98
m.insert(make_pair("apple", "蘋果"));//C++98
m.insert({ "left", "左邊" }); //C++11 多參數隱式類型轉換

在這里插入圖片描述

2??erase
刪除有3種方式，與set相同：

刪除position位置上的元素

void erase ( iterator position )

map<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("apple", "蘋果"));
m.insert(make_pair("left", "左邊"));
for (auto& e : m)
{cout << e.first << "：" << e.second << " ";
}
cout << endl;
map<string, string>::iterator pos = m.begin();
m.erase(pos);
for (auto& e : m)
{cout << e.first << "：" << e.second << " ";
}

在這里插入圖片描述

刪除鍵值為x的元素

size_type erase ( const key_type& x )

m.erase("sort");

在這里插入圖片描述

刪除[?rst, last)區間中的元素

void erase ( iterator ?rst, iterator last )

m.erase(m.begin(), m.end());

3??swap
交換兩個map中的元素

void swap ( map<Key,T,Compare,Allocator>& mp )

map<string, string> m1;
m1.insert(make_pair("sort", "排序"));
m1.insert(make_pair("apple", "蘋果"));
for (auto& e : m1)
{cout << e.first << "：" << e.second << " ";
}
map<string, string> m2;
m2.insert(make_pair("left", "左邊"));
m2.insert(make_pair("right", "右邊"));
for (auto& e : m2)
{cout << e.first << "：" << e.second << " ";
}
m2.swap(m1);
for (auto& e : m1)
{cout << e.first << "：" << e.second << " ";
}
for (auto& e : m2)
{cout << e.first << "：" << e.second << " ";
}

在這里插入圖片描述

4??clear
將map中的元素清空

void clear ( )

map<string, string> m;
m.insert(make_pair("sort", "排序"));
m.clear();
cout << m.empty() << endl;//1

5??find
查找key為x的元素，找到了返回該元素的迭代器，找不到返回end

iterator ?nd ( const key_type& x )

map<string, string> m;
m.insert(make_pair("sort", "排序"));
map<string, string>::iterator pos = m.find("sort");
if (pos != m.end())cout << "找到了" << endl;//找到了
elsecout << "沒找到" << endl;

6??count
返回key為x在map中的個數，由于map會去重，所以存在返回1，不存在返回0

size_type count ( const key_type& x ) const

map<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("sort", "排序"));
cout << m.count("sort") << endl;//1
cout << m.count("apple") << endl;//0

3.3.6 operator[]

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

該函數的參數是key，返回值是value。可以用來插入、查找、修改和計數。先來看看使用：

1??插入：如果key沒有重復，插入成功

map<string, string> m;
m.insert(make_pair("sort", "排序"));
m["left"];//插入
for (auto& e : m)
{cout << e.first << "：" << e.second << endl;
}

在這里插入圖片描述

2??查找：插入的key已經存在，查找到該key對應的value

map<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("apple", "蘋果"));
cout << m["apple"] << endl;//蘋果

3??修改：插入的key已經存在，同時右邊如下代碼所示，將該key對應的value修改

map<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("apple", "蘋果"));
m["sort"] = "排序的英文";
for (auto& e : m)
{cout << e.first << "：" << e.second << endl;
}

在這里插入圖片描述

4??插入+修改：插入key沒有重復，且右邊如下代碼所示，修改對應的value(其實是補上)

map<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("apple", "蘋果"));
m["left"] = "左邊";
for (auto& e : m)
{cout << e.first << "：" << e.second << endl;
}

在這里插入圖片描述

5??統計次數

map<string, int> m;
string arr[] = { "sort","sort" ,"apple" ,"apple", "banana","one" };
for (auto& e : arr)
{m[e]++;
}
for (auto& e : m)
{cout << e.first << "：" << e.second << " ";cout << endl;
}

在這里插入圖片描述

接下來看看operator[]是如何實現以上操作的：
在這里插入圖片描述

operator[]內部其實調用了insert函數
在這里插入圖片描述
我們再來看看insert函數：

回顧下，insert函數的要插入的數據類型是鍵值對

它的返回類型也是鍵值對，operator[]調用insert函數得到的返回值是迭代器，對迭代器解引用然后點訪問迭代器的第二個成員，最后返回該成員。

梳理下：
首先看operator[]調用insert函數，而insert里面的make_pair是(k, mapped_type())，也就是說key值是要輸入的，而value我們不寫編譯器幫我們默認構造出來，int類型是0。接著insert函數就要返回了，返回的是鍵值對，插入成功，返回該位置的迭代器和true；插入失敗，返回該位置的迭代器和false。.first，得到返回值的第一個成員，即迭代器。迭代器的本質是指針，指針指向的是該位置的key和對應的value，解引用指針，然后最后的 .second 得到是該迭代器的value，即插入的key對應的value

3.4 multimap

multimap與map的區別和multiset與set的區別相同，都能形成有序，但是multimap可以允許元素重復

multimap<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("left", "左邊"));
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("apple", "蘋果"));
m.insert(make_pair("apple", "蘋果"));
for (auto& e : m)
{cout << e.first << "：" << e.second << " ";cout << endl;
}

在這里插入圖片描述

還有find和count:

map的find與multimap的find
map返回該元素的迭代器，multimap返回該元素的第一個的迭代器

multimap<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("apple", "蘋果"));
multimap<string, string>::iterator pos = m.find("sort");
while (pos != m.end())
{cout << pos->first << "：" << pos->second << endl;++pos;
}

在這里插入圖片描述

map的count與multimap的count
map沒有重復元素，所以該元素存在返回1，不存在返回0；multimap可以有重復元素，存在返回該元素的個數，不存在返回0

multimap<string, string> m;
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("sort", "排序"));
m.insert(make_pair("apple", "蘋果"));
cout << m.count("sort") << endl;//2
cout << m.count("apple") << endl;//1
cout << m.count("left") << endl;//0