map和unordered_map区别

map和unordered_map也是常用的两个容器，当然面试的时候也可能会问你内部实现原理。

map、unordered_map 是 C++ STL 中的两个容器

区别

1. 导入的头文件 map：#include <map> unordered_map：#include <unordered_map>
2. 原理：map内部实现了一个红黑树（红黑树是非常严格的平衡二叉搜索树），该结构具有自动排序的功能，因此 map 内部的所有元素都是有序的，红黑树的每一个节点都代表着 map 的一个元素，所以对于 map 进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行这样的操作，故红黑树的效率决定了 map 的效率。
   unordered_map基于哈希表来实现的，因此其元素的排列顺序是杂乱的，无序的。查找的时间复杂度是O(1),在海量数据处理中有着广泛的应用。

map和unordered_map的优缺点

map优点：map是有序的、基于红黑树实现，查找的时间复杂度是O(n)
map缺点：空间占用率比较高，因为内部实现了红黑树，虽然提高了运行效率，但是每个节点都要保存父亲节点和孩子节点和红黑树的性质，使得每一个节点都占用大量的空间。
适用的情况：对于要有序的结构，使用map。
unordered_map优点：因为内部是哈希表来实现的，所以查找效率会非常高。
unordered_map缺点：哈希表的建立比较费时
适用的情况：对于查找问题，使用unordered_map会更好一点。

实例

map是STL的一个关联容器，它提供一对一的hash。也就是所说的键值对。
第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
第二个可能称为该关键字的值(value)；
可以存储任意类型的数据，包括使用者自定义的数据类型。map主要用于资料一对一映射(one-to-one)的情況

map中常用的操作
begin()	返回指向map头部的迭代器
clear()	删除所有元素，注意是所有元素
count()	还回指定元素出现的次序
empty()	如果map为空则还回true
end()	返回指向map末尾的迭代器
erase()	删除一个元素
find()		查找一个元素
insert()	插入一个元素
max_size()	还回可以容纳的最大元素个数
size()		还回map中元素的个数
swap()		交换两个map
rbegin()        返回一个指向map尾部的逆向迭代器
rend()          返回一个指向map头部的逆向迭代器
get_allocator() 返回map的配置器
key_comp()      返回比较元素key的函数
lower_bound()   返回键值>=给定元素的第一个位置
upper_bound()    返回键值>给定元素的第一个位置
value_comp()     返回比较元素value的函数

map<int, char> m;
//数据的插入
m.insert(pair<int, char>(1, 'a'));
m.insert(map<int, char>::value_type(2, 'b'));
m[3] = 'c';
m[4] = 'd';
map<int, char>::iterator it = m.begin();
for (; it != m.end(); it++) 
{
	cout << it->first << ":" << it->second << endl;
}

//数据的查找
//使用find()函数，该函数可以找到key对应的value
//使用count()函数,该函数的还回值只有0和1，1为找到，但是还回要查找的值
it = m.find(1);
if (it != m.end()) 
	cout << "find" << it->second << endl; 
else 
	cout << "not find" << endl; 

//map的清空
m.clear(m.begin(), m.end());
m.erase(m.begin(), m.end());

//数据的删除
it = m.find('1');
m.erase(it);
//用关键字刪除
int n = m.erase('2'); //如果刪除了會返回1，否則返回0
 

//map的反向遍历，使用反向迭代容器
for (map<int, char>::reverse_iterator Rit = m.rbegin(); Rit!=m.rend(); Rit++) 
{
	cout << Rit->first << ":" << Rit->second;
}

//map的大小
int nSize = m.size();

unordered_map是一个将key和value关联起来的容器，它可以高效的根据单个key值查找对应的value。

:unordered_map<string, int> umap; //定义
umap.insert(Map::value_type("test", 1));//增加
//根据key删除,如果没找到n=0
auto n = umap.erase("test")   //删除
auto it = umap.find(key) //改
if(it != umap.end()) 
    it->second = new_value; 
//map中查找x是否存在
umap.find(x) != map.end()//查
//或者
umap.count(x) != 0