@toc
前言
各位小伙伴们，在这个美好的中秋节来临之际，我衷心祝福你和你的家人度过一个幸福、团圆的时刻。愿明月的皎洁照耀你的每一天，团圆的月饼传递着我对你的思念和祝福。祝福你在中秋佳节里收获幸福与快乐，家庭和睦，心想事成。中秋快乐！
前面我们讲了C语言的基础知识，也了解了一些初阶数据结构，并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载，引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ，也了解了C++中的模版，以及学习了几个STL的结构也相信大家都掌握的不错，接下来博主将会带领大家继续学习有关C++比较重要的知识点—— map & multimap (STL) 。下面话不多说坐稳扶好咱们要开车了😍
一、map简介
在C++中，map是一种关联容器，它提供了一种将键值对存储为有序集合的方式。每个键唯一地映射到一个值，因此可以使用键来高效地查找、插入和删除元素。其中map又分为map和multimap，接下来博主将会带着大家认识一下这两个函数。
🔴 官方文档 > 链接
二、std::map
- std::map简介
⭕ 官方文档 > 链接
std::map是C++ STL提供的一种关联容器，它将键值对作为元素存储，并根据键的大小进行排序。每个键只能出现一次，即一个键最多只能映射到一个值。std::map提供了高效的插入、查找和删除操作，并支持多种方式遍历元素。
下面是std::map的一些重要特点： - 插入元素时会自动根据键的大小进行排序。
- 可以通过键来查找对应的值，时间复杂度为O(logN)，其中N为元素的个数。
- 从std::map中删除元素也很容易，时间复杂度为O(logN)。
- std::map可以用于各种类型的键和值，包括基本类型和用户定义类型。
- std::map的实现是基于红黑树的平衡二叉搜索树，因此插入、查找和删除的时间复杂度都是O(logN)。
- std::map使用
- 基本使用
使用std::map非常简单，只需要包含头文件，然后定义std::map对象并开始使用：include
std::map myMap;
myMap[0] = "zero";
myMap[1] = "one";
std::cout << myMap[0] << std::endl; // 输出"zero"
std::cout << myMap[1] << std::endl; // 输出"one"- map模板参数说明
template < class Key, class T, class Compare = less, class Alloc = allocator > > class map;
//模版说明
class Key //map::key_type
class T //map::mapped_type
class Compare = less //map::key_compare
class Alloc = allocator > //map::allocator_type⭕std::pair
- pair 是 C++ STL 中的一个模板类，用于表示一组键值对，其中键类型为 const Key，值类型为 T。它是由头文件 提供的。
- std::pair 是一个简单的容器类，用于保存两个值，并为这两个值提供了相应的访问方式。它有两个成员变量 first 和 second，分别用于存储第一个值和第二个值。
- 在 std::pair 中，键是一个 const 类型，即不可修改。这意味着一旦设置了键的值，就无法再更改它。这样设计是为了确保 std::map 等关联容器的键的稳定性和排序规则。
- std::pair 常常用来表示 std::map 或其他类似容器中的一个元素。每个元素由一个键和一个值组成，键的类型是 const Key，即不可修改，值的类型是 T。
可以通过以下方式访问 pair 对象中的键和值：
• pair.first：表示键的成员变量，类型为 const Key。
• pair.second：表示值的成员变量，类型为 T。
- map的构造函数
- 默认构造函数：
std::map myMap;创建一个空的 std::map 对象，其中键的类型为 Key，值的类型为 T。 - 区间构造函数：
template< class InputIt >
std::map( InputIt first, InputIt last,const Compare& comp = Compare(), const Allocator& alloc = Allocator() );使用范围 [first, last) 内的元素创建一个新的 std::map 对象。first 和 last 是输入迭代器，用于指定范围。元素的类型必须可以隐式转换为 std::pair<const Key, T>。可选地，可以提供一个比较函数对象 comp 和一个分配器 alloc。 - 拷贝构造函数：
std::map( const std::map& other );使用另一个 std::map 对象 other 中的所有元素创建一个新的 std::map 对象。创建的对象将拥有与 other 相同的键值对。 - 移动构造函数：
std::map( std::map&& other ) noexcept;使用另一个 std::map 对象 other 中的所有元素创建一个新的 std::map 对象。创建的对象将拥有 other 的键值对，并且 other 将被清空。
- map的迭代器
- 正向迭代器 (iterator) 和常量正向迭代器 (const_iterator)：
• 用途：可用于遍历 std::map 容器，并且可以修改或访问键值对。
• 示例用法：
std::map myMap;
for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) {
const Key& key = iter->first; // 键
Value& value = iter->second; // 值
// 进行操作或访问
}1. 反向迭代器 (reverse_iterator) 和常量反向迭代器 (const_reverse_iterator)：
• 用途：可用于以相反的顺序遍历 std::map 容器，并且可以修改或访问键值对。
• 示例用法：
std::map myMap;
for (auto rIter = myMap.rbegin(); rIter != myMap.rend(); ++rIter) {
const Key& key = rIter->first; // 键
Value& value = rIter->second; // 值
// 进行操作或访问
}1. 常量迭代器 (const_iterator) 和常量反向迭代器 (const_reverse_iterator)：
• 用途：用于遍历 std::map 容器，但不能修改键值对。仅适用于 const std::map 对象。
• 示例用法：
const std::map myMap;
for (auto cIter = myMap.begin(); cIter != myMap.end(); ++cIter) {
const Key& key = cIter->first; // 键
const Value& value = cIter->second; // 值
// 进行访问操作
}总结成一个表格如下：
函数
功能介绍
begin()
返回一个迭代器，指向容器中的第一个元素
end()
返回一个迭代器，指向容器中最后一个元素的下一个位置
cbegin()和 cend()
与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin()
返回一个反向迭代器，指向容器中最后一个元素的下一个位置
rend()
返回一个反向迭代器，指向容器中第一个元素
crbegin()
返回一个常量反向迭代器，指向容器中最后一个元素的下一个位置
crend()
返回一个常量反向迭代器，指向容器中第一个元素
- map的容量与元素访问函数
🍁容量函数
- empty()：返回一个布尔值，表示 std::map 是否为空。如果为空，则返回 true；否则，返回 false。
std::map myMap;
if (myMap.empty()) {
// map为空
}1. size()：返回 std::map 容器中键值对的数量。
std::map myMap;
std::size_t count = myMap.size();🍁元素访问函数 - operator[]：使用指定的键获取或设置相应的值。如果键不存在，会插入一个新的键值对。
std::map myMap;
myMap[key] = value; // 设置键为key的值为value
Value val = myMap[key]; // 获取键为key的值1. at()：根据指定的键获取相应的值，如果键不存在，会抛出 std::out_of_range 异常。
std::map myMap;
Value val = myMap.at(key); // 获取键为key的值1. insert()：插入一个新的键值对到 std::map 容器中。
std::map myMap;
myMap.insert(std::make_pair(key, value)); // 插入键值对（key, value）1. erase()：根据指定的键删除相应的键值对。
std::map myMap;
myMap.erase(key); // 删除键为key的键值对🚨🚨注意：对于operator[]来说如果键不存在，会插入一个新的键值对而 at()函数如果键不存在，会抛出 std::out_of_range 异常。 - map的所有函数（表）
函数用法
功能解释
empty()
返回一个布尔值，表示 std::map 是否为空。如果为空，则返回 true；否则，返回 false。
size()
返回 std::map 容器中键值对的数量。
operator[]
使用指定的键获取或设置相应的值。如果键不存在，会插入一个新的键值对。
at()
根据指定的键获取相应的值，如果键不存在，会抛出 std::out_of_range 异常。
insert()
插入一个新的键值对到 std::map 容器中。
erase()
根据指定的键删除相应的键值对。
find()
根据指定的键查找相应的键值对，并返回指向该键值对的迭代器。如果键不存在，则返回指向末尾的迭代器。
count()
返回指定键的数量。由于 std::map 中的键是唯一的，所以返回值要么是 0（键不存在），要么是 1（键存在）。
begin()
返回一个迭代器，指向 std::map 中第一个键值对。
end()
返回一个迭代器，指向 std::map 中最后一个键值对的下一个位置。
rbegin()
返回一个反向迭代器，指向 std::map 中最后一个键值对。
rend()
返回一个反向迭代器，指向 std::map 中第一个键值对的前一个位置。
lower_bound()
返回一个迭代器，指向大于等于给定键的第一个键值对。
upper_bound()
返回一个迭代器，指向大于给定键的第一个键值对。
equal_range()
返回一个 std::pair，其中包含两个迭代器：第一个迭代器指向大于等于给定键的第一个键值对，第二个迭代器指向大于给定键的第一个键值对。
clear()
清空 std::map 容器中的所有键值对。
三、std::multimap - std::multimap简介
⭕ 官方文档 > 链接
std::multimap 是 C++ 标准库中的关联容器之一，它提供了对键值对的有序存储和访问能力，并且允许多个元素具有相同的键。
std::multimap 的特点如下： - 存储重复键：std::multimap 允许多个元素具有相同的键。这意味着你可以在 std::multimap 中存储重复的键值对，每个键对应一个值。
- 排序：std::multimap 内部使用红黑树（Red-Black Tree）实现，可以保持元素的有序性。默认情况下，元素按照键的升序排序，但你也可以通过自定义的比较函数或比较运算符来指定排序规则。
- 插入和访问：向 std::multimap 中插入新元素时，按照键的顺序插入即可，不需要进行键的比较和查找操作。访问元素时，可以使用迭代器进行遍历和访问，也可以使用键进行范围查找。
- 动态大小：std::multimap 是动态大小的容器，它会根据元素的插入和删除自动调整自身的大小。
使用 std::multimap 可以方便地处理具有相同键的元素，例如在一个电话簿中存储多个人的联系电话，或者在一个日程安排中存储多个事件的时间。它提供了高效的键值对的插入、访问和搜索操作，并且可以根据指定的排序规则自动对元素进行排序。
🔴在使用上面与std::map的使用方法以及函数类型都一样，这里我就不再过多的赘述了。（详细的说明可以看官方文档的介绍）
四、std::map与std::multimap的比较
• 相同点： - 存储键值对：std::map 和 std::multimap 都用于存储键值对，并提供了对键值对的有序存储和访问能力。
- 基于红黑树：std::map 和 std::multimap 在内部实现上都使用了红黑树（Red-Black Tree），以保持元素的有序性。
- 迭代器支持：它们都提供了迭代器的支持，可以使用迭代器进行遍历、访问和修改容器中的元素。
• 不同点： - 唯一性：最主要的区别在于键的唯一性。std::map 中的键是唯一的，每个键只能对应一个值，如果插入具有相同键的元素，则会替换原有键对应的值。而 std::multimap 允许多个元素具有相同的键，因此可以在 std::multimap 中存储重复的键值对。
- 插入和查找：由于 std::map 中的键是唯一的，插入新元素时要进行键的比较和查找，以保持键的唯一性。这会导致插入和查找的时间复杂度是对数级别的。而 std::multimap 允许重复的键，因此插入新元素时只需按照键的顺序插入即可，插入的时间复杂度为常数级别。
- 迭代器范围：对于 std::map，每个键只有一个对应的值，因此迭代器范围是唯一的。而对于 std::multimap，由于允许重复的键，因此迭代器范围可以包含多个具有相同键的元素。
🚨综上所述，选择使用 std::map 还是 std::multimap 取决于你的需求和对键的唯一性的要求。如果需要存储唯一的键值对，可以选择 std::map，如果允许并且需要存储重复的键值对，可以选择 std::multimap。
温馨提示
感谢您对博主文章的关注与支持！另外，我计划在未来的更新中持续探讨与本文相关的内容，会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新，不要错过任何精彩内容！
再次感谢您的支持和关注。期待与您建立更紧密的互动，共同探索C++、算法和编程的奥秘。祝您生活愉快，排便顺畅！
