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按照长度升序输出：

3，计数：假设定义一个map<string,int>map1，输入数据s，记为first，如果这个数据存在，map1[s]++; 如果不存在，map1[s]=1;

什么样的题适合使用map

1.去重类问题

2.可以打乱重新排列的问题

3.有清晰的一对一关系的问题