C++ map和set的使用

0.前言

1.關聯式容器

2.鍵值對

3.樹形結構的關聯式容器

3.1樹形結構的特點

3.2樹形結構在關聯式容器中的應用

4.set

4.1概念與性質

4.2使用

5.multiset

5.1概念與性質

5.2使用

6.map

6.1概念與性質

6.2使用

7.multimap

7.1概念與性質

7.2使用

8.小結

（圖像由AI生成）?

0.前言

在C++編程中，標準模板庫（STL）提供了許多有用的容器，如vector、list、deque、forward_list等，這些容器被統稱為序列式容器，因為它們底層是線性序列的數據結構，存儲的是元素本身。然而，STL中還有一類非常重要的容器，它們通過鍵值對（key-value pairs）來組織數據，稱為關聯式容器。本文將介紹關聯式容器中的set、multiset、map和multimap。

1.關聯式容器

關聯式容器不同于序列式容器，它們通過鍵值對的形式來存儲數據。關聯式容器根據鍵（key）來快速檢索對應的值（value）。與序列式容器存儲元素本身不同，關聯式容器更關注元素之間的關系，通常使用某種樹形結構（如紅黑樹）來高效地管理數據。這類容器在插入、刪除和查找操作上具有對數時間復雜度。

常見的關聯式容器包括：

set：存儲唯一元素的集合。
multiset：允許重復元素的集合。
map：存儲鍵值對，鍵唯一。
multimap：存儲鍵值對，鍵允許重復。

2.鍵值對

鍵值對是關聯式容器的核心概念。一個鍵值對由兩個部分組成：鍵（key）和值（value）。在關聯式容器中，鍵用于唯一標識一個元素，值則是與該鍵關聯的數據。鍵和值的這種關聯關系使得我們可以通過鍵快速查找到對應的值。

在set和multiset中，鍵和值是相同的，實際上只存儲鍵，而沒有單獨的值。在這些容器中，每個元素即為鍵本身。

在map和multimap中，鍵和值是分開的。鍵用于唯一標識每個元素，而值是與鍵相關聯的數據。例如，在一個map容器中，我們可以通過鍵查找對應的值，就像字典一樣。

以下是鍵值對的一些特點和優勢：

唯一性：在map中，每個鍵是唯一的，這保證了查找操作的準確性。而在multimap中，雖然允許鍵重復，但每個鍵值對仍然是唯一的。
快速查找：關聯式容器通常通過某種平衡樹結構（如紅黑樹）實現，能夠在對數時間內完成查找操作。
自動排序：鍵值對按照鍵自動排序，這使得關聯式容器不僅可以高效地進行查找，還可以方便地進行范圍查詢和遍歷。

鍵值對的這種結構使得關聯式容器在處理需要快速查找和排序的數據時非常有用。接下來，我們將詳細介紹各個關聯式容器的具體概念與使用方法。

3.樹形結構的關聯式容器

樹形結構是實現關聯式容器的核心技術之一。關聯式容器通常使用平衡樹（如紅黑樹）來管理內部數據。這種樹形結構能夠保持數據的有序性，同時保證插入、刪除和查找操作的高效性。

3.1樹形結構的特點

自動排序：樹形結構中的元素按照鍵值自動排序，這使得容器內的數據始終保持有序。對于set和multiset，元素本身作為鍵進行排序；對于map和multimap，元素按照鍵排序，值與鍵關聯。
平衡性：平衡樹通過自我調整，保持樹的高度盡可能小，從而保證了操作的效率。紅黑樹是一種常見的平衡樹，它在最壞情況下仍能保證對數時間復雜度的操作性能。
高效操作：由于樹形結構的特性，插入、刪除和查找操作的時間復雜度為O(log n)，這是通過線性搜索無法達到的。

3.2樹形結構在關聯式容器中的應用

set和multiset：使用樹形結構來存儲唯一或允許重復的元素，并保持它們的有序性。
map和multimap：利用樹形結構存儲鍵值對，通過鍵來組織和查找數據，保證鍵的唯一性或允許重復鍵。

