Map概述
map本质上是一种映射，其可以将任何基本类型（包括STD容器）映射到任何基本类型（包括STL容器）。本质上数组也是一种映射，只不过是一种局限性更大的映射，只能将int类型映射到其它类型，并且由于数组的连续性，当key的分布过于稀疏的时候，会造成大量的空间浪费。要使用map需要#include <map>并加上 using namespace std;
Map的使用
一、Map的定义、元素添加与访问
#include <iostream>
#include <map>
using namespace std;
int main() {
map<char, int> m; //定义map
m['a'] = 1; // 直接用下标添加元素
m.insert(pair<char, int>('b', 2)); // 用insert函数添加元素
m['c'] = 3;
// 用迭代器访问元素
map<char, int>::iterator it;
for (it = m.begin(); it != m.end(); it++) {
cout << it->first << "," << it->second << endl;
}
cout << "----------------------------" << endl;
// 直接通过下表访问元素
cout << "a," << m['a'] << endl;
cout << "b," << m['b'] << endl;
cout << "c," << m['c'] << endl;
return 0;
}
运行结果如下：
总结：
- map的定义
map<type1, type2> m; - map元素的添加
m[key] = value;m.insert(pair<type1, type2>(key, value));
- map元素的访问
- 定义迭代器(
map<type1, type2>::iterator it;)访问 - 直接用
m[key]访问key对应的value
-
map会以键从小到大的顺序自动排序
将以上程序中元素添加部分改为
m['c'] = 3;
m['a'] = 1; // 直接用下标添加元素
m.insert(pair<char, int>('b', 2)); // 用insert函数添加元素
输出的结果不变。因此，map中元素的插入顺序，与map的遍历顺序/map内部元素的排序没有任何关系。之所以会这样，本质上是因为map是用红黑树实现的，红黑树是一种高效的自平衡的二叉树，其会通过旋转和变色来保证平衡，以此来保证内部元素的有序性，方便查找。
二、Map的常用函数
- find
用find函数来查找key，它返回的一个迭代器，当存在(key, value)时，它返回(key, value)所在位置的迭代器，如果map中没有(key, value)，则返回的迭代器等于end函数返回的迭代器。
#include <iostream>
#include <map>
using namespace std;
void Find(map<char, int> m, char c) {
map<char, int>::iterator it;
it = m.find(c);
if (it != m.end()) { // 找到了
cout << "Find (" << it->first << "," << it->second << ")" << endl;
} else {
cout << "No " << c << endl;
}
}
int main() {
map<char, int> m; //定义map
m['a'] = 1; // 直接用下标添加元素
m.insert(pair<char, int>('b', 2)); // 用insert函数添加元素
m['c'] = 3;
Find(m, 'b');
Find(m, 'd');
return 0;
}
- erase函数
#include <iostream>
#include <map>
using namespace std;
void Find_Erase(map<char, int> &m, char c) {
map<char, int>::iterator it;
it = m.find(c);
if (it != m.end()) { // 找到了
m.erase(it); // earse函数传递的参数是一个迭代器
} else {
cout << "No " << c << endl;
}
}
int main() {
map<char, int> m; //定义map
m['a'] = 1; // 直接用下标添加元素
m.insert(pair<char, int>('b', 2)); // 用insert函数添加元素
m['c'] = 3;
for (map<char, int>::iterator iter = m.begin(); iter != m.end(); iter++ ) {
cout << iter->first << "," << iter->second << endl;
}
Find_Erase(m, 'b');
cout << "--------------------" << endl;
for (map<char, int>::iterator iter = m.begin(); iter != m.end(); iter++ ) {
cout << iter->first << "," << iter->second << endl;
}
return 0;
}
PS: 除了删除单个元素外，erase还可以删除元素区间m.erase(first, last)该区间是一个左闭右开的区间[first, last)
- size函数
m.size()获取map中映射的对数 - clear函数
m.clear()用于清空map中所有的元素
#include <iostream>
#include <map>
using namespace std;
int main() {
map<char, int> m; //定义map
m['a'] = 1; // 直接用下标添加元素
m.insert(pair<char, int>('b', 2)); // 用insert函数添加元素
m['c'] = 3;
cout << m.size() << endl;
for (map<char, int>::iterator iter = m.begin(); iter != m.end(); iter++ ) {
cout << iter->first << "," << iter->second << endl;
}
cout << "--------------------" << endl;
m.clear();
cout << m.size() << endl;
for (map<char, int>::iterator iter = m.begin(); iter != m.end(); iter++ ) {
cout << iter->first << "," << iter->second << endl;
}
return 0;
}
三、Map的使用场景
本质上，用到映射的场景可以考虑使用map，此外map内元素自动有序也是一大优势。
- 字符串到整数的映射
- 大整数或其它数据类型是否存在的问题，可将map当bool数组使用
拓展：
- key对多个value(允许key重复)得使用multimap
- 处理只映射，不需按key排序的问题，使用unordered_map，效率更高。unordered_map是用哈希表实现的，而map是用红黑树实现的。
