前言
各位小伙伴们,在这个美好的中秋节来临之际,我衷心祝福你和你的家人度过一个幸福、团圆的时刻。愿明月的皎洁照耀你的每一天,团圆的月饼传递着我对你的思念和祝福。祝福你在中秋佳节里收获幸福与快乐,家庭和睦,心想事成。中秋快乐!
前面我们讲了C语言的基础知识,也了解了一些初阶数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ,也了解了C++中的模版,以及学习了几个STL的结构也相信大家都掌握的不错,接下来博主将会带领大家继续学习有关C++比较重要的知识点—— map & multimap (STL) 。下面话不多说坐稳扶好咱们要开车了😍
一、map简介
在C++中,map
是一种关联容器,它提供了一种将键值对存储为有序集合的方式。每个键唯一地映射到一个值,因此可以使用键来高效地查找、插入和删除元素。其中map
又分为map
和multimap
,接下来博主将会带着大家认识一下这两个函数。
🔴 官方文档 > 链接
二、std::map
1. std::map简介
⭕ 官方文档 > 链接
std::map
是C++ STL提供的一种关联容器,它将键值对作为元素存储,并根据键的大小进行排序。每个键只能出现一次,即一个键最多只能映射到一个值。std::map
提供了高效的插入、查找和删除操作,并支持多种方式遍历元素。
下面是std::map
的一些重要特点:
- 插入元素时会自动根据键的大小进行排序。
- 可以通过键来查找对应的值,时间复杂度为O(logN),其中N为元素的个数。
- 从
std::map
中删除元素也很容易,时间复杂度为O(logN)。 -
std::map
可以用于各种类型的键和值,包括基本类型和用户定义类型。 -
std::map
的实现是基于红黑树的平衡二叉搜索树,因此插入、查找和删除的时间复杂度都是O(logN)。
2. std::map使用
- 基本使用
使用std::map
非常简单,只需要包含头文件<map>
,然后定义std::map
对象并开始使用:
#include <map>
std::map<int, std::string> 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<Key>, class Alloc = allocator<pair<const Key,T> > > class map;
//模版说明
class Key //map::key_type
class T //map::mapped_type
class Compare = less<Key> //map::key_compare
class Alloc = allocator<pair<const Key,T> > //map::allocator_type
⭕std::pair<const Key, T>
-
pair<const Key, T>
是 C++ STL 中的一个模板类,用于表示一组键值对,其中键类型为const Key
,值类型为T
。它是由头文件<utility>
提供的。 -
std::pair
是一个简单的容器类,用于保存两个值,并为这两个值提供了相应的访问方式。它有两个成员变量first
和second
,分别用于存储第一个值和第二个值。 -
在
std::pair<const Key, T>
中,键是一个const
类型,即不可修改。这意味着一旦设置了键的值,就无法再更改它。这样设计是为了确保std::map
等关联容器的键的稳定性和排序规则。 -
std::pair<const Key, T>
常常用来表示std::map
或其他类似容器中的一个元素。每个元素由一个键和一个值组成,键的类型是const Key
,即不可修改,值的类型是T
。
可以通过以下方式访问 pair<const Key, T>
对象中的键和值:
-
pair.first
:表示键的成员变量,类型为const Key
。 -
pair.second
:表示值的成员变量,类型为T
。
- map的构造函数
-
默认构造函数:
std::map<Key, T> 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<Key, Value> myMap; for (auto iter = myMap.begin(); iter != myMap.end(); ++iter) { const Key& key = iter->first; // 键 Value& value = iter->second; // 值 // 进行操作或访问 }
- 用途:可用于遍历
-
反向迭代器 (
reverse_iterator
) 和常量反向迭代器 (const_reverse_iterator
):- 用途:可用于以相反的顺序遍历
std::map
容器,并且可以修改或访问键值对。 - 示例用法:
std::map<Key, Value> myMap; for (auto rIter = myMap.rbegin(); rIter != myMap.rend(); ++rIter) { const Key& key = rIter->first; // 键 Value& value = rIter->second; // 值 // 进行操作或访问 }
- 用途:可用于以相反的顺序遍历
-
常量迭代器 (
const_iterator
) 和常量反向迭代器 (const_reverse_iterator
):- 用途:用于遍历
std::map
容器,但不能修改键值对。仅适用于const std::map
对象。 - 示例用法:
const std::map<Key, Value> 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<Key, Value> myMap; if (myMap.empty()) { // map为空 }
-
size()
:返回std::map
容器中键值对的数量。std::map<Key, Value> myMap; std::size_t count = myMap.size();
🍁元素访问函数
-
operator[]
:使用指定的键获取或设置相应的值。如果键不存在,会插入一个新的键值对。std::map<Key, Value> myMap; myMap[key] = value; // 设置键为key的值为value Value val = myMap[key]; // 获取键为key的值
-
at()
:根据指定的键获取相应的值,如果键不存在,会抛出std::out_of_range
异常。std::map<Key, Value> myMap; Value val = myMap.at(key); // 获取键为key的值
-
insert()
:插入一个新的键值对到std::map
容器中。std::map<Key, Value> myMap; myMap.insert(std::make_pair(key, value)); // 插入键值对(key, value)
-
erase()
:根据指定的键删除相应的键值对。std::map<Key, Value> myMap; myMap.erase(key); // 删除键为key的键值对
🚨🚨注意:对于operator[]
来说如果键不存在,会插入一个新的键值对而 at()
函数如果键不存在,会抛出 std::out_of_range
异常。
3. 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
1. 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++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新,不要错过任何精彩内容!文章来源:https://www.toymoban.com/news/detail-716400.html
再次感谢您的支持和关注。期待与您建立更紧密的互动,共同探索C++、算法和编程的奥秘。祝您生活愉快,排便顺畅!
文章来源地址https://www.toymoban.com/news/detail-716400.html
到了这里,关于【C++入门到精通】C++入门 —— map & multimap (STL)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!