map知识点总结整理

往期内容： STL总目录-超详细

目录

1. map是什么？
2. 变量声明及成员函数
3. 函数时间复杂度及返回值总表

小tip

map中有大量与set相似的内容，也可以说是set的一个进阶，推荐先学习一下set的知识，会对map的理解有很大帮助。

map是什么

与set与vector相同的，map也是c+ +标准模板库（STL）中提供的一个“容器”（即一个放置、包含数据的地方），更进一步说，它是一个关联容器，他能存入“一组对应的值”。那这时估计有些大佬应该能想到另一个类型——pair。
pair是什么呢？
简单地说，我们其实可以直接把pair理解为一个含有两个数据的结构体，如

struct pair {
    Type1 first;
    Type2 second;
};
//其中Type处是两个数据的类型，不必相同

简单的了解了pair，我们再回过头来看一看map,与pair相似的，map是以键->值储存的数据类型，即是由一个关键字（key）和一个对应的值（value）组成的。其中，key和value的类型是任意的，包括自己新定义好的类型。需要注意的是，key的存储和set一样具有互异性，即一个map类型中不会出现重复的key值，这样便保证了map中每个key都对应着一个确定的value值，而value的值可以是任意的（可重复）。
key值与set同样的，也具有有序性，即key值也会从小到大自动排好顺序。

综上，我们可以直接将map中的key值理解为是以set的形式储存的。再进一步说，map可以理解为一个set，但这个set中存储的每个值都还对应着一个另外的值。

如果觉得上面的文字还不是很好了解的话，下面我来举个栗子例子对比理解一下set和map这两个容器：一个班级中的同学是固定且不重复的，并且每个同学都有一个只属于自己的学号，那么set便只能够让我们存储这个班级中每个同学的名字或只能存储学号，而map能更进一步的存储班级中每个学号并将每个学号对应上相应的同学。
由此可见，map的功能相较于set似乎更为强大，而且在我们平时的做题过程中，map的应用也更为广泛。

变量声明及成员函数

注意：map类型侧重的是后面的value值，这意味着多数的函数都是对key值进行操作的，最终得到相应改变后key值对应的value值

头文件

map同样是有自己的头文件的
#include <map>
这应该没什么可说的吧…

定义（声明）（构造）

用法（格式）：map<类型1, 类型2> 名称
如：

#include <iostream>
#include <string>
#include <map> //打上头文件
using namespace std;

map<int, string> mapp; 
//构造一个key值为int类型，value值为string类型的名为“mapp”的map；

int main() {

    ...

    return 0;
}

插入元素

与set不同的是，作为一个更加高大上的容器，它的读入方式是多种多样且复杂的，这里我们介绍较为简单的两种方式。

第一种：

最最最最简单的一种方式，数组爱好者狂喜，没错，就是set用不了的a[i]式调用！应该不需要太多解释了，直接看一下打法：
用法（格式）：名称[key值] = value值

map<int, string> mapp;
mapp[0] = "Hello map!"; //即在mapp中  0->"Hello map!"
mapp[2] = "Hello RanRan!" //0->"Hello map!"  2->"Hello RanRan!"

还需要注意的是[]中的内容不再是存储的位置而是key值，不要把两个概念搞混了。

第二种：

虽然说map比set高级，但是.insert()该用还是要用的（真香），但由于map存储的不再是单一的一个值，所以我们当然也不能用.insert()单单的向map中直接放入一个值，而是应该放入一组对应的key值和value值，那这时候我们开头提到的pair类型就能派上用场了。
用法（格式）：名称.insert(pair<类型1，类型2>(key值，value值)) （pair的类型1和类型2与map的两个类型是相对应的）。

map<int, string> mapp;
mapp.insert(pair<int, string>(0, "Hello map!"));
//在mapp中存入一对数据：0->"Hello map!"

介绍完这两种输入方式，那么他们完全是等价的吗？

答案是否定的！我们已经说过，map实际上完全可以理解为一种特殊的set，就像说过的“key值是不能重复的”。那我们回忆一下set中的.insert()有什么特别的地方吗？