4.set

4.1概念與性質

有序存儲：set是按照一定次序存儲元素的容器。在set中，元素始終保持有序。
唯一性：在set中，元素的值（value）也標識它（value就是key，類型為T），并且每個value必須是唯一的。set中的元素不能在容器中修改（元素總是const），但是可以從容器中插入或刪除它們。
內部排序：在內部，set中的元素總是按照其內部比較對象（類型比較）所指示的特定嚴格弱排序準則進行排序。
訪問速度：set容器通過key訪問單個元素的速度通常比unordered_set容器慢，但它們允許根據順序對子集進行直接迭代。
實現方式：set在底層是用二叉搜索樹（紅黑樹）實現的。

注意：

與map/multimap不同，map/multimap中存儲的是真正的鍵值對<key, value>，set中只放value，但在底層實際存放的是由<value, value>構成的鍵值對。
set中插入元素時，只需要插入value即可，不需要構造鍵值對。
set中的元素不可以重復（因此可以使用set進行去重）。
使用set的迭代器遍歷set中的元素，可以得到有序序列。
set中的元素默認按照小于來比較。
set中查找某個元素，時間復雜度為O(log n)。
set中的元素不允許修改。這是因為修改元素會破壞set的有序性和唯一性。
set的底層使用二叉搜索樹（紅黑樹）來實現。

4.2使用

以下是一些示例代碼，展示了set的主要功能：

插入和遍歷元素

#include <iostream>
#include <set>int main() {std::set<int> mySet;// 插入元素mySet.insert(10);mySet.insert(5);mySet.insert(20);mySet.insert(10); // 重復元素，不會插入// 遍歷元素for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

查找元素

#include <iostream>
#include <set>int main() {std::set<int> mySet = {10, 5, 20};// 查找元素auto it = mySet.find(10);if (it != mySet.end()) {std::cout << "Found: " << *it << std::endl;} else {std::cout << "Not Found" << std::endl;}return 0;
}

刪除元素

#include <iostream>
#include <set>int main() {std::set<int> mySet = {10, 5, 20};// 刪除元素mySet.erase(10);// 遍歷元素for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

?使用自定義比較函數

#include <iostream>
#include <set>struct Compare {bool operator()(const int& a, const int& b) const {return a > b; // 降序排列}
};int main() {std::set<int, Compare> mySet = {10, 5, 20};// 遍歷元素for (const auto& elem : mySet) {std::cout << elem << " ";}std::cout << std::endl;return 0;
}

5.multiset

5.1概念與性質

有序存儲：multiset是按照特定順序存儲元素的容器，其中元素是可以重復的。
元素識別：在multiset中，元素的值（value）也會識別它（因為multiset中本身存儲的就是<value, value>組成的鍵值對，因此value本身就是key，key就是value，類型為T）。multiset元素的值不能在容器中進行修改（因為元素總是const的），但可以從容器中插入或刪除。
排序規則：在內部，multiset中的元素總是按照其內部比較規則（類型比較）所指示的特定嚴格弱排序準則進行排序。
訪問速度：multiset容器通過key訪問單個元素的速度通常比unordered_multiset容器慢，但當使用迭代器遍歷時會得到一個有序序列。
底層實現：multiset底層結構為二叉搜索樹（紅黑樹）。

注意：

multiset在底層中存儲的是<value, value>的鍵值對。
multiset的插入接口中只需要插入value即可。
與set的區別是，multiset中的元素可以重復，而set中的value是唯一的。
使用迭代器對multiset中的元素進行遍歷，可以得到有序的序列。
multiset中的元素不能修改。
在multiset中查找某個元素的時間復雜度為O(log N)。
multiset的作用是可以對元素進行排序。

5.2使用

以下是一個結合代碼介紹multiset主要功能的示例：

