C++map字典

C++ 中，map 是关联容器的一种，关联容器将值与键关联到一起，并使用键来查找值。这与 python 中的字典类型类似，也是用来存储键值对（key-value） 形式的数据，正如vector可以简单对应到列表。键不能有重复的，值可以重复，map的内部自建一个红黑树，系统会根据键来自动将数据排序。

map的value_type是pair<const key_type, mapped_type>，所以map迭代器只能改变关键字映射的值(mapped_type)，不能修改关键字；set的value_type等于key_type，都是const关键字，不能修改。

声明

头文件：

#include <map>

类型的定义：

map<KeyType, ValueType> dict; 数据遍历

直接遍历：

map<char,char> mp={ {'(',')'}, {'[',']'}, {'{','}'}, {'y','x'} }; for(auto c : mp) { cout << c.first << ": " << c.second << endl; }

使用迭代器遍历：

auto map_it = mp.begin(); // 获取指向首元素的迭代器 // 判断范围，比较当前迭代器和尾后元素迭代器 while (map_it != mp.end()) { cout << map_it->first << ": " << map_it->second << endl; map_it++; // 迭代器递增，移动到下一个元素 }

查找元素：

if (mp.find('y') != mp.end()){ cout << mp.find('y')->second << endl; }else{ cout << "NOT FONUND" << endl; } 添加元素 map<int,string> student; stu.insert(map<int,string>::value_type(1,"Jerry"));//第一种 stu.insert(pair<int,string>(2,"Tom"));//第二种 stu[3] = "Meg";//第三种

前两种方法当map中已经存在这个关键字时，insert 操作是无法插入的。但是第三种方法用数组的方式可以，但会直接覆盖掉原先的数据。

删除元素 dict.erase(key)//删除键为 key 的元素 dict.erase(p)//删除迭代器p指定的元素，p不能为mp.end() dict.erase(a, b)//删除迭代器a和b之间的元素，返回e 与unordered_map的区别

头文件不同：

#include < unordered_map >

内部实现机理不同: map内部实现了一个红黑树，红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作，map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map内部实现了一个哈希表，其元素的排列顺序是无序的，对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map。

使用： unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现完全不同，但是就外部使用来说却是一致的。