由于某些原因其实就是作者咕咕咕了 ,这篇文章到2023年的最后一天才更出来
关于map,这是一种常用的工具
基本上可以看成一个下标可以为任意的数组
注意,这里的任意,包括C++中所有类型的所有取值可能
也就是说下标是什么都行
但是同一个map里下标只能是同类型的
map<*,*>*
第一个*填下标类型,第二个填数组元素类型,第三个填数组名
为了方便,这里默认定义了一个叫mp的map<int,int>
mp[x];
访问数组的下标为x的元素
这个下标也可以是负数
如果元素不存在,访问时会自动定义,并自动初始化为
{0,false,\0,“”,NULL}
等B东西(总之就是类似于int的0)
这个元素可以像正常的变量一样使用
mp.find(x)
查询下标为x的元素是(返回1)否(返回0)存在
mp.count(x)
mp中q出现的次数
好啦常用的就这些
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)的算法吗
路人甲:好像只有€€£ 的比赛可以
€€£ :禁赛三年!!必须禁赛三年