STL容器——map

发布时间:2023年12月31日

由于某些原因其实就是作者咕咕咕了 ,这篇文章到2023年的最后一天才更出来

map的认识

关于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)的算法吗

路人甲:好像只有€€£ 的比赛可以

€€£ :禁赛三年!!必须禁赛三年

后置芝士

€€£

文章来源:https://blog.csdn.net/zth413021/article/details/135318221
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。