C++ STL map 容器存储键值对，基于红黑树实现，支持 O(log n) 操作。pair 用于存储两个相关数据，是 map 节点的基础。map 支持 insert 插入及 operator[] 重载访问，若 key 不存在则自动创建。at 方法提供安全访问并抛出异常。multimap 允许重复 key。equal_range 返回匹配范围，lower_bound 和 upper_bound 分别定位起始和结束位置。map 与 set 均自动排序且键唯一，区别在于 map 存储键值对而 set 仅存键。
map 的声明定义了两种类型：Key和T。其中，Key是 map底层使用的关键字（键）的类型，而T是与之对应的值（value）的类型。对于 set（集合），默认情况下要求 Key类型支持小于比较操作。如果 Key类型不支持小于比较，或者需要自定义比较逻辑，可以通过传递一个仿函数（即自定义的比较函数对象）作为 map的第二个模板参数来实现。
map底层存储数据的内存是通过空间配置器分配的。在大多数情况下，我们不需要指定 map的后两个模板参数（即比较函数和内存分配器），因为它们有默认的实现。map的底层实现是基于红黑树，红黑树是一种自平衡的二叉搜索树，它能够在 O(logN)的时间复杂度内完成增、删、查、改操作。我们使用迭代器遍历 map时，会按照中序遍历的顺序进行，这意味着遍历将按照 key的有序顺序进行。
map（映射）是一个关联容器，它存储的是键值对（key-value pairs）。每个键（key）在 map中是唯一的，并且每个键都映射到一个值（value）。
<运算符排序，但可以自定义排序规则）。map内部通常实现为红黑树。在真正地探讨 map 之前，我们首先需要解决我们以前留下来的问题，什么是 pair？
C++标准库中，
pair是一个模板类，用于存储一对值。这对值可以是任何类型，包括自定义类型。pair通常用于需要同时返回或存储两个相关数据的场景~
pair由两个成员组成：
pair的第一个元素，可以是任何类型。pair的第二个元素，也可以是任何类型，并且不必与 first的类型相同。
pair可以通过多种方式构造和初始化：
pair对象，其 first和 second成员都被初始化为它们的默认值（通常是零或空指针，取决于类型）。pair对象时直接提供 first和 second的值。{}提供 first和 second的值。make_pair函数：使用 std::make_pair函数可以方便地构造一个 pair对象，而无需显式指定类型。#include<utility>//pair 头文件
void test1() {
pair<int, string> p1;//默认构造
pair<int, string> p2(2, "Hello!");//直接初始化
pair<int, string> p3 = { 3,"Haha!" };//列表初始化
pair<int, string> p4 = make_pair(4, "Hehe!");//make_pair 函数
cout << p1.first << " " << p1.second << endl;
cout << p2.first << " " << p2.second << endl;
cout << p3.first << " " << p3.second << endl;
cout << p4.first << " " << p4.second << endl;
}
pair提供了一些成员函数来访问和操作其成员：
first和 second：访问 pair的 first和 second成员。**operator=**：赋值操作符，用于将一个 pair对象的值赋给另一个 pair对象。**swap**：交换两个 pair对象的值。
void test2() {
pair<int, string> p1;//默认构造
pair<int, string> p2(2, "Hello!");//直接初始化
pair<int, string> p3 = { 3,"Haha!" };//列表初始化
pair<int, string> p4 = make_pair(4, "Hehe!");//make_pair 函数
p3 = p2;//支持赋值
p1.swap(p4);//支持交换
cout << p1.first << " " << p1.second << endl;
cout << p2.first << " " << p2.second << endl;
cout << p3.first << " " << p3.second << endl;
cout << p4.first << " " << p4.second << endl;
}
pair对象可以使用关系运算符（<, <=, >, >=, ==, !=）进行比较。比较是基于 first成员的字典序进行的，如果 first成员相等，则比较 second成员。
void test3() {
pair<int, string> p1;//默认构造
pair<int, string> p2(2, "Hello!");//直接初始化
pair<int, string> p3 = { 3,"Haha!" };//列表初始化
pair<int, string> p4 = make_pair(4, "Hehe!");//make_pair 函数
pair<int, string> p5 = make_pair(4, "AAAA!");//make_pair 函数
if (p2 > p3) cout << "p2 > p3" << endl;
else cout << "p2 < p3" << endl;
if (p4 < p5) cout << "p4 < p5" << endl;
else cout << "p4 > p5" << endl;
//first 相等，比较 second
}
pair在 C++编程中有多种用途，包括但不限于：
pair对象，从而同时返回两个值。pair。pair可以作为其他容器（如 vector, list, set等）的元素类型，用于存储键值对或其他成对的数据。接下来我们的 map 就会大量使用 pair~
在 map中，每个红黑树节点都存储一个 pair<Key, T>对象。这允许 map将键和值紧密地关联在一起，并有效地管理它们。当我们向 map中插入一个元素时，实际上是在红黑树中插入一个新的节点，该节点包含一个 pair<Key, T>对象，其中 Key是我们要插入的键，T是与该键相关联的值。
map的构造涉及选择键和值的类型，并使用合适的构造函数。最常用的构造函数包括默认构造函数（创建空map）、拷贝构造函数（基于现有map创建新map），以及迭代器区间构造函数（基于迭代器指定的元素范围初始化map）。map的构造灵活，支持多种初始化方式，满足不同的编程需求。构造后的map提供高效的插入、删除和查找操作，时间复杂度为 O(log n)。
map 提供了 insert 成员函数，来进行插入，同样有多个版本，我们可以根据需要进行选择~
我们可以看到第一个 insert 插入函数，返回值是一个 pair<iterator,bool>,返回一个
pair，其中first是一个迭代器，指向插入的键值对，second是一个布尔值，来表示插入是否成功~
void test4() {
map<int, string> mymap;
mymap.insert(pair<int, string>(1, "Hello!"));
pair<int, string> p(2, "Haha!");
mymap.insert(p);
mymap.insert(make_pair(3, "Hehe!"));
mymap.insert({ 4,"Heihei!" });
mymap[5] = "Five";//这里还可以使用数组的方式，更加巧妙
//遍历打印键值对
for (const auto& e : mymap) {
cout << "Key:" << e.first << " " << "Value:" << e.second << endl;
}
}
我们还需要注意的是 map 是不支持 key 冗余的，即使它们的 value 不一样，所以相同的 key 插入就会失败~
void test5() {
map<int, string> mymap;
mymap.insert(pair<int, string>(1, "Hello!"));
pair<int, string> p(2, "Haha!");
mymap.insert(p);
mymap.insert(make_pair(3, "Hehe!"));
mymap.insert({ 4,"Heihei!" });
mymap.insert({ 4,"He!" }); //使用迭代器遍历访问
auto it = mymap.begin();
while (it != mymap.end()) {
//cout << (*it).first << " " << (*it).second << endl;
cout << it->first << " " << it->second << endl;
//本质上是下面这种调用方式，编译器进行了优化
//cout << it.operator->()->first << " " << it.operator->()->second << endl;
it++;
}
}
前面我们使用初始化直接使用数组来对 map 进行初始化，实现了插入元素并且修改 value，这就不得不提 map 对 [] 运算符的重载了
下面这一句是重点：
让我们逐步解析：
this->insert(make_pair(k, mapped_type())):this指针指向当前对象。insert是当前对象的一个成员函数。make_pair(k, mapped_type())创建了一个键值对，其中k是键，mapped_type()是默认构造的值。insert函数将这个键值对插入到当前对象中，并返回一个pair，其中first是一个迭代器，指向插入的键值对，second是一个布尔值，表示插入是否成功。(this->insert(make_pair(k, mapped_type()))).first:从insert函数返回的pair中取出first，即指向插入的键值对的迭代器。*((this->insert(make_pair(k, mapped_type()))).first):对迭代器进行解引用，得到插入的键值对。(*((this->insert(make_pair(k, mapped_type()))).first)).second:从解引用的键值对中取出second，即插入的值。
根据这个，我们就可以来简单实现一下 operator 的底层：
//operator[]底层
Value& opertor[](const K& key) {
//首先调用 insert，得到返回的 pair 类型
pair<iterator, bool> ret = insert({ key,Value() });
//返回插入键值对迭代器里面的第二个，也就是插入位置的 value
return ret.first->second;
}
这里的 Value（）也就是调用的默认构造返回值也就是 Value 值的引用
事实上，operator[]的使用不仅仅限于此，它还有其他的使用方式~我们一起来看看：
void test6() {
map<int, string> mymap;
mymap.insert(pair<int, string>(1, "Hello!"));
pair<int, string> p(2, "Haha!");
mymap.insert(p);
mymap.insert(make_pair(3, "Hehe!"));
//1.插入
mymap[4];
//2、插入 + 修改
mymap[5] = "HHHH";//没有存在的，就插入然后返回的 value 值进行了修改
//3、修改
mymap[1] = "Heee";//已经存在的修改 value 值
//4.查找对应 key 的 value 值
cout << "mymap[2]:" << mymap[2] << endl;
auto it = mymap.begin();
while (it != mymap.end()) {
cout << it->first << " " << it->second << endl;
it++;
}
}
可以发现 map 对 [] 的重载给我们带来了极大的方便~
接下来我们来看一段小程序，进一步体会 operator[]的魅力~
void test7() {
vector<string> s = { "key","value","learn","learn","key","hello","key" };
//单词计数
map<string, int> count_map;
for (auto e : s) {
//利用 [] 重载
//没有就进行插入并且修改 value 值
//有就利用找到的迭代器对 value 值进行修改
count_map[e]++;
}
auto it = count_map.begin();
while (it != count_map.end()) {
cout << (*it).first << " " << (*it).second << endl;
it++;
}
}
这样使用 [ ] 就十分方便~
值得注意的是，map 实现了 [] 运算符重载，但是 set、multimap、multiset 都没有实现 [] 运算符重载，所以使用的时候我们需要注意可以使用的地方~
我们还可以看到 C++11 还添加了**at函数用于访问 map中指定键对应的值**，有两种重载形式：非常量版本和常量版本。如果键存在，返回对应值的引用；如果键不存在，抛出 std::out_of_range异常，这提供了一种安全的元素访问方式。
简单测试：
void test8() {
map<int, string> mymap;
mymap.insert(pair<int, string>(1, "Hello!"));
pair<int, string> p(2, "Haha!");
mymap.insert(p);
mymap.insert(make_pair(3, "Hehe!"));
cout << mymap.at(1) << endl;//键存在，返回对应值的引用
//cout << mymap.at(4) << endl;//err,键不存在，抛出 std::out_of_range 异常
}
我们已经讲解了 map 容器里面的大多数接口，剩下的接口大家可以查阅文档 C++中的 map，大多数与我们前面讲解的 set 接口是一样的，大家也可以参考前面 set 的文章~
接下来，我们来看看 multimap：
map中每个键是唯一的，插入相同键会失败或更新值；而 multimap允许多个相同键的元素，两者通常基于红黑树实现，查找、插入和删除操作的时间复杂度为 O(log n)~
我们来看看它们的使用:
void test9() {
//是否插入看的是 key,不是 value
//map 不支持 key 冗余，无论 value 是否一样
map<int, string> mymap;
mymap.insert({ 1, "Hello" });
mymap.insert({ 1, "Haha" });
mymap.insert({ 2,"Hehe" });
mymap.insert({ 3,"H" });
mymap.insert({ 3,"H" });
//multimap 支持 key 冗余，无论 value 是否一样
multimap<int, string> mul_map;
mul_map.insert({ 1, "Hello" });
mul_map.insert({ 1, "Haha" });
mul_map.insert({ 2,"Hehe" });
mul_map.insert({ 3,"H" });
mul_map.insert({ 3,"H" });
cout << "map:" << endl;
auto it = mymap.begin();
while (it != mymap.end()) {
cout << it->first << " " << it->second << endl;
it++;
}
cout << "multimap:" << endl;
for (const auto& e : mul_map) {
cout << e.first << " " << e.second << endl;
}
}
其他接口依然是类似的，这里就不过多的描述了~
在 set 里面我们提到了 lower_bound 和 upper_bound，这里我们有一个新的内容 equal_range，它可以用来获取与指定键匹配的所有元素范围~返回值是 pair 类型，里面是两个迭代器，也就是开始位置的迭代器和结束位置后面的迭代器（左闭右开的区间）
void test10() {
multimap<int, string> mul_map;
mul_map.insert({ 1, "Hello" });
mul_map.insert({ 1, "Haha" });
mul_map.insert({ 2,"Hehe" });
mul_map.insert({ 3,"H" });
mul_map.insert({ 3,"H" });
//获取与指定键 1 匹配的所有元素范围
pair<multimap<int, string>::iterator,multimap<int, string>::iterator> ret = mul_map.equal_range(1);
auto it = ret.first; //左闭右开的区间
while (it != ret.second)//ret 是 pair 类型的
{
cout << it->first << " " << it->second << endl;
it++;
}
}
equal_range、lower_bound和 upper_bound简单对比equal_range、lower_bound和 upper_bound都是 C++标准库中关联容器（std::map、std::multimap、std::set、std::multiset）的成员函数，用于查找元素或元素范围。它们之间的区别和联系如下：
equal_rangestd::pair，其中 first是指向第一个不小于指定键的元素的迭代器，second是指向第一个大于指定键的元素的迭代器。std::multimap和 std::multiset）。lower_boundupper_boundequal_range实际上可以通过 lower_bound和 upper_bound的组合来实现，具体来说，equal_range(key)返回的范围等同于 {lower_bound(key), upper_bound(key)}。lower_bound。upper_bound。equal_range。map和 set容器的简单对比存储内容
唯一性
排序
时间复杂度
map和 set这些操作的时间复杂度都是 O(log n)。使用场景
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online