转至：https://blog.csdn.net/BillCYJ/article/details/78985895

https://www.cnblogs.com/langyao/p/8823092.html 

需要引入的头文件不同

map: #include < map >
unordered_map: #include < unordered_map >

内部实现机理不同

map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。
 

优缺点以及适用处
map：

优点：

有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高
缺点： 空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map：

优点： 因为内部实现了哈希表，因此其查找速度非常的快
缺点： 哈希表的建立比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

map和unordered_map的使用

unordered_map成员函数：：

---

迭代器
begin 　　返回指向容器起始位置的迭代器（iterator） 
end 　　   返回指向容器末尾位置的迭代器 
cbegin　   返回指向容器起始位置的常迭代器（const_iterator） 
cend 　　 返回指向容器末尾位置的常迭代器 

---

Capacity
size  　　 返回有效元素个数 
max_size  返回 unordered_map 支持的最大元素个数 
empty        判断是否为空 

---

元素访问
operator[]  　　   访问元素 
at  　　 　　　　访问元素 

---

元素修改
insert  　　插入元素 
erase　　 删除元素 
swap 　　 交换内容 
clear　　   清空内容 
emplace 　构造及插入一个元素 
emplace_hint 按提示构造及插入一个元素 

---

操作
find 　　　　　　通过给定主键查找元素,没找到：返回unordered_map::end
count 　　　　　返回匹配给定主键的元素的个数 
equal_range 　　返回值匹配给定搜索值的元素组成的范围 

---

Buckets
bucket_count 　　　返回槽（Bucket）数 
max_bucket_count    返回最大槽数 
bucket_size 　　　   返回槽大小 
bucket 　　　　　　返回元素所在槽的序号 
load_factor　　　　 返回载入因子，即一个元素槽（Bucket）的最大元素数 
max_load_factor 　  返回或设置最大载入因子 
rehash　　　　　　 设置槽数 
reserve 　　　　　  请求改变容器容量

 插入元素实例：

 // unordered_map::insert#include <iostream>#include <string>#include <unordered_map>using namespace std;void display(unordered_map<string,double> myrecipe,string str){cout << str << endl;for (auto& x: myrecipe)cout << x.first << ": " << x.second << endl;cout << endl;}int main (){unordered_map<string,double>myrecipe,mypantry = {{"milk",2.0},{"flour",1.5}};/****************插入*****************/pair<string,double> myshopping ("baking powder",0.3);myrecipe.insert (myshopping);                        // 复制插入myrecipe.insert (make_pair<string,double>("eggs",6.0)); // 移动插入myrecipe.insert (mypantry.begin(), mypantry.end());  // 范围插入myrecipe.insert ({{"sugar",0.8},{"salt",0.1}});    // 初始化数组插入(可以用二维一次插 //入多个元素，也可以用一维插入一个元素)myrecipe["coffee"]// = 10.0;  //数组形式插入display(myrecipe,"myrecipe contains:");/****************查找*****************/unordered_map<string,double>::const_iterator got = myrecipe.find ("coffee");if ( got == myrecipe.end() )cout << "not found";elsecout << "found "<<got->first << " is " << got->second<<"\n\n";/****************修改*****************/myrecipe.at("coffee") = 9.0;myrecipe["milk"] = 3.0;display(myrecipe,"After modify myrecipe contains:");/****************擦除*****************/myrecipe.erase(myrecipe.begin());  //通过位置myrecipe.erase("milk");    //通过keydisplay(myrecipe,"After erase myrecipe contains:");/****************交换*****************/myrecipe.swap(mypantry);display(myrecipe,"After swap with mypantry, myrecipe contains:");/****************清空*****************/myrecipe.clear();display(myrecipe,"After clear, myrecipe contains:");return 0;}/*myrecipe contains:salt: 0.1milk: 2flour: 1.5coffee: 10eggs: 6sugar: 0.8baking powder: 0.3found coffee is 10After modify myrecipe contains:salt: 0.1milk: 3flour: 1.5coffee: 9eggs: 6sugar: 0.8baking powder: 0.3After erase myrecipe contains:flour: 1.5coffee: 9eggs: 6sugar: 0.8baking powder: 0.3After swap with mypantry, myrecipe contains:flour: 1.5milk: 2After clear, myrecipe contains:*/

 

---

 遍历实例

 // unordered_map::bucket_count#include <iostream>#include <string>#include <unordered_map>using namespace std;int main (){unordered_map<string,string> mymap ={{"house","maison"},{"apple","pomme"},{"tree","arbre"},{"book","livre"},{"door","porte"},{"grapefruit","pamplemousse"}};/************begin和end迭代器***************/cout << "mymap contains:";for ( auto it = mymap.begin(); it != mymap.end(); ++it )cout << " " << it->first << ":" << it->second;cout << endl;/************bucket操作***************/unsigned n = mymap.bucket_count();cout << "mymap has " << n << " buckets.\n";for (unsigned i=0; i<n; ++i){cout << "bucket #" << i << "'s size:"<<mymap.bucket_size(i)<<" contains: ";for (auto it = mymap.begin(i); it!=mymap.end(i); ++it)cout << "[" << it->first << ":" << it->second << "] ";cout << "\n";}cout <<"\nkey:'apple' is in bucket #" << mymap.bucket("apple") <<endl;cout <<"\nkey:'computer' is in bucket #" << mymap.bucket("computer") <<endl;return 0;}
/*mymap contains: door:porte grapefruit:pamplemousse tree:arbre apple:pomme book:livre house:maisonmymap has 7 buckets.bucket #0's size:2 contains: [book:livre] [house:maison]bucket #1's size:0 contains:bucket #2's size:0 contains:bucket #3's size:2 contains: [grapefruit:pamplemousse] [tree:arbre]bucket #4's size:0 contains:bucket #5's size:1 contains: [apple:pomme]bucket #6's size:1 contains: [door:porte]key:'apple' is in bucket #5key:'computer' is in bucket #6*/