C++ unordered_map

简介

map 和 unordered_map 都是 c++ 中可以充当字典 (key-value) 来用的数据类型, 但是其基本实现是不一样的.

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;

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

unordered_map 用到自定义的类型, 需要对 key 定义 hash_value 函数并且重载 operator ==, 具体用法请参考文献 3(有空再来补个示例).