Cpp

map

scorlw 发布于

map

c++

map是STL的一个关联容器，它提供一对一的hash。

  • 第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
  • 第二个可能称为该关键字的值(value)；

map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的。

pair类型

pair类型是在有文件utility中定义的，pair类型包含了两个数据值，通常有以下的一些定义和初始化的一些方法：

1
2
3
pair<T1, T2> p;//定义了一个空的pair对象p
pair<T1, T2> p(v1, v2);//定义了包含初始值为v1和v2的pair对象p
make_pair(v1, v2)//以v1和v2值创建的一个新的pair对象

除此之外，pair对象还有一些方法，如取出pair对象中的每一个成员的值：

  • p.first
  • p.second

实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <string.h>
#include <string>
#include <utility>
#include <iostream>
using namespace std;

int main(){
        pair<int, string> p1(0, "Hello");
        printf("%d, %s\n", p1.first, p1.second.c_str());
    	//cout << p1.first << p1.second << endl;//与上一句结果一致
        pair<int, string> p2 = make_pair(1, "World");
        printf("%d, %s\n", p2.first, p2.second.c_str());
        return 0;
}

注：c_str函数

IO:

1
2
3
输出：
0, Hello
1, World

map对象的定义和初始化

map是键-值对的组合，有以下的一些定义的方法：

1
2
3
map<k, v> m;//定义了一个名为m的空的map对象
map<k, v> m(m2);//创建了m2的副本m
map<k, v> m(b, e);//创建了map对象m，并且存储迭代器b和e范围内的所有元素的副本

map的value_type是存储元素的键以及值的pair类型，键为const。

map对象的一些基本操作

1.map中元素的插入

在map中元素有两种插入方法：

  1. 使用下标
  2. 使用insert函数

在map中使用下标访问不存在的元素将导致在map容器中添加一个新的元素。

insert函数的插入方法主要有如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 定义一个map对象
map<int, string> mapStudent;
 
// 第一种 用insert函數插入pair
mapStudent.insert(pair<int, string>(000, "student_zero"));
 
// 第二种 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(001, "student_one"));

//第三种 insert(m.beg, m.end)
for (int i = 0; i < 10; i ++) mp[i] = i;
mp1.insert(mp.begin(), mp.end());

// 第四种 用"array"方式插入
mapStudent[123] = "student_first";
mapStudent[456] = "student_second";

以上四种用法，虽然都可以实现数据的插入，但是它们是有区别的，当然了第一种和第二种在效果上是完成一样的，用insert函数插入数据，在数据的插入上涉及到集合的唯一性这个概念，即当map中有这个关键字时，insert操作是不能在插入数据的，但是用数组方式就不同了，它可以覆盖以前该关键字对 应的值，用程序说明如下：

1
2
3
mapStudent.insert(map<int, string>::value_type (001, "student_one"));
 
mapStudent.insert(map<int, string>::value_type (001, "student_two"));

上面这两条语句执行后，map中001这个关键字对应的值是“student_one”，第二条语句并没有生效，那么这就涉及到我们怎么知道insert语句是否插入成功的问题了，可以用pair来获得是否插入成功，程序如下:

1
2
3
4
5
6
7
8
9
// 构造定义，返回一个pair对象
pair<iterator,bool> insert (const value_type& val);
 
pair<map<int, string>::iterator, bool> Insert_Pair;
 
Insert_Pair = mapStudent.insert(map<int, string>::value_type (001, "student_one"));
 
if(!Insert_Pair.second)
    cout << "Error insert new element" << endl;

我们通过pair的第二个变量来知道是否插入成功，它的第一个变量返回的是一个map的迭代器，如果插入成功的话Insert_Pair.second应该是true的，否则为false。

三种插入方法如下面的例子所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
#include <map>
using namespace std;

