map是 stl 的一个关联容器,名叫“映射”,何为“映射”?其实就是一个数组,但有了数组何必还需映射,这是一个高深的问题。
目录
一、map 简介
1.空间复杂度
map 类似于 vector,可以随时创建新的“键”(类似下标),避免浪费过多空间,具体实现如下:
pair<iterator, bool> insert(_Pp&& __p)
{
return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));
}
2.时间复杂度
map 使用了红黑树(一种自平衡二叉查找树),每次插入新的键和搜索时都只用 O(log size) 的时间复杂度,虽然数组只需 O(1) 的时间复杂度,但在空间方面数组极差。它与 vector 空间复杂度相同,但远优于 vector O(size) 的时间复杂度。具体实现在头文件 bits/stl_tree 中。
3.“键”的类型
map 键可以为任何类型,但必须具有小于比较模版或比较函数,在这一点上一个数组完全达不到。具体实现运用了类模板,如下:
template <class _Key, class _Tp, class _Compare = less<_Key>,
class _Allocator = allocator<pair<const _Key, _Tp> > >
二、 map 用法
1.声明
首先需要引用 “map” 头文件,如下:
#include <map>
声明时和一般模版类的声明方式一样,先注明类型(即 map )再填写模版,注意 map 的“键”和“值”的类型均需声明,最后为变量名。例如:
map <int,int> mp;
2.新增“键”
由于 map 中兼容了中括号(“[”、“]”)所以可以像访问数组一样访问或创建,如下:
mp[2]=1;
若只创建“键”而不赋值系统会默认为 0 ,例如:
mp[1];
cout << mp[1];
输出:
0
也可以使用 “insert” 函数,如下:
mp.insert(1,1);
三、map 遍历
1.使用 “iterator”
“iterator” 中文名为“迭代器”,访问方式如下:
for(map <int,int>::iterator it = mp.begin();it != mp.end();++ it)
{
cout << *it -> first << ' ' << *it -> second;
}
map 中有两个变量,"first" 和 "second",即“键”和“值”,
由于 "it" 是一个指针,所以需要 "->" 来访问。
2.使用 “auto”
c++11 以后,新增了一种 for 循环语法(如下), vector、list 等容器也可以这么访问。
for (auto i : v)
{
}
四、关于 map 的函数
1.find
查找 x 再 map 中的位置,若不存在这个键返回 “mp.end()”,各自返回指针,如下:
cout << mp.find(x) -> first;
2.clear
清空 map,vector 等容器也有这个函数,如下:
mp.clear();
3.erase
清除一个键对,或从 “begin” 到 “end” 的所有键对,注意参数需为指针,如下:
mp.eraser(mp.find(x));
mp.eraser(begin,end);
4.empty
查看 map 是否为空,如下:
if(mp.empty()) cout << "Yes";
5.swap
交换两个 map,如下:
mp.swap(temp);
6.count
查找 x 在 map 中出现了几次,如下:
cout << mp.count(x);
你学会了吗?
标签:map,cout,stl,复杂度,c++,如下,vector,mp From: https://blog.csdn.net/zhhg0123/article/details/136963562