#include <iostream>
#include <set>int main() {// 創建一個multiset容器std::multiset<int> myMultiset;// 插入元素myMultiset.insert(10);myMultiset.insert(20);myMultiset.insert(10); // 重復元素myMultiset.insert(15);myMultiset.insert(10); // 重復元素// 遍歷multiset中的元素std::cout << "Elements in myMultiset:" << std::endl;for (const auto& elem : myMultiset) {std::cout << elem << " ";}std::cout << std::endl;// 查找某個元素auto it = myMultiset.find(10);if (it != myMultiset.end()) {std::cout << "Found element: " << *it << std::endl;} else {std::cout << "Element not found." << std::endl;}// 刪除某個元素myMultiset.erase(10);// 遍歷multiset中的元素std::cout << "Elements in myMultiset after erasing 10:" << std::endl;for (const auto& elem : myMultiset) {std::cout << elem << " ";}std::cout << std::endl;// 使用迭代器對multiset中的元素進行遍歷，可以得到有序的序列std::cout << "Elements in myMultiset using iterator:" << std::endl;for (auto it = myMultiset.begin(); it != myMultiset.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;return 0;
}

?輸出結果：

Elements in myMultiset:
10 10 10 15 20
Found element: 10
Elements in myMultiset after erasing 10:
15 20
Elements in myMultiset using iterator:
15 20

代碼說明：

創建一個multiset容器，并插入一些元素，包括重復的元素。
使用范圍for循環遍歷并打印multiset中的所有元素。
查找并打印特定元素是否存在。
刪除特定元素后再次遍歷并打印multiset中的所有元素。
使用迭代器遍歷并打印multiset中的所有元素，展示有序的序列。

6.map

6.1概念與性質

關聯容器：map是關聯容器，它按照特定的次序（按照key來比較）存儲由鍵值key和值value組合而成的元素。
鍵值對：在map中，鍵值key通常用于排序和唯一地標識元素，而值value中存儲與此鍵值key關聯的內容。鍵值key和值value的類型可能不同，并且在map的內部，key與value通過成員類型value_type綁定在一起，稱為pair：
```
typedef pair<const key, T> value_type;
```
排序：在內部，map中的元素總是按照鍵值key進行比較排序的。
訪問速度：map中通過鍵值訪問單個元素的速度通常比unordered_map容器慢，但map允許根據順序對元素進行直接迭代（即對map中的元素進行迭代時，可以得到一個有序的序列）。
下標訪問符：map支持下標訪問符，即在[]中放入key，就可以找到與key對應的value。
實現方式：map通常被實現為二叉搜索樹（更準確地說是平衡二叉搜索樹（紅黑樹））。

6.2使用

以下是一個結合代碼介紹map主要功能的示例：

#include <iostream>
#include <map>int main() {// 創建一個map容器std::map<int, std::string> myMap;// 插入元素myMap[1] = "one";myMap[2] = "two";myMap[3] = "three";// 遍歷map中的元素std::cout << "Elements in myMap:" << std::endl;for (const auto& elem : myMap) {std::cout << elem.first << " => " << elem.second << std::endl;}// 查找某個元素auto it = myMap.find(2);if (it != myMap.end()) {std::cout << "Found element with key 2: " << it->second << std::endl;} else {std::cout << "Element with key 2 not found." << std::endl;}// 刪除某個元素myMap.erase(2);// 遍歷map中的元素std::cout << "Elements in myMap after erasing key 2:" << std::endl;for (const auto& elem : myMap) {std::cout << elem.first << " => " << elem.second << std::endl;}// 使用下標訪問符修改元素myMap[1] = "ONE";std::cout << "Modified element with key 1: " << myMap[1] << std::endl;return 0;
}

輸出結果：

Elements in myMap:
1 => one
2 => two
3 => three
Found element with key 2: two
Elements in myMap after erasing key 2:
1 => one
3 => three
Modified element with key 1: ONE

代碼說明：

創建map容器：創建一個map容器，用于存儲int類型的鍵和std::string類型的值。
插入元素：使用下標操作符插入元素。
遍歷元素：使用范圍for循環遍歷并打印map中的所有元素，展示鍵值對。
查找元素：使用find函數查找特定鍵的元素，并打印是否找到該元素。
刪除元素：使用erase函數刪除特定鍵的元素，并再次遍歷打印剩余的元素。
修改元素：使用下標操作符修改特定鍵的值，并打印修改后的結果。