互异性 即如果存入的数据在set中已经存在即自动忽略。

那同样在map中，.insert()具有相同的性质，即如果插入的元素在原map中已经存在，如果此时用.insert()的方式读入的话，便会直接忽略这条指令。
而对于“数组式”的插入来说结果是不同的，当用“数组式”插入时，如果插入的一组数据的key值是已经存在的，这个时候这条插入的指令并不会被忽略，++而是让新的value值覆盖原本对应的value值。
如：

map<int, string> mapp;
mapp[1] = "Hello map!";
//构造一个map容器并 令：1->"Hello map!"

//用.insert()插入另一组key值为1的数据
mapp.insert(pair<int, string>(1, "Hello RanRan!"));
//此时mapp中依然有 1->"Hello map!"

//用数组式插入另一组key值为1的数据
mapp[1] = "Hello RanRan!";
//此时mapp有新的 1->"Hello RanRan!"

调取元素

这个就直接用最简单的数组式应该最方便了吧…
迭代器当然也可以，放在后面开专栏了Orz
用法（格式）：名称[key值] -> 返回key值对应的value值

map<int, string> mapp;
mapp[1] = "Hello map!"
//构造

cout << mapp[1] << endl;
//输出：Hello map!

查看元素组数 .size()

这个应该也没太多可说的，大家应该再熟悉不过了吧…如果我们想要知道map中共存入了几组元素，.size()可以帮我们解决。
用法（格式）：名称.size()

map<int, string> mapp;
mapp[123] = "Hello map!";
//构造

cout << mapp.size() << endl;
//输出：1

检查map是否为空 .empty()

如名…
用法（格式）：名称.empty()

map<int, string> mapp;
//构造

//mapp.empty() == true;
//此时还没有插入任何元素，所以map中是空的

mapp[123] = "Hello map!";
//mapp.empty() == false;
//插入了一组元素，此时mapp以不为空

数某组元素（key值）出现次数 .count()

如名…
还是那句话，map作为一个特殊的set，它的.count()和set中的也是一样的，由于互异性的存在，它的返回值只能是1或0，所以基本上唯一的用途便是判断一个元素是否存在了…
用法（格式）：名称.count(x)这里的x是一个key值而不能是一个value值！！！

map<int, string> mapp;
mapp[0] = "Hello map!";
//构造

cout << mapp.count(0) << endl;
//由于mapp中存在0这个key值且只能出现一次，所以返回1
//输出：1

cout << mapp.count(1) << endl;
//由于mapp中不存在key值为1的数据，所以返回0
//输出：0

cout << mapp.count("Hello map!") << endl;
//.count()只能查找key值，而我们定义的mapp的key值是一个int类型的变量，所以你得到的只能是 编译错误

迭代器

没有错，该来的还是来了QAQ
迭代器的基本概念在set的讲解中已经涵盖了，这里不再赘述，我们直接来看一下它的用法。
其实基本的格式和set中的基本上是一样的…那就直接上代码吧…
用法（格式）：map<类型1, 类型2>::iterator 迭代器名称
如：

map<int, string> mapp;
mapp[123] = "Hello map!";
mapp[456] = "Hello RanRan!";
mapp[789] = "QAQ";
//构造

map<int, string>::iterator it;//注意迭代器的两个类型必须与所要查看的map的两个类型完全对应好
//构造一个指向key值为int类型，value值为string类型的map的迭代器it

这样我们便拥有了一个迭代器，但这个迭代器依然是没有值的，它还没有指向任何东西，所以我们需要给它一个初始值，这个值可以是.begin()或.end()，但必须是你要查看的map类型中的位置。

此处.begin()和.end()两个函数与set中的.begin()和.end()完全相同，分别返回的是map中第一组元素的迭代器和最后一组元素的下一位的迭代器。一定要注意.end()指向的并不是最后一组元素，当你输出*(mapp.end())时不会返回任何结果，.end()--指向的才是最后一组元素

