std:map使用笔记

本人是多年的C码农，最近才开始玩C++，所以难免会遇到C++里很平常普通的东西，在C程序员眼里已经灰常神奇了。
举个例子，最普通的链表，在C里面要构建一个链表，要解决的几个问题：

1. 每个节点的数据结构
2. 节点的插入、删除问题，以及由此产生的内存问题
3. 链表的表头，表尾问题
4. 特定节点的查找，匹配
5. 链表的遍历，排序问题
6. 等等

上面列举的是链表操作的几个基本问题，但是在C里面要自己构建一个好用且不出错的链表，并且把以上基本操作都实现，估计也得花一番好功夫。
C++就不一样了，C++提供一个STL（标准模板类）库，这个里面有个std::map模板类，是一个关联式容易，简单理解为，链表里的每个节点都是一个<key, value>对。
现在就来看下它是如何减轻码农痛苦的。

---

一.建一张表

看到这个问题，C码农是不是马上就要想，哎呀，那我要：

1. 先设计一个数据节点，并设计成链表节点；
2. 然后再不断的malloc新节点；
3. 再依次把这些节点串接起来，形成一张表。

把上面这几点用code实现并调通，那就是个合格的C程序员。
但是我们来看看用STL提供的模板类有多么方便。
直接上代码：

sample 1

#include<map>
#include<string>
#include<iostream>
using namespace std;

int main()
{
    // 声明一张表
    map<string,int>  myMap;     
    
    // 依次给这张表添加元素
    myMap["a"]=1;                       
    myMap["b"]=2;
    myMap["c"]=3;
    
    // 遍历刚刚建的表
    map<string,int>::iterator it;
    for(it=myMap.begin(); it!=myMap.end(); ++it)
        cout<<"key: "<<it->first <<" value: "<<it->second<<endl;
    
    return   0;
}

这段code输出为：

key: a value: 1
key: b value: 2
key: c value: 3

哇，是不是有点神奇了，建一张表，以及遍历这张表，这么简单！
怎么看起来像C的数组？
其实不是，其实是这个模板类重载了操作符[ ]， 让你看起来觉得像数组而已；
这个有点点误导，我觉得比较纯正的还是insert方法，再看下一段code：

sample 2

#include<map>
#include<string>
#include<iostream>
using namespace std;

int main()
{
    map<string,int>  myMap;             // 声明一张表

    // 依次给这张表添加元素
    myMap.insert(pair<string, int>("a", 1));    
    myMap.insert(pair<string, int>("b", 2));
    myMap.insert(pair<string, int>("c", 3));

    // 遍历刚刚建的表
    map<string,int>::iterator it;
    for(it=myMap.begin(); it!=myMap.end(); ++it)
        cout<<"key: "<<it->first <<" value: "<<it->second<<endl;
    return   0;
}

这次看起来有点正儿八经的链表插入的感觉了吧:)
用上C++提供的标准模板库，有不有点从石器时代跨入青铜时代的感觉~~~

---

二. 删除节点

既然有增加节点，那么对应地，就有删除节点。
我们先回顾一下C怎么考虑这个问题的：

1. 在链表中找到特定的节点。
2. 把这个节点从链表中断开，把这个节点的相邻节点链上。
3. free掉这个节点。

裹筋吧，我们看看std:map是怎么让人happy的。
看代码：

sample 3

#include<map>
#include<string>
#include<iostream>
using namespace std;

int main()
{
    map<string,int>  myMap;             // 声明一张表

    // 依次给这张表添加元素
    myMap.insert(pair<string, int>("a", 1));    
    myMap.insert(pair<string, int>("b", 2));
    myMap.insert(pair<string, int>("c", 3));

    // 遍历刚刚建的表
    map<string,int>::iterator it;
    for(it=myMap.begin(); it!=myMap.end(); ++it)
        cout<<"key: "<<it->first <<" value: "<<it->second<<endl;

    cout << endl;

    // 删掉一个节点
    myMap.erase("b");
    map<string,int>::iterator iter;
    for(iter=myMap.begin(); iter!=myMap.end(); ++iter)
        cout<<"key: "<<iter->first <<" value: "<<iter->second<<endl;
    return   0;
}

删除特定节点？free废节点？自动就帮你做了！

---

三. 清空map

清空操作为什么单独拿出来说一下，是因为我第一次使用也犯了错误，因为最容易想到的方法就是：遍历这个表，one by one地删除每一个节点。
请看错误代码：

map<string,int>::iterator iter;
for(iter=myMap.begin(); iter!=myMap.end(); ++iter) {
    myMap.erase(iter);
}

这其实是错误的写法，因为erase会释放掉iter，然后执行++iter，程序就回跑飞。
所以这里附上一个推荐的写法：

map<string,int>::iterator iter;
for(iter=myMap.begin(); iter!=myMap.end(); ) {
    // erase() 返回的是下一个元素的迭代器 
    iter = myMap.erase(iter);
}

或者再简单一点：

myMap.clear();

世界清净了~ 让我歇会儿，喝口茶。

---

四. 几个经常用的方法

Item	Description
begin()	返回指向map头部的迭代器
clear()	删除所有元素
empty()	判断map是否为空
end()	返回指向map末尾的迭代器
erase()	删除一个元素
find()	查找一个元素
insert()	插入元素
size()	返回map中元素的个数

还有其他的就不一一列举了，还有就是要注意这些方法的重载版本，用的时候可以特别研究一下。