目录
引言
在C++ 的标准模板库（STL）中，关联式容器是非常重要的一部分，它们为我们提供了高效的数据存储和检索方式。今天，我们就来深入探讨一下其中的 map 和 set 容器，看看它们是如何在实际编程中发挥作用的。
一、关联式容器概述
1.1 与序列式容器的区别
在之前的学习中，我们接触过像 vector 、 list 、 deque 这样的序列式容器，它们底层是线性序列的数据结构，存储的是数据本身。而关联式容器存储的是 <key, value> 结构的键值对，在数据检索时比序列式容器效率更高。
1.2 底层结构
关联式容器根据应用场景不同，主要有树形结构（如红黑树）和哈希结构。今天重点讨论的 map 和 set 以及它们的变体 multimap 、 multiset 底层多采用平衡搜索树（红黑树）实现，这使得容器中的元素是有序的序列。
二、set容器详解set介绍
2.1 set的特性
set 是按照一定次序存储元素的容器，其中元素的 value 也标识它自己（即 value 就是 key ），并且每个 value 必须是唯一的。 set 中的元素不能在容器中修改（元素总是 const ），但可以插入或删除。其内部元素默认按照小于来比较排序。
2.2 set的模板参数
cpp
template <
class T,
class Compare = less<T>,
class Allocator = allocator<T>
> class set;- T ：存储元素的类型，实际底层存储 <value, value> 的键值对。
- Compare ：比较器类型，默认按小于比较。
- Allocator ：空间配置器，一般不用用户传递。
2.3 set的常用接口
1. 插入元素
cpp
#include <set>
#include <iostream>
int main() {
std::set<int> s;
std::pair<std::set<int>::iterator, bool> ret = s.insert(5);
if (ret.second) {
std::cout << "插入成功，元素值为：" << *ret.first << std::endl;
} else {
std::cout << "插入失败，元素已存在" << std::endl;
}
return 0;
}1. 删除元素
cpp
#include <set>
#include <iostream>
int main() {
std::set<int> s = {1, 2, 3, 4, 5};
s.erase(s.find(3)); // 删除值为3的元素
for (auto e : s) {
std::cout << e << " ";
}
std::cout << std::endl;
return 0;
}1. 查找元素
cpp
#include <set>
#include <iostream>
int main() {
std::set<int> s = {1, 2, 3, 4, 5};
std::set<int>::iterator it = s.find(3);
if (it != s.end()) {
std::cout << "找到元素：" << *it << std::endl;
} else {
std::cout << "未找到元素" << std::endl;
}
return 0;
}
2.4 set使用示例
cpp
#include <set>
#include <iostream>
void TestSet() {
int array[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
std::set<int> s(array, array + sizeof(array) / sizeof(array[0]));
std::cout << "set的大小为：" << s.size() << std::endl;
// 正向打印set中的元素
std::cout << "正向打印set元素：";
for (auto& e : s) {
std::cout << e << " ";
}
std::cout << std::endl;
// 使用迭代器逆向打印set中的元素
std::cout << "逆向打印set元素：";
for (auto it = s.rbegin(); it != s.rend(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// set中值为3的元素出现了几次
std::cout << "值为3的元素个数：" << s.count(3) << std::endl;
}
int main() {
TestSet();
return 0;
}三、map容器详解map介绍
3.1 map的特性
map 是关联容器，它按照特定的次序（按照 key 来比较）存储由键值 key 和值 value 组合而成的元素。 key 通常用于排序和唯一地标识元素， value 存储与此键值 key 关联的内容。
3.2 map的模板参数
cpp
template <
class Key,
class T,
class Compare = less<Key>,
class Allocator = allocator<pair<const Key, T>>
> class map;
- Key ：键值对中 key 的类型。
- T ：键值对中 value 的类型。
- Compare ：比较器类型，默认按 key 小于比较。
- Allocator ：空间配置器。
3.3 map的常用接口
1. 插入元素
cpp
#include <map>
#include <string>
#include <iostream>
int main() {
std::map<std::string, std::string> m;
// 方式一：用pair直接构造键值对插入
std::pair<std::map<std::string, std::string>::iterator, bool> ret1 = m.insert(std::pair<std::string, std::string>("apple", "苹果"));
if (ret1.second) {
std::cout << "插入成功" << std::endl;
} else {
std::cout << "插入失败，元素已存在" << std::endl;
}
// 方式二：用make_pair函数构造键值对插入
std::pair<std::map<std::string, std::string>::iterator, bool> ret2 = m.insert(std::make_pair("banana", "香蕉"));
if (ret2.second) {
std::cout << "插入成功" << std::endl;
} else {
std::cout << "插入失败，元素已存在" << std::endl;
}
// 方式三：通过operator[]插入
m["pear"] = "梨";
return 0;
}1. 删除元素
cpp
#include <map>
#include <string>
#include <iostream>
int main() {
std::map<std::string, std::string> m = {{"apple", "苹果"}, {"banana", "香蕉"}};
m.erase("banana");
for (const auto& e : m) {
std::cout << e.first << " -> " << e.second << std::endl;
}
return 0;
}1. 查找元素
cpp
#include <map>
#include <string>
#include <iostream>
int main() {
std::map<std::string, std::string> m = {{"apple", "苹果"}, {"banana", "香蕉"}};
std::map<std::string, std::string>::iterator it = m.find("apple");
if (it != m.end()) {
std::cout << "找到元素：" << it->first << " -> " << it->second << std::endl;
} else {
std::cout << "未找到元素" << std::endl;
}
return 0;
}3.4 map使用示例
cpp
#include <map>
#include <string>
#include <iostream>
void TestMap() {
std::map<std::string, std::string> m;
// 向map中插入元素的方式
// 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
m.insert(std::pair<std::string, std::string>("peach", "桃子"));
// 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
m.insert(std::make_pair("banana", "香蕉"));
// 借用operator[]向map中插入元素
m["apple"] = "苹果";
std::cout << "map的大小为：" << m.size() << std::endl;
// 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
std::cout << "遍历map元素：" << std::endl;
for (const auto& e : m) {
std::cout << e.first << " ---> " << e.second << std::endl;
}
// map中的键值对key一定是唯一的，如果key存在将插入失败
auto ret = m.insert(std::make_pair("peach", "桃色"));
if (ret.second) {
std::cout << "peach，桃色不在map中，已经插入" << std::endl;
} else {
std::cout << "键值为peach的元素已经存在：" << ret.first->first << " ---> " << ret.first->second << " 插入失败" << std::endl;
}
// 删除key为"apple"的元素
m.erase("apple");
if (1 == m.count("apple")) {
std::cout << "apple还在" << std::endl;
} else {
std::cout << "apple被吃了" << std::endl;
}
}
int main() {
TestMap();
return 0;
}四、multiset容器详解multiset介绍
4.1 multiset的特性
multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的。元素的 value 也会标识它（因为 multiset 中本身存储的就是 <value, value> 组成的键值对），元素的值不能在容器中进行修改（元素总是 const ），但可以从容器中插入或删除。其内部元素默认按照小于来比较排序。
4.2 multiset的模板参数
cpp
template <
class T,
class Compare = less<T>,
class Allocator = allocator<T>
> class multiset;
与 set 的模板参数类似， T 为存储元素的类型， Compare 是比较器， Allocator 是空间配置器 。
4.3 multiset的常用接口
1. 插入元素
cpp
#include <multiset>
#include <iostream>
int main() {
std::multiset<int> ms;
ms.insert(3);
ms.insert(3);
ms.insert(5);
for (auto e : ms) {
std::cout << e << " ";
}
std::cout << std::endl;
return 0;
}
1. 删除元素
cpp
#include <multiset>
#include <iostream>
int main() {
std::multiset<int> ms = {1, 3, 3, 5};
ms.erase(ms.find(3)); // 删除一个值为3的元素
for (auto e : ms) {
std::cout << e << " ";
}
std::cout << std::endl;
return 0;
}
4.4 multiset使用示例
cpp
#include <set>
#include <iostream>
void TestMultiset() {
int array[] = {2, 1, 3, 9, 6, 0, 5, 8, 4, 7};
std::multiset<int> ms(array, array + sizeof(array) / sizeof(array[0]));
for (auto& e : ms) {
std::cout << e << " ";
}
std::cout << std::endl;
}
int main() {
TestMultiset();
return 0;
}五、multimap容器详解multimap介绍
5.1 multimap的特性
multimap 是关联式容器，它按照特定的顺序，存储由 key 和 value 映射成的键值对 <key, value> ，其中多个键值对之间的 key 是可以重复的。通常按照 key 排序和唯一地标识元素， value 存储与 key 关联的内容。
5.2 multimap的模板参数
cpp
template <
class Key,
class T,
class Compare = less<Key>,
class Allocator = allocator<pair<const Key, T>>
> class multimap;
和 map 的模板参数类似， Key 是键的类型， T 是值的类型， Compare 是比较器， Allocator 是空间配置器。
5.3 multimap的常用接口
1. 插入元素
cpp
#include <multimap>
#include <string>
#include <iostream>
int main() {
std::multimap<std::string, std::string> mm;
mm.insert(std::make_pair("fruit", "apple"));
mm.insert(std::make_pair("fruit", "banana"));
for (const auto& e : mm) {
std::cout << e.first << " -> " << e.second << std::endl;
}
return 0;
}
1. 删除元素
cpp
#include <multimap>
#include <string>
#include <iostream>
int main() {
std::multimap<std::string, std::string> mm = {{"fruit", "apple"}, {"fruit", "banana"}};
mm.erase(mm.find("fruit")); // 删除一个key为"fruit"的键值对
for (const auto& e : mm) {
std::cout << e.first << " -> " << e.second << std::endl;
}
return 0;
}
5.4 multimap使用示例
cpp
#include <multimap>
#include <string>
#include <iostream>
void TestMultimap() {
std::multimap<std::string, std::string> mm;
mm.insert(std::make_pair("person", "Alice"));
mm.insert(std::make_pair("person", "Bob"));
mm.insert(std::make_pair("animal", "cat"));
mm.insert(std::make_pair("animal", "dog"));
std::cout << "遍历multimap元素：" << std::endl;
for (const auto& e : mm) {
std::cout << e.first << " ---> " << e.second << std::endl;
}
}
int main() {
TestMultimap();
return 0;
}| 容器 | 元素唯一性 | 元素修改 | 底层结构 | 应用场景举例 |
| set | 唯一 | 不可修改 | 红黑树 | 红黑树|存储不重复的整数集合，如学生学号集合 |
| map | key唯一 | value可修改 | 红黑树 | 红黑树|存储学生学号与成绩的映射关系 |
| multiset | 可重复 | 不可修改 | 红黑树 | 统计单词在文本中出现的所有位置（位置可重复） |
| multimap | key可重复 | value可修改 | 红黑树 | |红黑树|存储一个班级中所有学生的成绩（可能有重名学生） |
六、总结
set 和 map 作为C++ STL中重要的关联式容器，有着广泛的应用场景。 set 适用于需要存储唯一元素并进行快速查找、排序的场景； map 则适用于需要建立键值对映射关系，通过 key 高效查找 value 的场景。理解它们的特性、接口和底层实现，能帮助我们在实际编程中更高效地使用它们，优化代码性能。希望通过这篇博客，大家能对 set 和 map 有更深入的认识。