在浏览器上搜了一下相关的博文，整理了一部分相对基础的内容，有点难懂的另一部分等以后遇到案例了再重新整理

[TOC]

一、说明

1.名词解释

  • map是STL的一个关联容器，它以<key,value>一对一的形式存储，且map的内部自建一个红黑树，使得其可以自动排序(在map内部一切都是有序的)

  • key可以时任意的数据类型，比如int,char，包括用户自定义数据类型

  • value是该key对应的存储的值

8697326-1c3bfc38aacd4611

2.定义

1
2
3
4
5
6
7
8
map<typename1, typename2> mp;
//例子
map<int string> mis;
map<string, string>mss;
map<float,int> mfi;
map<double,long> mdl;
map<person, int>mpi;//创建一个key为person型、value为int类型的map对象
map<string, int> mp;

注：如果是字符串到整型的映射，必须使用string而不能使用char数组。

3.元素的访问

（1）通过下标访问

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <map>
using namespace std;
map<char, int> mp;
int main()
{
    mp['a']=1;
    mp['c']=2;    
    cout<<mp['c'];
    return 0;
}

返回：2

（2）通过迭代器访问

定义迭代器：

map<typename1, typename2>::iterator it;

map可以使用it->first来访问键，使用it->second来访问值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <map>
using namespace std;
map<char, int> mp;
int main()
{
    mp['a']=1;
    mp['c']=2;    
    mp['b']=3;
    for(map<char, int>::iterator it=mp.begin();it!=mp.end();it++){
        cout<<it->first<<" "<<it->second<<endl;
    }
    return 0;
}
返回：
a 1
b 3
c 2

map会以键从小到大的顺序自动排序，这种方法可以用于遍历

二、常用函数

1.find()

find（key）返回键值为key的映射的迭代器，时间复杂度为O（logN），N为map中映射的个数。

如果find()找不到，将返回NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
 #include <map>
 using namespace std;
 map<char, int> mp;
 int main()
 {
     mp['a']=1;
     mp['c']=2;    
     mp['b']=3;
     map<char, int>::iterator it=mp.find('c');
     cout<<it->first<<" "<<it->second;
     return 0;
 }
输出结果：
c 2
1
2
3
4
5
6
7
8
当map的第一个元素是int类型时候，可以这样操作

map<int, int>mp1;
int sum = 100;
sum += mp1[10];//mp1中不存在关键字10，所以mp1返回的值为0，sum累加后是100

map<int,int> mp2;
mp2[20]++;//因关键字20不存在，增加一个关键字20，其值从0自增到1， 效果相当于mp2增加一个元素<20,1>

2.erase()

erase()可以删除单个元素，也可以删除一个区间的所有元素。

（1）删除单个元素

mp.erase(it)，it为需要删除的元素的迭代器，时间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 #include <iostream>
 #include <map>
 using namespace std;
 map<char, int> mp;
 int main()
 {
     mp['a']=1;
     mp['c']=2;    
     mp['b']=3;
     map<char, int>::iterator it=mp.find('c');
     mp.erase(it);
     for(map<char, int>::iterator it=mp.begin();it!=mp.end();it++){
             cout<<it->first<<" "<<it->second<<endl;
     }
     return 0;
 }

输出结果：
a 1

b 3

mp.erase(key)，key为欲删除的映射的键。时间复杂度为O(logN)，N为map内元素的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 #include <iostream>
 #include <map>
 using namespace std;
 map<char, int> mp;
 int main()
 {
     mp['a']=1;
     mp['c']=2;    
     mp['b']=3;
     mp.erase('c');
     for(map<char, int>::iterator it=mp.begin();it!=mp.end();it++){
             cout<<it->first<<" "<<it->second<<endl;
     }
     return 0;
 }
输出结果：
a 1

b 3

（2）删除一个区间内的所有元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 #include <map>
 using namespace std;
 map<char, int> mp;
 int main()
 {
     mp['a']=1;
     mp['c']=2;    
     mp['b']=3;
     map<char, int>::iterator it=mp.find('c');    //令it指向键为c的值 
     mp.erase(it, mp.end());    //删除it之后的所有映射 
     for(map<char, int>::iterator it=mp.begin();it!=mp.end();it++){
             cout<<it->first<<" "<<it->second<<endl;
     }
     return 0;
 }

输出结果：
a 1

b 3　

3.size()

size()用来获得map中映射的对数，时间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 #include <iostream>
 #include <map>
 using namespace std;
 map<char, int> mp;
 int main()
 {
     mp['a']=1;
     mp['c']=2;    
     mp['b']=3;
     cout<<mp.size();
     return 0;
 }
输出结果：
3

4.clear()

clear()用来清除map中的所有元素，时间复杂度为O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 #include <iostream>
 #include <map>
 using namespace std;
 map<char, int> mp;
 int main()
 {
     mp['a']=1;
     mp['c']=2;    
     mp['b']=3;
     mp.clear();    //清空map 
     cout<<mp.size();
     return 0;
 }
输出结果：
0