c++ 数据结构map的使用详解

时间:2022-11-21 14:17:50

map的常用用法

map 表示映射,可以将任何基本类型(包括 STL 容器)映射到任何基本类型(包括 STL 容器),例如可以建立如 int 到 double,string 到 int 的映射等。

map 提供一对一的 hash,该功能类似 Python 的字典:

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

1. 头文件

<bits/stdc++.h> 头文件已经包括了该头文件。

2. 定义

定义 map 如下,参数的第一个为 key 的类型,第二个为 value 的类型。

?
1
map<typename1, typename2> mp;

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

map 的键和值也可以是 STL 容器,例如可以将一个 set 容器映射到一个字符串:

?
1
map<set<int>, string> mp;

3. map 容器内元素的访问

(1)通过下标访问

注意:map 的键是唯一的。

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

30

(2)通过迭代器访问

定义迭代器:

?
1
map<typename1, typename2>::iterator it;

这样可以得到迭代器 it,map 可以使用 it->first来访问键,使用 it->second 来访问值。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char, int>::iterator it = mp.begin(); it!=mp.end();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

输出:

a 40
m 20
r 30

【注意】map 会以键从小到大的顺序自动排序。迭代器的比较不能用 < 或者 >,而只能使用 == 或者 !=

(3)通过逆向迭代器访问

?
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char, int>::reverse_iterator it = mp.rbegin(); it!=mp.rend();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

输出:

r 30
m 20
a 40

rbegin()指向 map 的最后一个元素,rend()指向 map 第一个元素之前。

4. map 元素的插入

(1)通过insert + <key, value> 插入

?
1
2
map<int, string> mapStudent; 
mapStudent.insert(pair<int, string>(1, "student_one")); 

(2)通过insert + 迭代器 插入

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

(3)通过数组方式插入

?
1
2
map<int, string> mapStudent; 
mapStudent[1] = "student_one";

【注意】第一、二种方法完全等价,但是第三种和前两种有所区别。当映射中包含了键,则第一、二中方法插入失败,而第三种方法会覆盖之前的键值对。所以先后插入相同 key 的元素,第一、二种方法会保留第一次的数据,第三种会保留最后一次的。

5. map 常用函数实例解析

(1)find()

find(key) 返回键为 key 的映射的迭代器,时间复杂度为 O(logN),N为 map 中映射的个数。

?
1
2
3
4
5
6
7
8
9
10
11
12
#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char, int>::iterator it = mp.find('b');
    printf("%c %d\n", it->first, it->second);
    return 0;
}

b 2

(2)erase()

① 删除单个元素

mp.erase(it) :it 是要删除的元素的迭代器,时间复杂度为 O(1)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    map<char, int>::iterator it = mp.find('b');
    mp.erase(it);  // 删除 b 2
    for(map<char, int>::iterator it = mp.begin(); it!=mp.end();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

a 1
c 3

mp.erase(key):key是要删除的映射的键,时间复杂度为 O(logN)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 1;
    mp['b'] = 2;
    mp['c'] = 3;
    mp.erase('b');  // 删除 b 2
    for(map<char, int>::iterator it = mp.begin(); it!=mp.end();it++){
        printf("%c %d\n", it->first, it->second);
    }
    return 0;
}

a 1
c 3

② 删除一个区间内所有元素

mp.erase(first, last):first 为需要删除区间的起始迭代器,last 为需要删除的区间的末尾迭代器的下一个地址,即删除左闭右开区间 [first, last) 内所有元素。

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

a 1

(3)size()

size() :获取 map 中映射的对数,时间复杂度为 O(1)。

?
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
#include <map>
using namespace std;
int main(){
    map<char, int> mp;
    mp['a'] = 10;
    mp['b'] = 20;
    mp['c'] = 30;
    printf("%d\n", mp.size());  // 3对映射
    return 0;
}

(4)count()

count(): 返回 map 中对应键的个数,由于 map 中相同键只能最多有一个,所以 count() 的结果只能是 0 或者 1。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <map>
 
int main (){
    std::map<char,int> mymap;
    char c;
    
    mymap ['a']=101;
    mymap ['c']=202;
    mymap ['d']=303;
    
    for (c='a'; c<'e'; c++){
      std::cout << c;
      if (mymap.count(c)>0)
        std::cout << " is an element of mymap.\n";
      else
        std::cout << " is not an element of mymap.\n";
    }
    return 0;
}

结果:

a is an element of mymap.
b is not an element of mymap.
c is an element of mymap.
d is an element of mymap.

(5)clear()

clear(): 用于清空 map,map变为初始的空状态。

(6)empty()

empty():判断 map 是否为空,如果 map 为空,返回 true,否则返回 false.

(7)lower_bound() 、upper_bound()

lower_bound() : 返回键值 >= 给定元素的第一个位置。即如果键的类型可以比较,可以使用二分查找的方法,返回的类型是一个迭代器。 upper_bound(): 返回键值>给定元素的第一个位置。即如果键的类型可以比较,可以使用二分查找的方法,返回的类型是一个迭代器。

?
1
2
3
4
5
6
7
map<int, string> mapStudent; 
mapStudent[1] = "student_one"
mapStudent[3] = "student_three"
mapStudent[5] = "student_five";
map<int, string>::iterator iter;
iter = mapStudent.lower_bound(2); // 返回键值为3的迭代器;
iter = mapStudent.upper_bound(2); // 返回键值为3的迭代器

以上就是c++ 数据结构map的使用详解的详细内容,更多关于c++ 数据结构map的使用的资料请关注服务器之家其它相关文章!

原文链接:https://juejin.cn/post/6954185004939214855