在定义数组时(如int array[100]),其实是定义了一个从int型到int型的映射
比如array[0]=25、array[4]=36就分别是将0映射到25、将4映射到36
一个double型数组则是将int型映射到double型,
如db[0]=3.14,double[1]=0.01
但是,无论是什么类型
它总是将int型映射到其他类型
这似乎表现出一个弊端:
当需要以其他类型为关键字来做映射时,
会显得不太方便
例如有一本字典,
上面提供了很多的字符串和对应的页码,如果要用数组来表示“字符串——>页码”这样的对应关系
就会感觉不太好操作
这时,就可以用到map,因为map可以将任何基本类型
(包括STL容器)映射到任何基本类型(包括STL容器)
也就可以建立string型到int型的映射
【另一种情况】
需要判断给定的一些数字在某个文件中是否出现过
按照正常的思路,可以开一个bool 型hashTable[max_size]
通过判断hashTable[x]为true还是false来确定x是否在文件中出现
但是这会碰到一种问题:
如果这些数字很大(例如有几千位)那么这个数字就会开不了
而这时map就可以派上用场
因为可以把这些数字当成一些字符串
然后建立至int的映射(或者直接建立int至int的映射)
【头文件】
#include
1、map的定义
map 容器名;
与其他STL容器在定义上不一样,因为map需要确定映射前类型(键key)和映射后类型(值value)
所以需要在<>内填写两个类型
其中一个是键的类型
第二个是值得类型
如果是int型映射到int型,就相当于是普通的int型数组
但是如果是字符串到整型的映射,必须是string而不是char数组
map
这时因为char数组作为数组是不能被作为键值的。所以字符串作映射,只能用string
而map的剑河之也可以是STL容器
map
2、map容器内元素的访问
①通过下标访问
【注意】map的键是唯一的
mp[‘c’]=20;
②通过迭代器访问
定义方式与其他STL容器迭代器相同
【不同】
map迭代器的使用方式和其他STL容器的迭代器不同
因为map的每一对映射都有两个typename
这决定了必须通过一个it来同时访问键和值
事实上,map可以使用it->first来访问键
使用it->second来访问值
举个例子:
#include
#include
#include
#include
map会以键的大小从小到大的顺序自动排序
即按照a
在建立映射的过程中会自动实现从小到大的排序功能
map的底层实现是红黑树,unordered_map的底层实现是哈希表,
引用头文件(C++11):#include
定义:unordered_map
插入:例如将("ABC" -> 5.45)
插入unordered_map
中hash["ABC"]=5.45
查询hash["ABC"]
会返回5.45
判断key是否存在:hash.count("ABC") != 0
或 hash.find("ABC") != hash.end()
遍历
for (auto &item : hash)
{
cout << item.first << ’ ’ << item.second << endl;
}
或
for (unordered_map::iterator it = hash.begin(); it != hash.end(); it ++ )
{
cout << it->first << ' ' << it->second << endl;
}
通常来说我们一般用C++11的用法auto会更加方便简洁一点。
map与unordered_map中的插入,查询,判断key值存在,遍历都是相同的。
但是由于map与unordered_map的底层实现不同,map会将插入的所有值,按照key的顺序默认从小到大排序,unordered_map则是按照插入的顺序默认存在。
map比unordered_map的功能更多,但是牺牲的时间上的效率。
m a p map map
插 入 : O ( l o g n ) 插入:O(logn) 插入:O(logn)
查 询 : O ( l o g n ) 查询:O(logn) 查询:O(logn)
判 断 k e y 值 : O ( l o g n ) 判断key值:O(logn) 判断key值:O(logn)
u n o r d e r e d m a p unordered-map unorderedmap
插 入 : O ( 1 ) 插入:O(1) 插入:O(1)
查 询 : O ( 1 ) 查询:O(1) 查询:O(1)
判 断 k e y 值 : O ( 1 ) 判断key值:O(1) 判断key值:O(1)