由于某些原因其实就是作者咕咕咕了 ，这篇文章到2023年的最后一天才更出来
map的认识
关于map，这是一种常用的工具
基本上可以看成一个下标可以为任意的数组
注意，这里的任意，包括C++中所有类型的所有取值可能
也就是说下标是什么都行
但是同一个map里下标只能是同类型的
定义方式：
map<*,*>*
第一个*填下标类型，第二个填数组元素类型，第三个填数组名
常用操作：
为了方便，这里默认定义了一个叫mp的map
mp[x];
访问数组的下标为x的元素
这个下标也可以是负数
如果元素不存在，访问时会自动定义，并自动初始化为
{0,false,\0,“”,NULL}
等B东西(总之就是类似于int的0)
这个元素可以像正常的变量一样使用
mp.find(x)
查询下标为x的元素是（返回地址）否（返回mp.end()）存在
mp.count(x)
mp中q出现的次数
mp.empty()
不说了，是否为空
好啦常用的就这些
注意
map本质不是Hash！！！
底层是红黑树！！！
时间复杂度是
O
(
log
n
)
\mathcal O(\log n)
O(logn)！！
这复杂度，作为一棵树还不错，但作为一个数组…
依托答辩
路人甲：但是没有哈希冲突啊~
啊这答辩真香
其实吧，log n的复杂度，对付
1
0
5
10^5
105的数据还是没问题的（
O
(
n
log
n
)
\mathcal O(n \log n)
O(nlogn)）
路人乙：
1
0
5
10^5
105不是可以用
O
(
n
2
)
\mathcal O(n^2)
O(n2)的算法吗
路人甲：好像只有€€£ 的比赛可以
€€£ :禁赛三年！！必须禁赛三年
后置芝士
€€£
精彩内容
发表评论