STL—map
一、什么是map
map是映射,我们在定义数组的时候int a[100];
其实是一个int --> int
的映射,比如a[3] = 5
的含义就是把3映射到5,一个double
类型的数组就是一个int --> double
的映射,这里我们就能知道我们数组的一个弊端,就是只能实现int --> typename
的映射,如果我们要表示一个字典的话,想要实现 字符串到页码的映射的时候显然就不好操作,这里,我们就可以用到map
,map
的作用就是可以把任何基本类型(包括STL),map
还可以处理这么一种特殊情况:判断一些数字是否出现过,我们通常会开一个bool
数组去判断,但是有一个问题就是当这个数字十分大的时候比如1e100
的数量级的时候,这个数组就不能开,这个时候就可以用到map
,我们可以把很大的数字当成字符串,从而建立string --> int
的映射
我们在使用map
之前,需要添加头文件#include <map>
二、map的操作
1.map的定义
map<typename1, typename2> m;
- 1
我们需要在<>
中添加两种数据类型,表达的是建立一个typename1 --> typename2
的映射
如果是字符串到整型的映射,必须使用string
不能使用char
数组
map<string, int> m;
- 1
当然,我们也可以和其他的STL容器混合起来一起使用
map<set<int>, int> m;
- 1
2.map内元素的访问
(1)通过下标访问
和访问数组是一个道理,比如对于一个map<char, int> m;
,我们可以直接通过m['a']
去访问'a'
所对应的整数,同样,它在被赋予新值的时候会被覆盖
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 2;
m['c'] = 3;
cout << m['c'];
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
输出结果为:3
(2)通过迭代器访问
定义一个map
迭代器
map<typename1, typename2>::iterator it;
- 1
typename1
,typename2
就是我们在定义map的时候的类型,我们把typename1
称为键
map
通过it -> first
,it -> second
去分别访问typename1
,typename2
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
for (map<char, int>::iterator it = m.begin(); it != m.end(); it ++ )
cout << it -> first << ' ' << it -> second << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
当然我们可以用auto
去缩写
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
for (auto it = m.begin(); it != m.end(); it ++ )
cout << it -> first << ' ' << it -> second << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
输出结果为:
a 1
b 2
c 3
我们发现,map
会以typename
从小到大进行自动排序
3.map中的函数
(1)find()
m.find(key);
返回值为key
的映射的迭代器,时间复杂度是O(logN),N为map
中映射的个数
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
map<char, int>::iterator it = m.find('b');
cout << it -> first << ' ' << it -> second << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
输出结果为:b 2
(2)erase()
删除单个元素
m.erase(it);
,it
为需要删除元素的迭代器,时间复杂度为O(1)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
map<char, int>::iterator it = m.find('b');
m.erase(it); //删除 b 2
for (auto it = m.begin(); it != m.end(); it ++ )
cout << it -> first << ' ' << it -> second << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
输出结果为:
a 1
c 3
m.erase(key);
,key
为欲删除的映射的键,时间复杂度为O(logN),N为map
内元素的个数
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
m.erase(m.find('b')); //删除 b 2
for (auto it = m.begin(); it != m.end(); it ++ )
cout << it -> first << ' ' << it -> second << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
删除一个区间内的所有元素
m.erase(first, last);
,其中first
是需要删除区间的起始迭代器,last
为需要删除的区间的末尾迭代器的下一个地址,即删除左闭右开区间[first, last)
,时间复杂度为O(last - first)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
m.erase(m.find('b'), m.end());
for (auto it = m.begin(); it != m.end(); it ++ )
cout << it -> first << ' ' << it -> second << endl;
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
输出结果为:a 1
(4)size()
m.size()
用来获得map
中映射的对数,时间复杂度为O(1)
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
cout << m.size();
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
输出结果为:3
(4)clear()
m.clear();
用来清空map
中的所有元素,时间复杂度为O(N),N为map
中元素的个数
#include <iostream>
#include <map>
using namespace std;
int main()
{
map<char, int> m;
m['c'] = 3;
m['a'] = 1;
m['b'] = 2;
m.clear();
cout << m.size();
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
输出结果为:0
文章来源: chen-ac.blog.csdn.net,作者:辰chen,版权归原作者所有,如需转载,请联系作者。
原文链接:chen-ac.blog.csdn.net/article/details/116395272
- 点赞
- 收藏
- 关注作者
评论(0)