C++ STL-map

map内部数据组织：自建一颗红黑树（一种非严格意义上的平衡二叉树）

头文件：#include <map>

Operation：

1. 自动建立Key-Value的键值对；
2. 根据Key值快速查找记录，复杂度 \(O(log(N))\) ；
3. 快速插入Key-Value记录；
4. 快速删除Key-Value记录；
5. 遍历所有记录。

1. 数据插入

Way1：用insert函数插入pair数据:

map
    
      mInt;mInt.insert(pair
     
      (1, "One"));mInt.insert(pair
      
       (2, "Two"));mInt.insert(pair
       
        (3, "Three"));
       
      
     
    

Way2：用数组方式插入数据：

map
    
      mInt;mInt[1] = "One";mInt[2] = "Two";mInt[3] = "Three";
    

2. map的大小

int size = mInt.size()

3. 数据遍历

Way1：前向迭代器

map
    
     ::iterator iter;for(iter=mInt.begin(); iter!=mInt.end(); iter++){    cout<
     
      first<<" "<
      
       second<
      
     
    

Way2：反向迭代器

map
    
     ::iterator iter;for(iter=mInt.rbegin(); iter!=mInt.rend(); iter++){    cout<
     
      first<<" "<
      
       second<
      
     
    

Way3：数组形式

int size = mInt.size();for(int i=1; i<=size; i++){    cout<
    
     <
    

4. 查找并获取map中的元素（包括判断这个关键字是否在map中出现）

Way1：count函数：判断关键字是否出现，但无法定位数据出现位置。若存在，返回1；否则返回0；

if(mInt.count(1) > 0){    cout<<"Yes"<

Way2：find函数：返回一个迭代器。数据出现时，返回数据所在位置的迭代器；否则返回的迭代器等于end函数返回的迭代器；

iter = mInt.find(1);if(iter != mInt.end())    cout<<"Find"<
    
     second<
    

5. 删除键值对

移除map中某个条目用erase函数，其有三个重载函数

F1：iterator erase(iterator it) 删除一个条目对象

iter = mInt.find(1);mInt.erase(iter);

F2：通过关键字删除

int n = mInt.erase(1);  //如果删除则返回1，否则返回0

F3：iterator erase(iterator first, iterator last)删除一个范围

mInt.erase(mInt.begin(), mInt.end()) //相当于mInt.clear()

6. Swap

待补充

7. 排序

map中的元素自动按Key升序排序，所以不能对map用sort函数。STL默认采用小于号排序，比如上例关键字是int型，所以排序没有问题；如果关键字是结构体，就会使得排序出现问题。有两种解决办法。

Way1：小于号重载

typedef struct tagInfo{    int id;    string strName;    bool operator <(tagInfo const& _A) const{        if(id < _A.id) return true;        if(id == _A.id)            return strName.compare(_A.strName) < 0;        return false;    }}Info, *PInfo;int main(){    map
    
      mapInfo;}
    

Way2：应用仿函数，这时结构体中没有直接的小于号重载

typedef struct tagInfo{    int id;    string strName;}Info, *PInfo;class sort{    public:    bool operator()(Info const &_A, Info const &_B) const{        if(_A.id < _B.id)            return true;        if(_A.id == _B.id)            return _A.strName.compare(_B.strName) < 0;        return false;    }   };int main(){    map
    
      mapInfo;}