接上段代码：

...
it = mapp.begin();
//使迭代器指向mapp的第一个元素

//it = mapp.end();

当我们的迭代器有了一个初始的值，接下来就可以开始遍历了：
接上段代码：

...
for (it; it != mapp.end(); it++) {

}

但我们知道map中的元素都是成组的，而迭代器指向的是这一组数组的整体，所以如何输出迭代器指向的数据组中的key值或value值呢？
这里，我们引入一个（或者说一对两个）新的符号->，就是这个长得和小箭头一样的符号，他便能使迭代器的指向更加精确，精确到这组数据中的key值或value值。在map中，我们把key值作为一级数据（first）而value值作为二级数据（second），那么，迭代器名称->first便可以得到迭代器当前指向的一组数据中的key值，同理，迭代器名称->second可以得到这组数据中的value值。
用法（格式）：迭代器名称 -> first/second

...
for (it; it != mapp.end(); it++) {
    cout << it->first << endl;
}

//依次输出mapp中所有的key值
for (it; it != mapp.end(); it++) {
    cout << it->second << endl;
}
//依次输出mapp中所有的value值

删除元素 .erase()

基本用法：删除某一key值及其对应的value值
用法（结构）：名称.erase(x)x值为某一key值

map<int, string> mapp;
mapp[123] = "Hello map!";
//构造

//mapp.empty() == false;
//此时mapp中有一组元素123->Hello map!

mapp.erase(123);
//mapp.empty() == true;
//仅有的一组元素被清除

其他用法：
1.名称.erase(x)中x除了可以是一个key值外，还可以是迭代器
2.由于.erase()会有一个返回值，所以

int n = mapp.erase(123); //如果删除了返回1，否则返回0

3.可以用迭代器将map范围清空（如清空），与set中相同的，清除的范围为[first, last)内的所有元素

a.erase(a.begin(), a.end()); //清空

删除所有元素 .clear()

如名字，清空一个map
用法（结构）：名称.clear()

map<int, string> mapp;
mapp[123] = "Hello map!";
mapp[456] = "Hello RanRan!";
mapp[789] = "QAQ";

cout << mapp.size() << endl;
//输出：3

mapp.clear();//清空
cout << mapp.size() << endl;
//输出：0

查找一个key值是否被存储 .find()

与set中的.find()函数相同，它的返回值固定为一个迭代器，如果查找的元素（key值）存在，返回key值所在一组元素的迭代器的值，否则返回.end()的值。

map<int, string> a;
//构造
a[0] = "Hello map!";
//存入
map<int, string>::iterator it;
//构造一个迭代器
it = a.find(0);
//迭代器的值更新为指向key值为0的一组元素
cout << it->second << endl;
//输出key值为0的这组元素的value值
//输出：Hello map!

.lower_bound() & upper _bound()

与set中的用法依然相同…
.lower_bound()表示=> 查找key值≥x的元素中最小的一个，并返回指向该元素的迭代器
.upper_bound()表示=> 查找key值>x的元素中最小的一个，并返回指向该元素的迭代器
用法（格式）：名称.lower_bound() 名称.upper_bound()

map<int, string> mapp;
mapp[123] = "Hello map!";
mapp[456] = "Hello RanRan!";
mapp[789] = "QAQ";

map<int, string>::iterator it;

it = mapp.lower_bound(456);
cout << it->second << endl;
//≥456的最小key值即为456，所以迭代器指向456->Hello RanRan!这组数据
//输出：Hello RanRan!

it = mapp.upper_bound(456);
cout << it->second << endl;
//>456的最小key值为789，所以迭代器指向789->QAQ这组数据
//输出：QAQ

Ps：特殊的，对于比map中最大的元素大的元素，两个函数返回的都是mapp.end()

各函数时间复杂度及返回值

尾声

制作较为仓促，有问题请指正Orz
全文markdown语法共3600余字，感谢您耐心读完~
希望能被更多人看到（疯狂暗示）

ヾ(•ω•`)o