1. 簡介

map是key-value構(gòu)成的集合。

2. 操作

map是鍵值對<key,value>構(gòu)據(jù)集合。key必須唯一。

• 主要用來查找key對應(yīng)value,要求key必須是可排序的，必須支持<比較運(yùn)算符。
• map默認(rèn)是以key升序存放鍵值對<key,value>數(shù)據(jù)，比較適合二分查找。

map內(nèi)部結(jié)構(gòu)

map使用pair<key,value>類模板保存key與value，pair<key,value>有兩個(gè)public成員變量:first和second,first存放key,second存放value。在map里面可以使用map<>::value_type表示pair<key,value>。

typedef pair<key,value> value_type;

2.1 初始化

1. 默認(rèn)構(gòu)造(可帶參數(shù))
2. 復(fù)制構(gòu)造
3. 范圍賦值構(gòu)造

初始化時(shí)必須給map<>類模板同時(shí)設(shè)置key與value的類型模板實(shí)參。
實(shí)參類型不限于基本類型、類類型(class、struct、union)，還可以是容器模板。

2.2 基本操作

• 迭代器

與vector相似。

• 數(shù)據(jù)量操作

2.3 添加數(shù)據(jù)

1. insert插入pair<>數(shù)據(jù)

#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);
}

2. insert插入map<>::value_type數(shù)據(jù)

#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);
}

3. insert插入make_pair數(shù)據(jù)

make_pair是一個(gè)函數(shù)模板，類似與如下實(shí)現(xiàn)：

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);
}

4. 下標(biāo)運(yùn)算符[]添加數(shù)據(jù)

#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不存在則會(huì)創(chuàng)建，反之，使用已存在的<key,val>。對于已存在的key，insert()操作是無法插入數(shù)據(jù)，可以通過判斷insert()的返回值pair<map<>::iterator,bool>，得知是否插入成功。

vector為空，是否可以使用下標(biāo)運(yùn)算符添加數(shù)據(jù)?例如：vec[2]=3;

2.4 遍歷

• 迭代器for循環(huán)

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

• for_each()循環(huán)
  定義函數(shù)指針

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

執(zhí)行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表達(dá)式

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

2.5 key查找

1. count()判斷key是否存在

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

2. find()判斷key是否存在以及位置

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

3. 下標(biāo)運(yùn)算符[]

m[key];

如果key不存在，默認(rèn)創(chuàng)建。

2.6 區(qū)域查找

2.7 刪除

1. 關(guān)鍵字刪除

m.erase(key);

2. 迭代器刪除

m.erase(m.begin());

3. 區(qū)域刪除

m.erase(it_a,it_b);

2.8 排序

默認(rèn)按照key升序排列。自定義排序是，可以在實(shí)例化加上key的comp仿函數(shù)，重載<運(yùn)算符。

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

3. 實(shí)例

1.兩個(gè)數(shù)組合并成一個(gè)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表達(dá)式，改寫成

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

2.把map的key和value各自分解成一個(gè)vector

#include <iostream>
#include <algorithm>
#include <iterator> // ostream_iterator
#include <vector>
#include <map>
using namespace std;
// 仿函數(shù)
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表達(dá)式，改寫成

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);
}

3. map的key和value互換

4. 練習(xí)

面試題 16.02. 單詞頻率

205. 同構(gòu)字符串

383. 贖金信

49. 字母異位詞分組

容器綜合練習(xí)

1418. 點(diǎn)菜展示表

1. 兩數(shù)之和