1. 简介
map和unordered_map都是c++中可以充当字典（key-value）来用的数据类型，但是其基本实现是不一样的。
2. map
对于map的底层原理，是通过红黑树（一种非严格意义上的平衡二叉树）来实现的，因此map内部所有的数据都是有序的，map的查询、插入、删除操作的时间复杂度都是O(logn)。此外，map的key需要定义operator <，对于一般的数据类型已被系统实现，若是用户自定义的数据类型，则要重新定义该操作符。
map的基本操作如下
#include<iostream>
#include<map>
#include<string> using namespace std; int main()
{
// 构造函数
map<string, int> dict; // 插入数据的三种方式
dict.insert(pair<string,int>("apple",2));
dict.insert(map<string, int>::value_type("orange",3));
dict["banana"] = 6; // 判断是否有元素
if(dict.empty())
cout<<"该字典无元素"<<endl;
else
cout<<"该字典共有"<<dict.size()<<"个元素"<<endl; // 遍历
map<string, int>::iterator iter;
for(iter=dict.begin();iter!=dict.end();iter++)
cout<<iter->first<<ends<<iter->second<<endl; // 查找
if((iter=dict.find("banana"))!=dict.end()) // 返回一个迭代器指向键值为key的元素，如果没找到就返回end()
cout<<"已找到banana,其value为"<<iter->second<<"."<<endl;
else
cout<<"未找到banana."<<endl; if(dict.count("watermelon")==0) // 返回键值等于key的元素的个数
cout<<"watermelon不存在"<<endl;
else
cout<<"watermelon存在"<<endl; pair<map<string, int>::iterator, map<string, int>::iterator> ret;
ret = dict.equal_range("banana"); // 查找键值等于 key 的元素区间为[start,end)，指示范围的两个迭代器以 pair 返回
cout<<ret.first->first<<ends<<ret.first->second<<endl;
cout<<ret.second->first<<ends<<ret.second->second<<endl; iter = dict.lower_bound("boluo"); // 返回一个迭代器，指向键值>=key的第一个元素。
cout<<iter->first<<endl;
iter = dict.upper_bound("boluo"); // 返回一个迭代器，指向值键值>key的第一个元素。
cout<<iter->first<<endl;
return 0;
}
注意如果定义了map<string,int>这个类型，需要在头文件中包含“#include<string>”，这是因为默认的string是系统的xstring对象，但是没有定义operator<，从而报错。map用到自定义的类型，一定要定义operator<，具体用法如下。
struct person
{
string name;
int age; person(string name, int age)
{
this->name = name;
this->age = age;
} bool operator < (const person& p) const
{
return this->age < p.age;
}
}; map<person,int> m;
3. unordered_map
unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的。unordered_map的底层是一个防冗余的哈希表（开链法避免地址冲突）。unordered_map的key需要定义hash_value函数并且重载operator ==。
哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，时间复杂度为O(1)；而代价仅仅是消耗比较多的内存。哈希表的查询时间虽然是O(1)，但是并不是unordered_map查询时间一定比map短，因为实际情况中还要考虑到数据量，而且unordered_map的hash函数的构造速度也没那么快，所以不能一概而论，应该具体情况具体分析。
unordered_map的基本操作
#include<string>
#include<iostream>
#include<unordered_map>
using namespace std; int main()
{
unordered_map<string, int> dict; // 声明unordered_map对象 // 插入数据的三种方式
dict.insert(pair<string,int>("apple",2));
dict.insert(unordered_map<string, int>::value_type("orange",3));
dict["banana"] = 6; // 判断是否有元素
if(dict.empty())
cout<<"该字典无元素"<<endl;
else
cout<<"该字典共有"<<dict.size()<<"个元素"<<endl; // 遍历
unordered_map<string, int>::iterator iter;
for(iter=dict.begin();iter!=dict.end();iter++)
cout<<iter->first<<ends<<iter->second<<endl; // 查找
if(dict.count("boluo")==0)
cout<<"can't find boluo!"<<endl;
else
cout<<"find boluo!"<<endl; if((iter=dict.find("banana"))!=dict.end())
cout<<"banana="<<iter->second<<endl;
else
cout<<"can't find boluo!"<<endl; return 0;
}
nordered_map用到自定义的类型，需要对key定义hash_value函数并且重载operator ==，具体用法请参考文献。