int main(){
        map<int, int> mp;
    	map<int, int> mp1;
        for (int i = 0; i < 10; i ++){
                mp[i] = i;
        }
        for (int i = 10; i < 20; i++){
                mp.insert(make_pair(i, i));
        }
        map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d-->%d\n", it->first, it->second);
        }
    	mp1.insert(mp.begin(), mp.end());
        map<int, int>::iterator it;
        for (it = mp1.begin(); it != mp1.end(); it++){
                printf("%d-->%d\n", it->first, it->second);
        }
        return 0;
}

2.map中元素的查找与读取

注意：上述采用下标的方法读取map中元素时，若map中不存在该元素，则会在map中插入。

因此，若只是查找该元素是否存在，可以使用函数count(k)，该函数返回的是k出现的次数；若是想取得key对应的值，可以使用函数find(k)，该函数返回的是指向该元素的迭代器。

上述的两个函数的使用如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <map>
#include <iostream>
using namespace std;

int main(){
        map<int, int> mp;
        for (int i = 0; i < 20; i++){
                mp.insert(make_pair(i, i));
        }
    	cout << mp.count(0) << endl;
    
        if (mp.count(0)){
                printf("yes!\n");
        }else{
                printf("no!\n");
        }
        

        map<int, int>::iterator it_find;
        it_find = mp.find(0);
        if (it_find != mp.end()){
                it_find->second = 20;
        }else{
                printf("no!\n");
        }

        map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d->%d\n", it->first, it->second);
        }
        return 0;
}

IO:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
输出：
1
yes!
0->20
1->1
2->2
3->3
4->4
5->5
6->6
7->7
8->8
9->9
10->10
11->11
12->12
13->13
14->14
15->15
16->16
17->17
18->18
19->19

3.从map中删除元素

从map中删除元素的函数是erase()，该函数有如下的三种形式：

m.erase(k)//k为key
m.erase(p)//p为迭代器
m.erase(b, e)//b，e均为迭代器

第一种方法删除的是m中键为k的元素，返回的是删除的元素的个数；第二种方法删除的是迭代器p指向的元素，返回的是void；第三种方法删除的是迭代器b和迭代器e范围内的元素，返回void。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <map>
#include <iostream>
using namespace std;

int main(){
        map<int, int> mp;
        for (int i = 0; i < 10; i++){
                mp.insert(make_pair(i, i));
        }

        cout << mp.erase(0) << endl;
        map<int, int>::iterator it;
        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d->%d\n", it->first, it->second);
        }
        cout << endl;
        mp.erase(mp.begin());
        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d->%d\n", it->first, it->second);
        }
        cout << endl;
        mp.erase(++mp.begin(), --mp.end());

        for (it = mp.begin(); it != mp.end(); it++){
                printf("%d->%d\n", it->first, it->second);
        }
        system("pause");
        return 0;
}

IO：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1
1->1
2->2
3->3
4->4
5->5
6->6
7->7
8->8
9->9

2->2
3->3
4->4
5->5
6->6
7->7
8->8
9->9

2->2
9->9

4.map的基本操作函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
begin()         返回指向map头部的迭代器

clear(）        删除所有元素

count()         返回指定元素出现的次数

empty()         如果map为空则返回true

end()           返回指向map末尾的迭代器

equal_range()   返回特殊条目的迭代器对

erase()         删除一个元素

find()          查找一个元素

get_allocator() 返回map的配置器

insert()        插入元素

key_comp()      返回比较元素key的函数

lower_bound()   返回键值>=给定元素的第一个位置

max_size()      返回可以容纳的最大元素个数

rbegin()        返回一个指向map尾部的逆向迭代器

rend()          返回一个指向map头部的逆向迭代器

size()          返回map中元素的个数

swap()           交换两个map

upper_bound()    返回键值>给定元素的第一个位置

value_comp()     返回比较元素value的函数

附：迭代器的加减法

原文地址：https://blog.csdn.net/sevenjoin/article/details/81943864

https://blog.csdn.net/google19890102/article/details/51720305