1. 简介

map 是 key-value 构成的集合。

2. 操作

map 是键值对 <key,value> 构据集合。key 必须唯一。

主要用来查找key对应value,要求key必须是可排序的，必须支持<比较运算符。map默认是以key升序存放键值对<key,value>数据，比较适合二分查找。 map内部结构

map 使用 pair<key,value> 类模板保存 key 与 value，pair<key,value> 有两个 public 成员变量: first 和 second , first 存放 key , second 存放 value。在 map 里面可以使用 map<>::value_type 表示 pair<key,value>。

typedef pair<key,value> value_type;

2.1 初始化

默认构造(可带参数)复制构造范围赋值构造

初始化时必须给 map<> 类模板同时设置key与value的类型模板实参。 实参类型不限于基本类型、类类型(class、struct、union)，还可以是容器模板。

a.只能前面的键找后面的数值；后面的找前面的返回空字符；

cout << fruits["香蕉"] <<endl; //a.只能前面的键找后面的数值； cout << fruits["banana"] <<endl; //a.后面的找前面的返回空字符；

b.找到了返回内容，找不到返回空字符；可以用if判断

if(fruits.count("香蕉")==1){ //b.找到了返回内容，找不到返回空字符；，可以用if判断 cout << fruits["香蕉"] <<endl; } 完整案例 #include <iostream> #include <map> using namespace std; int main() { map<string,string> fruits ={ {"香蕉","banana"}, {"苹果","apple"}, {"橘子","orange"} }; for(auto p: fruits){ //c++11的常见用法； cout << p.first <<"\t" << p.second << endl; } cout << fruits["香蕉"] <<endl; //a.只能前面的键找后面的； cout << fruits["banana"] <<endl; //a.后面的找前面的返回空字符； if(fruits.count("香蕉")==1){ //b.找到了返回内容，找不到返回空字符；，可以用if判断 cout << fruits["香蕉"] <<endl; } return 0; }

2.2 修改&添加&删除&遍历常见的用法

a.遍历常见的用法

for(auto p: fruits){ //c++11的常见用法； cout << p.first <<"\t" << p.second << endl; }

b.删除：通过删除键来删除键值对

fruits.erase("香蕉");

c.插入：（法1）pair()通过类型插入键值对； （法2:常用）make_pair()直接添加键值对

fruits.insert(pair<string,string>("樱桃","cherry"));//c1.pair()通过类型插入键值对； fruits.insert(make_pair("梨子","pear"));//c2.make_pair()直接添加键值对

d.修改：通过修改值来修改键值对

fruits["橘子"] = "juice"; //d.修改：通过修改值来修改键值对 完整案例 #include <iostream> #include <map> using namespace std; int main() { map<string,string> fruits ={ {"香蕉","banana"}, {"苹果","apple"}, {"橘子","orange"} }; fruits.erase("香蕉"); //b.删除：通过删除键来删除键值对 for(auto p: fruits){ //a.c++11的常见遍历用法； cout << p.first <<"\t" << p.second << endl; } cout << endl; fruits["橘子"] = "juice"; //d.修改：通过修改值来修改键值对 fruits.insert(pair<string,string>("樱桃","cherry"));//c1.pair()通过类型插入键值对； fruits.insert(make_pair("梨子","pear"));//c2.make_pair()直接添加键值对 for(auto p: fruits){ //c++11的常见用法； cout << p.first <<"\t" << p.second << endl; } cout << endl; map<string,string>::iterator it = fruits.find("苹果"); if(it != fruits.end()){ cout << it ->first << it->second << endl; } return 0; }

2.3 面试常考

2.3.1 (面试题56)数字和出现的次数

数字和出现的次数

step1. 键值对表示<数字，次数>,首先遍历向量nums,将其存入map; 空值插入1;非空的话，次数自增

map<int,int> m; //a.键值对表示<数字，次数> for(auto n:nums){ //b1.首先遍历向量nums,将其存入map if(m.count(n)==0){ m.insert(make_pair(n,1));//b2.空值插入1 }else{ ++m[n]; //b3.非空的话，次数自增 }

step2 遍历map,次数为1的将键存入到vector

for(auto p:m){ //c.遍历map,次数为1的将键存入到vector if(p.second == 1){ res.push_back(p.first); } } 完整代码 #include <iostream> #include <map> #include <vector> using namespace std; vector<int> timesNumbers(vector<int>& nums){ map<int,int> m; //a.键值对表示<数字，次数> for(auto n:nums){ //b1.首先遍历向量nums,将其存入map if(m.count(n)==0){ m.insert(make_pair(n,1));//b2.空值插入1 }else{ ++m[n]; //b3.非空的话，次数自增 } } vector<int> res; for(auto p:m){ //c.遍历map,次数为1的将键存入到vector if(p.second == 1){ res.push_back(p.first); } } return res; } int main() { vector<int> vec = {4,1,4,6}; vector<int> res = timesNumbers(vec); for(auto n:res){ cout << n << "\t"; } cout << endl; return 0; }

2.3.2 (面试题56-2)数字出现的次数

数字出现的次数 step1. 键值对表示<数字，次数>,首先遍历向量nums,将其存入map; 空值插入1;非空的话，次数自增

map<int,int> m; //a.键值对表示<数字，次数> for(auto n:nums){ //b1.首先遍历向量nums,将其存入map if(m.count(n)==0){ m.insert(make_pair(n,1));//b2.空值插入1 }else{ ++m[n]; //b3.非空的话，次数自增 }

step2. 遍历nums,将次数为1的键返回；

for(auto p:m){ //c.将次数为1的键返回； if(p.second == 1){ res=p.first; } } return res; } 完整代码 int singleNumber(vector<int>& nums) { map<int,int> m; //a.键值对表示<数字，次数> for(auto n:nums){ //b1.首先遍历向量nums,将其存入map if(m.count(n)==0){ m.insert(make_pair(n,1));//b2.空值插入1 }else{ ++m[n]; //b3.非空的话，次数自增 } } int res; for(auto p:m){ //c.遍历nums,将次数为1的键返回； if(p.second == 1){ res=p.first; } } return res; }

3.标准

迭代器 迭代器作用c.begin()头迭代器c.end()尾迭代器c.rbegin()反向头迭代器c.rend()反向尾迭代器

与vector相似。

数据量操作 函数作用c.size()大小c.max_size()最大大小c.empty()判空c.clear()清空

3.1 添加数据

insert插入pair<>数据 #include <iostream> #include <map> #include <algorithm> using namespace std; void Display(map<int,int>::value_type const& val){ cout << val.first <<" " << val.second << endl; } int main(){ map<int,int> m; for(int i=0;i<10;i++){ m.insert(pair<int,int>(i,i*10)); } for_each(m.begin(),m.end(),Display); } insert插入map<>::value_type数据 #include <iostream> #include <map> #include <algorithm> using namespace std; void Display(map<int,int>::value_type const& val){ cout << val.first <<" " << val.second << endl; } int main(){ map<int,int> m; for(int i=0;i<10;i++){ m.insert(map<int,int>::value_type(i,i*10)); } for_each(m.begin(),m.end(),Display); } insert插入make_pair数据 make_pair是一个函数模板，类似与如下实现： template<class K,class V) inline pair<K,V> make_pair(K const& k,V const& v){ return pair<K,V>(k,v); } #include <iostream> #include <map> #include <algorithm> using namespace std; void Display(map<int,int>::value_type const& val){ cout << val.first <<" " << val.second << endl; } int main(){ map<int,int> m; for(int i=0;i<10;i++){ m.insert(make_pair(i,i*10)); } for_each(m.begin(),m.end(),Display); } 下标运算符[]添加数据 #include <iostream> #include <map> #include <algorithm> using namespace std; void Display(map<int,int>::value_type const& val){ cout << val.first <<" " << val.second << endl; } int main(){ map<int,int> m; for(int i=0;i<10;i++){ m[i] = i*10; } for_each(m.begin(),m.end(),Display); }

说明：

map只有在访问key,如果key不存在则会创建，反之，使用已存在的<key,val>。对于已存在的key，insert()操作是无法插入数据，可以通过判断insert()的返回值pair<map<>::iterator,bool>，得知是否插入成功。 vector为空，是否可以使用下标运算符添加数据?例如：vec[2]=3;

3.2 遍历

迭代器for循环 for(map<int,int>::iterator it = m.begin();it != m.end();it++){ cout << "[" << it->first << "]=" << it->second() << endl; } for_each()循环 定义函数指针 inline void Display(map<int,int>::value_type const& val){ cout << "[" << val.first << "]=" << val.second << endl; }

执行for_each

for_each(m.begin(),m.end(),Display); C++11auto迭代器写法 for(auto it = m.begin();it != m.end();it++){ cout << "[" << it->first << "]=" << it->second() << endl; } C++11 for-loop-scope迭代器写法 for(auto p : m){ cout << "[" << p.first << "]=" << p.second << endl; } C++11 for_each()与lamdba表达式 for_each(m.begin(),m.end(),[](map<int,int>::value_type& p){ cout << "[" << p.first << "]=" << p.second << endl; });

3.3key查找

count()判断key是否存在 if(m.count(key) == 1){ ... } find()判断key是否存在以及位置 map<int,int>::iterator it = m.find(key); if(m.end() != it){ ... } 下标运算符[] 下标运算符[]

如果key不存在，默认创建。

3.4 区域查找

成员变量作用m.lower_bound(key)key下边界m.upper_bound(key)key上边界m.equal_range(key)key上下边界

3.5 删除

关键字删除 m.erase(key); 迭代器删除 m.erase(m.begin()); 区域删除 m.erase(it_a,it_b);

3.6 排序

默认按照key升序排列。自定义排序是，可以在实例化加上key的comp仿函数，重载<运算符。

map<key类型,value类型,comp> m;

4. 实例

1.两个数组合并成一个map

#include <iostream> #include <map> #include <iterator> #include <algorithm> using namespace std; void Display(map<int,int>::value_type const& val){ cout << "[" << val.first << "]=" << val.second << endl; } class MapMaker{ public: MapMaker(map<int,int>& m):m_(m){} inline bool operator()(int k,int v){ return m_.insert(make_pair(k,v)).second; } private: map<int,int>& m_; }; int main(){ map<int,int> m; int arr1[] = {1,2,1,4,5,2,3,4}; int arr2[] = {19,29,39,49,59,69,79,89}; bool res[8]; transform(arr1,arr1+8,arr2,res,MapMaker(m)); cout<< boolalpha; copy(res,res+8,ostream_iterator<bool>(cout,",")); cout<< noboolalpha << endl; for_each(m.begin(),m.end(),Display); }

在C++11中transform可以使用lamdba表达式，改写成

transform(arr1,arr1+8,arr2,res,[&m](int k,int v){ return m.insert(make_pair(k,v)).second; }); 把map的key和value各自分解成一个vector #include <iostream> #include <algorithm> #include <iterator> // ostream_iterator #include <vector> #include <map> using namespace std; // 仿函数 class Spliter{ public: Spliter(vector<int>& k,vector<int>& v):k_(k),v_(v){} void operator()(map<int,int>::value_type const& pair){ k_.push_back(pair.first); v_.push_back(pair.second); } private: vector<int>& k_; vector<int>& v_; }; int main () { map<int,int> m; for(int i=0;i<10;i++){ m[i] = i*10; } vector<int> keys; vector<int> values; for_each(m.begin(),m.end(),Spliter(keys,values)); copy(keys.begin(),keys.end(),ostream_iterator<int>(cout,",")); cout << endl; copy(values.begin(),values.end(),ostream_iterator<int>(cout,",")); return 0; }

在C++11中for_each可以使用lamdba表达式，改写成

for_each(m.begin(),m.end(),[&keys,&values](map<int,int>::value_type const& pair){ keys.push_back(pair.first); values.push_back(pair.second); });

使用C++11 for-loop-scope语法

for(auto p:m){ keys.push_back(p.first); values.push_back(p.second); } map的key和value互换