《算法笔记》学习笔记

map 常见用法详解

**map翻译为映射，也是常用的STL容器 **

map可以将任何基本类型（包括STL容器）映射到任何基本类型（包括STL容器）

1. map 的定义

//单独定义一个map

map<typename1, typename2> mp;

//map和其他的STL容器在定义上有点不同

//因为 map 需要确定映射前类型（键key）和映射后类型（值value）

//其中第一个是键的类型，第二个是值的类型

//字符串到整型的映射

//必须使用string而不能用char数组

map<string, int> mp;

//map的键和值也可以是STL容器

//将一个 set 容器映射到一个字符串

map<set<int>, string> mp;

2. map 容器内元素访问

//map 一般有两种访问方式：通过下标或迭代器访问

(1) 通过下标访问

//和访问普通的数组是一样的

//注意：map中的键是唯一的

#include <stdio.h>

#include <map>

using namespace std;

int main() {

    map<char, int> mp;

    mp['c'] = 20;

    mp['c'] = 30;   //20被覆盖

    printf("%d\n", mp['c']);

    return 0;

}

(2) 通过迭代器访问

//map 迭代器的定义和其他STL容器迭代器定义的方式相同

map<typename1, typename2>::iterator it;

//typename1和typename2就是定义map填写时的类型

//map的每一对映射都有两个typename,这决定了必须能通过一个 it 来同时访问键和值。

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

#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;

}

3. map常用函数实例解析

**(1) find() **

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

#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;

}

(2) erase()

//erase()有两种用法：删除单个元素，删除一个区间内的所有元素

//<1> 删除单个元素

//删除单个元素有两种方法：

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

#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;

}

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

#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的映射，即 b 2

    for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {

        printf("%c %d\n", it -> first, it -> second);

    }

    return 0;

}

//<2> 删除一个区间内的所有元素

//mp.erase(first, last), 其中first为需要删除的区间的起始迭代器，

//而last则为需要删除的区间的末尾迭代器的下一个地址，也即为删除左闭右开

//的区间[first, last)。时间复杂度为O(last - first)

#include <stdio.h>

#include <map>

using namespace std;

int main() {

    map<char, int> mp;

    mp['a'] = 1;

    mp['b'] = 2;

    mp['c'] = 3;

    mp<char, int>::iterator it = mp.find('b');  //令it指向键为b的映射

    mp.erase(it. mp.end()); //删除it之后的所有映射，即b 2和c 3

    for(map<char, int>::iterator it = mp.begin(); it != mp.end(); it++) {

        printf("%c %d\n", it -> first, it -> second);

    }

    return 0;

}

(3) size()

//size()用来获取map中映射的对数，时间复杂度位O(1)

#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) clear()

//clear()用来清空map中的所有元素，复杂度为O(N),其中N为map中元素的个数。

#include <stdio.h>

#include <map>

using namespace std;

int main() {

    map<char, int> mp;

    mp['a'] = 1;

    mp['b'] = 2;

    mp['c'] = 3;

    mp.clear();     //清空map

    printf("%d\n", mp.size());

    return 0;

}

4.map的常见用途

• 需要建立字符（或字符串）与整数之间映射的题目，使用map可以减少代码量。
• 判断大整数或者其他类型数据是否存在的题目，可以把map当作bool数组用。
• 字符串和字符串的映射也有可能会遇到。