四、STL容器：map

4 map 4.1 简介

map是key-value构成的集合。

4.2 操作

map是键值对构据集合。key必须唯一。

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

map内部结构：
1、map使用pair类模板保存key与value；
2、pair有两个public成员变量:first和second，first存放key,second存放value。
3、在map里面可以使用map<>::value_type表示pair。

typedef pair value_type;

4.2.1 初始化

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

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

4.2.2 基本操作

迭代器

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

注：与vector相似。

数据量操作

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

4.2.3 添加数据

1、insert插入pair<>数据

#include 
#include 
#include 
using namespace std;
void Display(map::value_type const& val){
    cout << val.first <<" " << val.second << endl;
}
int main(){
    map m;
    for(int i=0;i<10;i++){
        m.insert(pair(i,i*10));
    }
    for_each(m.begin(),m.end(),Display);
}

2、insert插入map<>::value_type数据

#include 
#include 
#include 
using namespace std;
void Display(map::value_type const& val){
    cout << val.first <<" " << val.second << endl;
}
int main(){
    map m;
    for(int i=0;i<10;i++){
        m.insert(map::value_type(i,i*10));
    }
    for_each(m.begin(),m.end(),Display);
}

3、insert插入make_pair数据

make_pair是一个函数模板，类似与如下实现：

template make_pair(K const& k,V const& v){
    return pair(k,v);
}

#include 
#include 
#include 
using namespace std;
void Display(map::value_type const& val){
    cout << val.first <<" " << val.second << endl;
}
int main(){
    map m;
    for(int i=0;i<10;i++){
        m.insert(make_pair(i,i*10));
    }

    for_each(m.begin(),m.end(),Display);
}

4、下标运算符[]添加数据

#include 
#include 
#include 
using namespace std;
void Display(map::value_type const& val){
    cout << val.first <<" " << val.second << endl;
}
int main(){
    map m;
    for(int i=0;i<10;i++){
        m[i] = i*10;
    }
    for_each(m.begin(),m.end(),Display);
}

注：map只有在访问key,如果key不存在则会创建，反之，使用已存在的。对于已存在的key，insert()操作是无法插入数据，可以通过判断insert()的返回值pair::iterator,bool>，得知是否插入成功。

4.2.4 遍历

1、迭代器for循环

for(map::iterator it = m.begin();it != m.end();it++){
        cout << "[" << it->first << "]=" << it->second() << endl; 
}

2、for_each()循环

定义函数指针

inline void Display(map::value_type const& val){
    cout << "[" << val.first << "]=" << val.second << endl;
}

执行for_each

for_each(m.begin(),m.end(),Display);

3、C++11auto迭代器写法

for(auto it = m.begin();it != m.end();it++){
        cout << "[" << it->first << "]=" << it->second() << endl; 
}

4、C++11 for-loop-scope迭代器写法

for(auto p : m){
    cout << "[" << p.first << "]=" << p.second << endl;
}

5、C++11 for_each()与lamdba表达式

for_each(m.begin(),m.end(),[](map::value_type& p){
    cout << "[" << p.first << "]=" << p.second << endl;
});

4.2.5 key查找

1、count()判断key是否存在

if(m.count(key) == 1){
     ...
}

2、find()判断key是否存在以及位置

map::iterator it = m.find(key);
if(m.end() != it){
     ...
}

3、下标运算符[]

m[key];

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

4.2.6 区域查找

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

4.2.7 删除

1、关键字删除

m.erase(key);

2、迭代器删除

m.erase(m.begin());

3、区域删除

m.erase(it_a,it_b);

4.2.8 排序

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

map m;

4.3 实例

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

#include 
#include 
#include 
#include 
using namespace std;
void Display(map::value_type const& val){
    cout << "[" << val.first << "]=" << val.second << endl;
}
class MapMaker{
public:
    MapMaker(map& m):m_(m){}
    inline bool operator()(int k,int v){
        return m_.insert(make_pair(k,v)).second;
    }
private:
    map& m_;
};
int main(){
    map 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(cout,","));
    cout<< noboolalpha << endl;
    for_each(m.begin(),m.end(),Display);
}

true,true,false,true,true,false,true,false,
[1]=19
[2]=29
[3]=79
[4]=49
[5]=59

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

transform(arr1,arr1+8,arr2,res,[&m](int k,int v){
    return m.insert(make_pair(k,v)).second;
});

2、把map的key和value各自分解成一个vector

#include 
#include 
#include  // ostream_iterator
#include 
#include 
using namespace std;
// 仿函数
class Spliter{
public:
    Spliter(vector& k,vector& v):k_(k),v_(v){}
    void operator()(map::value_type const& pair){
        k_.push_back(pair.first);
        v_.push_back(pair.second);
    }
private:
    vector& k_;
    vector& v_;
};
int main () {
  map m;
  for(int i=0;i<10;i++){
    m[i] = i*10;
  }
  vector keys;
  vector values;
  for_each(m.begin(),m.end(),Spliter(keys,values));
  copy(keys.begin(),keys.end(),ostream_iterator(cout,","));
  cout << endl;
  copy(values.begin(),values.end(),ostream_iterator(cout,","));
  cout << endl;
  return 0;
}

0,1,2,3,4,5,6,7,8,9,
0,10,20,30,40,50,60,70,80,90,

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

for_each(m.begin(),m.end(),[&keys,&values](map::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);
}

3、map实现采用映射实现字典查找

#include 
#include 

using namespace std;

int main(){
    // map映射 dict 目录/字典
    map dict = {
    	//key    value
	{"Apple","苹果"},
    	{"Orange","橘子"},
    	{"Banana","香蕉"},
	{"苹果","Apple"},
    	{"橘子","Orange"},
    	{"香蕉","Banana"},
    	{"Orange","橘子"}, //重复key忽略
    };

    dict["Car"] = "汽车"; //添加数据
    dict.insert(pair("汽车","Car"));
    dict.insert(make_pair("Cat","猫"));
    dict.insert({"猫","Cat"}); //C++11
    dict["Car"] = "小汽车"; //修改数据

    map::iterator it = dict.begin();
    while(it != dict.end()){
    	//pair  first,second
	cout << it->first << " " << it->second << endl;
    	it++;
    }

    string s;
    cin >> s; 
    //if(dict.count(s) == 1){
    if(dict.find(s) != dict.end()){
    	cout << dict[s] << endl;
    }else{
    	cout << "不存在" << endl;
    }
}

Apple 苹果
Banana 香蕉
Car 小汽车
Cat 猫
Orange 橘子
橘子 Orange
汽车 Car
猫 Cat
苹果 Apple
香蕉 Banana
猫 
Cat

四、STL容器：map

C/C++/C#相关栏目本月热门文章