C++中map和unordered_map的用法

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;
}