C++STL中的map

map简介
map是STL中的一个关联式的容器,可以建立key(first)和value(second)一对一的联系,由key映射到value。
map内部自建了一棵红黑二叉树,可以对数据进行自动排序,所以map里的数据都是有序的,这也是我们通过map简化代码的原因。
使用map需要声明头文件#include<map>

map特点
自动建立key-value的对应关系,key和value可以是你需要的任何类型。
快速查找,删除记录,根据key值查找的复杂度基本上是long(n)
key和value一一对应的关系可以去重
-map的基本操作
-构造map:
map<int,string> map_student
//定义了一个由int映射到string的map,并命名为map_student
这里的first和second的数据类型可以是任意类型的数据,包括自定义的数据类型。
向map中插入数据:
1.这里通常的方法是把map用数组的方法插入数据。
-图片说明
可以看出第二次的操作覆盖了第一次的key对应的value。
2.用insert()函数插入数据//(1)(2)等价
(1)insert(map<int,string>::value_type(1,"student1"));
(2)insert(make_pair(1,"student1"));
与方法1不同的是,insert()函数体现了映射的一一对应这一特性,即当map中有这个key时,就不能用insert插入数据了,但是用数组的方法1是可以覆盖原数据的。
图片说明
使用find()查找
用find函数来定位数据出现位置它返回的是一个迭代器。当数据出现时,它返回的是数据所在位置的迭代器。如果map中没有要查找的数据,它返回的迭代器等于end函数返回的迭代器。
图片说明
使用count函数
count函数返回的是数据在映射中出现的次数,即0或1.无法定位数据在映射中出现的位置。
图片说明
map在题目中的应用
1.去重 2.排序 3.计数
去重:利用映射的一一对应性,把可能出现重复的数据设置为key值以达到去重的目的。
排序(按照key排序):map是STL中的一个模版类,以下是map的定义:

template < class Key, class T, class Compare = less<Key>,  
           class Allocator = allocator<pair<const Key,T> > > class map;  

其实map里应该有四个变量(第四个不用看),而第三个变量是排序方式,如果我们不指定排序方式的话,按照平时的写法,map就会按照模版中的less<key>进行排列。</key>

如果我们想按照我们自己的想法来对key排序呢?
我们先来看一下class Compare = less<key>的类模版:</key>

template <class T> struct greater : binary_function <T,T,bool> {  
  bool operator() (const T& x, const T& y) const  
    {return x>y;}  
};  

抓关键点:return的值是较大的,即为key升序排列。
自定义Compare类(依葫芦画瓢)
我们可以自己定义一个Compare类,把这个类按照map的模版,加在本该在Compare类的位置上,就可以自定义key的排序方式了。

比如我建了一个学生-成绩的map,原先是按照学生名字的字典序
排序的。

如果我想按照降序呢?学生姓名长度呢?

  • 按照默认cmp的输出:
  • 按照默认cmp的输出
  • 降序输出:
    图片说明
  • 自定义cmp按照长度升序输出:
    图片说明
    3,计数:假设定义一个map<string,int>map1,输入数据s,记为first,如果这个数据存在,map1[s]++; 如果不存在,map1[s]=1;

什么样的题适合使用map
1.去重类问题
2.可以打乱重新排列的问题
3.有清晰的一对一关系的问题

全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务