7.multimap

7.1概念與性質

關聯式容器：multimap是關聯式容器，它按照特定的順序存儲由key和value映射成的鍵值對<key, value>，其中多個鍵值對之間的key是可以重復的。
鍵值對：在multimap中，鍵值對按照key排序和唯一地標識元素，而映射的value存儲與key關聯的內容。key和value的類型可能不同，通過multimap內部的成員類型value_type組合在一起，value_type是組合key和value的鍵值對：
```
typedef pair<const Key, T> value_type;
```
排序規則：在內部，multimap中的元素總是通過其內部比較對象，按照指定的特定嚴格弱排序標準對key進行排序。
訪問速度：multimap通過key訪問單個元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍歷multimap中的元素可以得到關于key有序的序列。
實現方式：multimap在底層用二叉搜索樹（紅黑樹）來實現。

注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重復的。

7.2使用

以下是一個結合代碼介紹multimap主要功能的示例：

#include <iostream>
#include <map>int main() {// 創建一個multimap容器std::multimap<int, std::string> myMultimap;// 插入元素myMultimap.insert({1, "one"});myMultimap.insert({2, "two"});myMultimap.insert({1, "uno"});  // 重復keymyMultimap.insert({3, "three"});// 遍歷multimap中的元素std::cout << "Elements in myMultimap:" << std::endl;for (const auto& elem : myMultimap) {std::cout << elem.first << " => " << elem.second << std::endl;}// 查找某個元素auto it = myMultimap.find(1);if (it != myMultimap.end()) {std::cout << "Found element with key 1: " << it->second << std::endl;} else {std::cout << "Element with key 1 not found." << std::endl;}// 刪除某個元素myMultimap.erase(2);// 遍歷multimap中的元素std::cout << "Elements in myMultimap after erasing key 2:" << std::endl;for (const auto& elem : myMultimap) {std::cout << elem.first << " => " << elem.second << std::endl;}// 使用迭代器遍歷multimap中的元素std::cout << "Elements in myMultimap using iterator:" << std::endl;for (auto it = myMultimap.begin(); it != myMultimap.end(); ++it) {std::cout << it->first << " => " << it->second << " ";}std::cout << std::endl;return 0;
}

輸出結果：

Elements in myMultimap:
1 => one
1 => uno
2 => two
3 => three
Found element with key 1: one
Elements in myMultimap after erasing key 2:
1 => one
1 => uno
3 => three
Elements in myMultimap using iterator:
1 => one 1 => uno 3 => three

?代碼說明：

創建multimap容器：創建一個multimap容器，用于存儲int類型的鍵和std::string類型的值。
插入元素：使用insert函數插入元素，包括重復的鍵。
遍歷元素：使用范圍for循環遍歷并打印multimap中的所有元素，展示鍵值對。
查找元素：使用find函數查找特定鍵的元素，并打印是否找到該元素。
刪除元素：使用erase函數刪除特定鍵的元素，并再次遍歷打印剩余的元素。
使用迭代器遍歷元素：使用迭代器遍歷并打印multimap中的所有元素，展示有序的序列。

注意：

multimap中的key是可以重復的。
multimap中的元素默認將key按照小于來比較。
multimap中沒有重載operator[]操作，這是因為operator[]需要唯一的鍵來訪問對應的值，而multimap中的鍵是可以重復的，無法保證唯一性。

8.小結

在C++中，關聯式容器如set、multiset、map和multimap通過鍵值對來高效地管理和存儲數據。這些容器利用平衡樹結構（如紅黑樹）保證操作的有序性和高效性。set和multiset用于存儲唯一和重復的有序元素，而map和multimap則通過鍵值對實現鍵的唯一和重復存儲。理解和使用這些容器可以幫助我們在編程中高效地處理各種復雜的數據結構和操作需求。