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容器中，我们可以通过键查找对应的值，就像字典一样。

以下是键值对的一些特点和优势：

1. 唯一性：在map中，每个键是唯一的，这保证了查找操作的准确性。而在multimap中，虽然允许键重复，但每个键值对仍然是唯一的。
2. 快速查找：关联式容器通常通过某种平衡树结构（如红黑树）实现，能够在对数时间内完成查找操作。
3. 自动排序：键值对按照键自动排序，这使得关联式容器不仅可以高效地进行查找，还可以方便地进行范围查询和遍历。

键值对的这种结构使得关联式容器在处理需要快速查找和排序的数据时非常有用。接下来，我们将详细介绍各个关联式容器的具体概念与使用方法。

3.树形结构的关联式容器

树形结构是实现关联式容器的核心技术之一。关联式容器通常使用平衡树（如红黑树）来管理内部数据。这种树形结构能够保持数据的有序性，同时保证插入、删除和查找操作的高效性。

3.1树形结构的特点

1. 自动排序：树形结构中的元素按照键值自动排序，这使得容器内的数据始终保持有序。对于set和multiset，元素本身作为键进行排序；对于map和multimap，元素按照键排序，值与键关联。

2. 平衡性：平衡树通过自我调整，保持树的高度尽可能小，从而保证了操作的效率。红黑树是一种常见的平衡树，它在最坏情况下仍能保证对数时间复杂度的操作性能。

3. 高效操作：由于树形结构的特性，插入、删除和查找操作的时间复杂度为O(log n)，这是通过线性搜索无法达到的。

3.2树形结构在关联式容器中的应用

• set和multiset：使用树形结构来存储唯一或允许重复的元素，并保持它们的有序性。
• map和multimap：利用树形结构存储键值对，通过键来组织和查找数据，保证键的唯一性或允许重复键。

4.set

4.1概念与性质

1. 有序存储：set是按照一定次序存储元素的容器。在set中，元素始终保持有序。
2. 唯一性：在set中，元素的值（value）也标识它（value就是key，类型为T），并且每个value必须是唯一的。set中的元素不能在容器中修改（元素总是const），但是可以从容器中插入或删除它们。
3. 内部排序：在内部，set中的元素总是按照其内部比较对象（类型比较）所指示的特定严格弱排序准则进行排序。
4. 访问速度：set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. 实现方式：set在底层是用二叉搜索树（红黑树）实现的。

注意：

1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复（因此可以使用set进行去重）。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列。
5. set中的元素默认按照小于来比较。
6. set中查找某个元素，时间复杂度为O(log n)。
7. set中的元素不允许修改。这是因为修改元素会破坏set的有序性和唯一性。
8. 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概念与性质

1. 有序存储：multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
2. 元素识别：在multiset中，元素的值（value）也会识别它（因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T）。multiset元素的值不能在容器中进行修改（因为元素总是const的），但可以从容器中插入或删除。
3. 排序规则：在内部，multiset中的元素总是按照其内部比较规则（类型比较）所指示的特定严格弱排序准则进行排序。
4. 访问速度：multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
5. 底层实现：multiset底层结构为二叉搜索树（红黑树）。

注意：

1. multiset在底层中存储的是<value, value>的键值对。
2. multiset的插入接口中只需要插入value即可。
3. 与set的区别是，multiset中的元素可以重复，而set中的value是唯一的。
4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列。
5. multiset中的元素不能修改。
6. 在multiset中查找某个元素的时间复杂度为O(log N)。
7. 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

代码说明：

1. 创建一个multiset容器，并插入一些元素，包括重复的元素。
2. 使用范围for循环遍历并打印multiset中的所有元素。
3. 查找并打印特定元素是否存在。
4. 删除特定元素后再次遍历并打印multiset中的所有元素。
5. 使用迭代器遍历并打印multiset中的所有元素，展示有序的序列。

6.map

6.1概念与性质

1. 关联容器：map是关联容器，它按照特定的次序（按照key来比较）存储由键值key和值value组合而成的元素。
2. 键值对：在map中，键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，称为pair：

   typedef pair<const key, T> value_type;

3. 排序：在内部，map中的元素总是按照键值key进行比较排序的。
4. 访问速度：map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代（即对map中的元素进行迭代时，可以得到一个有序的序列）。
5. 下标访问符：map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. 实现方式：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

代码说明：

1. 创建map容器：创建一个map容器，用于存储int类型的键和std::string类型的值。
2. 插入元素：使用下标操作符插入元素。
3. 遍历元素：使用范围for循环遍历并打印map中的所有元素，展示键值对。
4. 查找元素：使用find函数查找特定键的元素，并打印是否找到该元素。
5. 删除元素：使用erase函数删除特定键的元素，并再次遍历打印剩余的元素。
6. 修改元素：使用下标操作符修改特定键的值，并打印修改后的结果。

7.multimap

7.1概念与性质

1. 关联式容器：multimap是关联式容器，它按照特定的顺序存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的。
2. 键值对：在multimap中，键值对按照key排序和唯一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对：

   typedef pair<const Key, T> value_type;

3. 排序规则：在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序。
4. 访问速度：multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
5. 实现方式：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

 代码说明：

1. 创建multimap容器：创建一个multimap容器，用于存储int类型的键和std::string类型的值。
2. 插入元素：使用insert函数插入元素，包括重复的键。
3. 遍历元素：使用范围for循环遍历并打印multimap中的所有元素，展示键值对。
4. 查找元素：使用find函数查找特定键的元素，并打印是否找到该元素。
5. 删除元素：使用erase函数删除特定键的元素，并再次遍历打印剩余的元素。
6. 使用迭代器遍历元素：使用迭代器遍历并打印multimap中的所有元素，展示有序的序列。

注意：

1. multimap中的key是可以重复的。
2. multimap中的元素默认将key按照小于来比较。
3. multimap中没有重载operator[]操作，这是因为operator[]需要唯一的键来访问对应的值，而multimap中的键是可以重复的，无法保证唯一性。

8.小结

在C++中，关联式容器如set、multiset、map和multimap通过键值对来高效地管理和存储数据。这些容器利用平衡树结构（如红黑树）保证操作的有序性和高效性。set和multiset用于存储唯一和重复的有序元素，而map和multimap则通过键值对实现键的唯一和重复存储。理解和使用这些容器可以帮助我们在编程中高效地处理各种复杂的数据结构和操作需求。