C++11

// <unordered_map>
template < class Key,
    class T,
    class Hash = hash<Key>,
    class Pred = equal_to<Key>,
    class Alloc = allocator< pair<const Key,T> >
> class unordered_map;

无序映射表(Unordered Map)容器是一个存储以键值对组合而成的元素的关联容器(Associative container),容器中的元素无特别的次序关系。该容器允许基于主键地快速检索各个元素。

An unordered_map is an unordered associative container that supports unique keys (an unordered_map contains at most one of each key value) and that associates values of another type mapped_type with the keys.

C++编程语言国际标准:ISO/IEC 14882:2011

容器特性

关联(Associative)

关联容器中的元素是通过主键(Key)而不是它们在容器中的绝对位置来引用的。

无序(Unordered)

无序容器通过 hash 表来组织它们的元素,允许通过主键快速地访问元素。

映射(Map)

每个元素为一个值(Mapped value)绑定一个键(Key):以主键来标志主要内容等于被映射值的元素。

键唯一(Unique keys)

容器中不存在两个元素有相同的主键。

能够感知内存分配器的(Allocator-aware)

容器使用一个内存分配器对象来动态地处理它的存储需求。

  • Key

    主键的类型。

    在类模板内部,使用其别名为 key_type 的成员类型。

    T

    被映射的值的类型。

    在类模板内部,使用其别名为 mapped_type 的成员类型。

    Hash

    一元谓词,以一个 Key 类型的对象为参数,返回一个基于该对象的 size_t 类型的唯一值。

    可以是函数指针(Function pointer)类型或函数对象(Function object)类型。

    在类模板内部,使用其别名为 hasher 的成员类型。

    Pred

    二元谓词,以两个 Key 类型的对象为参数,返回一个 bool 值,如果第一个参数等价于第二个参数,该 bool 值为 true,否则为 false。默认为 std::equal_to

    可以是函数指针类型(Function pointer)类型或函数对象(Function object)类型。

    在类模板内部,使用其别名为 key_equal 的成员类型。

    Alloc

    容器内部用来管理内存分配及释放的内存分配器的类型。

    这个参数是可选的,它的默认值是 std::allocator<T>,这个是一个最简单的非值依赖的(Value-independent)内存分配器。在类模板内部,使用其别名为 allocator_type 的成员类型。

  • 在一个 unordered_map 容器中,主键通常被用来唯一标志(Uniquely identify)一个元素,而被映射的值保存了与该主键关联的内容。主键与被映射值的类型可以不同,在模板内部,这两种类型合并绑定成成员类型 value_type。由上述描述可知,value_type 是一个双元组类型(Pair type),具体定义如下:

    typedef pair<const Key, T> value_type;

    unordered_map 内部,元素不会按任何顺序排序,而是通过主键的 hash 值将元素分组放置到各个槽(Bucket,也可译成“桶”)中,这样就能通过主键快速地访问各个对应的元素(平均耗时为一个常量,即时间复杂度为 O(1))。

    在访问容器中的某个元素时,unordered_map 容器比 map 容器高效,而在迭代容器元素的某个子集时,前者比后者稍微低效了一点。

    unordered_map 实现了直接访问操作符(operator[]),使得可以通过主键(Key value)直接访问被映射的值(Mapped value)。

    unordered_map 容器支持正向迭代。

    The unordered_map class supports forward iterators.

    C++编程语言国际标准:ISO/IEC 14882:2011

  • 成员类型 定义
    key_type 第一个模板参数 Key
    mapped_type 第二个模板参数 T
    value_type std::pair<const Key, T>
    size_type 无符号整数类型(通常为 size_t
    difference_type 有符号整数类型(通常为 ptrdiff_t
    hasher 第三个模板参数 Hash
    key_equal 第四个模板参数 KeyEqual
    allocator_type 第五个模板参数 Alloc
    reference value_type&
    const_reference const value_type&
    pointer std::allocator_traits<Allocator>::pointer
    const_pointer std::allocator_traits<Allocator>::const_pointer
    iterator 正向迭代器
    const_iterator 常正向迭代器
    local_iterator 本地迭代器,可以迭代一个槽的元素,但不能跨槽迭代
    const_local_iterator 常本地迭代器,可以迭代一个槽的元素,但不能跨槽迭代
  • (constructor) 创建 unordered_map
    (destructor) 释放 unordered_map
    operator= 值赋操作

    ​Iterators:

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

    Capacity:

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

    Element access:

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

    Modifiers:

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

    Observers:

    hash_function 返回 hash 函数
    key_eq 返回主键等价性判断谓词

    Operations:

    find 通过给定主键查找元素
    count 返回匹配给定主键的元素的个数
    equal_range 返回值匹配给定搜索值的元素组成的范围

    Buckets:

    bucket_count 返回槽(Bucket)
    max_bucket_count 返回最大槽数
    bucket_size 返回槽大小
    bucket 返回元素所在槽的序号

    Hash policy:

    load_factor 返回载入因子,即一个元素槽(Bucket)的最大元素数
    max_load_factor 返回或设置最大载入因子
    rehash 设置槽数
    reserve 请求改变容器容量

    Allocator:

    get_allocator 获得内存分配器
  • operator==、operator!=、operator<、operator<=、operator>、operator>= 

    关系操作符
    std::swap 交换两个无序映射表容器的内容
  • <algorithm> 头文件中包含大量与 unordered_map 容器相关的算法,常使用的有

    搜索算法std::adjacent_findstd::count
    std::count_ifstd::find
    std::find_ifstd::find_end
    std::find_first_ofstd::search
    std::search_nstd::equal
    std::mismatch
    二分查找(Binary search)std::lower_boundstd::upper_bound
    std::equal_rangestd::binary_search
    集合(Set)操作std::includesstd::set_difference
    std::set_intersectionstd::set_union
    std::set_symmetric_difference
    最大与最小std::min_elementstd::max_element
    字典序比较std::lexicographical_compare
    排列生成器std::next_permutation
    std::prev_permutation
    其它操作std::all_ofstd::any_ofstd::none_of
    std::for_eachstd::copystd::copy_if
    std::copy_nstd::copy_backward
    std::movestd::move_backward
    std::swap_rangesstd::iter_swap
    std::transformstd::replace
    std::replace_ifstd::replace_copy
    std::replace_copy_ifstd::fill
    std::fill_nstd::generate
    std::generate_nstd::remove
    std::remove_ifstd::unique
    std::unique_copystd::reverse
    ​std::reverse_copystd::rotate
    std::rotate_copystd::random_shuffle
    std::shufflestd::partition
    std::is_partitionedstd::stable_partition
    std::partition_copystd::merge

    具体内容详见各个功能函数。除了排序(std::sort 等)、堆操作(std::make_heapstd::sort_heap 等)、第n个元素(std::nth_element),适用于 std::vector 的例子基本上都适用于 std::unordered_map,可以参考 vector 与算法 主题,该主题包含大量的代码示例

  • 注意!以下代码仅用于快速了解 unordered_map,具体代码示例请查看各个成员函数或上章节提到的 vector 与算法 主题。

    综合 1

    下面这个例子简单地介绍了 unordered_map 的常用使用方法:

    #include <unordered_map>
    #include <iostream>
     
    namespace ClassFoo{
    void PrintIntDoubleUnOrderedMap(std::unordered_map<int,double>& m, char* pre) {
        std::unordered_map<int,double>::iterator it;
        std::cout << pre;
        for ( it = m.begin(); it != m.end(); it++ )
            std::cout << "(" << it->first << "," << it->second << ") ";
        std::cout << std::endl;
    }
    void UnOrderedMapExample1() {
        std::unordered_map<int,double> foo1;
        // operator[]在主键不存在时,自动创建
        foo1[0] = 32.8;
        // 普通插入
        foo1.insert(std::unordered_map<int,double>::value_type(1, 33.2));
        // 带暗示插入,std::pair<int,double>等价于上述的
        // std::unordered_map<int,double>::value_type
        foo1.insert(foo1.end(),std::pair<int,double>(2,35.8));
        
        // 插入一个范围
        std::unordered_map<int,double> foo2;
        foo2.insert(std::unordered_map<int,double>::value_type(3, 36.4));
        foo2.insert(std::unordered_map<int,double>::value_type(4, 37.8));
        foo2.insert(std::unordered_map<int,double>::value_type(5, 35.4));
        foo1.insert(foo2.begin(),foo2.end());
        PrintIntDoubleUnOrderedMap(foo1,"插入元素后的foo1:");
        // 查找主键4
        std::unordered_map<int,double>::iterator it;
        it = foo1.find(4);
        if( it != foo1.end() )
        {
            std::cout << "foo1.find(4):";
            std::cout << "(" << it->first << "," << it->second << ")" 
                << std::endl;
        }
        // 删除上述找到的元素
        if( it != foo1.end() )
        {
            foo1.erase(it);
        }
        PrintIntDoubleUnOrderedMap(foo1,"删除主键为4的元素后的foo1:");
        
        // 遍历删除主键为2的元素
        for(it = foo1.begin();it != foo1.end();it++)
        {
            //遍历删除主键等于2
            //注意,删除元素会使迭代范围发生变化
            if(it->first == 2)
            {
                foo1.erase(it);
                break;
            }
        }
        // 内部数据
        std::cout << "bucket_count:" << foo1.bucket_count() << std::endl;
        std::cout << "max_bucket_count:" << foo1.max_bucket_count() << std::endl;
        std::cout << "bucket_size:" << foo1.bucket_size(0) << std::endl;
        std::cout << "load_factor:" << foo1.load_factor() << std::endl;
        std::cout << "max_load_factor:" << foo1.max_load_factor() << std::endl;
        PrintIntDoubleUnOrderedMap(foo1,"删除主键为2的元素后的foo1:");
        foo1.clear();
        PrintIntDoubleUnOrderedMap(foo1,"清空后的foo1:");
    }
    }
    int main( )
    {
        ClassFoo::UnOrderedMapExample1();
        return 0;
    }
    

    输出

    插入元素后的foo1:(0,32.8) (1,33.2) (2,35.8) (3,36.4) (4,37.8) (5,35.4) 
    foo1.find(4):(4,37.8)
    删除主键为4的元素后的foo1:(0,32.8) (1,33.2) (2,35.8) (3,36.4) (5,35.4) 
    bucket_count:8
    max_bucket_count:8
    bucket_size:1
    load_factor:0.5
    max_load_factor:1
    删除主键为2的元素后的foo1:(0,32.8) (1,33.2) (3,36.4) (5,35.4) 
    清空后的foo1:​

    综合 2 C++11

    修改自上述例子,使可以演示 C++11 中新增的部份功能,其中涉及的成员函数 unordered_map::atunordered_map::emplaceunordered_map::emplace_hintC++11 中新增的:

    #include <unordered_map>
    #include <iostream>
    
    namespace ClassFoo{
    void PrintIntDoubleUnOrderedMap(std::unordered_map<int,double>& m, char* pre) {
        std::cout << pre;
        for ( auto& t : m )
            std::cout << "(" << t.first << "," << t.second << ")";
        std::cout << std::endl;
    }
    void UnOrderedMapExample2() {
        std::unordered_map<int,double> foo1;
    
        // operator[]在主键不存在时,自动创建
        foo1[0] = 32.8;
    
        // 普通插入
        foo1.insert(std::unordered_map<int,double>::value_type(1, 33.2));
    
        // 带暗示插入,std::pair<int,double>等价于上述的
        // std::unordered_map<int,double>::value_type
        foo1.insert(foo1.end(),std::pair<int,double>(2,35.8));
        
        // 插入一个范围
        std::unordered_map<int,double> foo2;
        foo2.insert(std::unordered_map<int,double>::value_type(3, 36.4));
        foo2.insert(std::unordered_map<int,double>::value_type(4, 37.8));
        foo2.insert(std::unordered_map<int,double>::value_type(5, 35.4));
        foo1.insert(foo2.begin(),foo2.end());
        // 放置插入
        foo1.emplace(6,38.0);
        // 带暗示的放置插入
        foo1.emplace_hint(foo1.end(),7,36.4);
        PrintIntDoubleUnOrderedMap(foo1,"插入元素后的foo1:");
        
        // 修改键值为5的元素中的被
        foo1.at(5) = 100.1;
        PrintIntDoubleUnOrderedMap(foo1,"修改键值为5的元素后的foo1:");
    
        // 查找主键4
        std::unordered_map<int,double>::iterator it;
        it = foo1.find(4);
        if( it != foo1.end() )
        {
            std::cout << "foo1.find(4):";
            std::cout << "(" << it->first << "," << it->second << ")" 
                << std::endl;
        }
    
        // 删除上述找到的元素
        if( it != foo1.end() )
        {
            foo1.erase(it);
        }
        PrintIntDoubleUnOrderedMap(foo1,"删除主键为4的元素后的foo1:");
        
        // 遍历删除主键为2的元素
        for(it = foo1.begin();it != foo1.end();it++)
        {
            //遍历删除主键等于2
            //注意,删除元素会使迭代范围发生变化
            if(it->first == 2)
            {
                foo1.erase(it);
                break;
            }
        }
    
        // 内部数据
        std::cout << "bucket_count:" << foo1.bucket_count() << std::endl;
        std::cout << "max_bucket_count:" << foo1.max_bucket_count() << std::endl;
        std::cout << "bucket_size:" << foo1.bucket_size(0) << std::endl;
        std::cout << "load_factor:" << foo1.load_factor() << std::endl;
        std::cout << "max_load_factor:" << foo1.max_load_factor() << std::endl;
    
        PrintIntDoubleUnOrderedMap(foo1,"删除主键为2的元素后的foo1:");
        foo1.clear();
        PrintIntDoubleUnOrderedMap(foo1,"清空后的foo1:");
    }
    }
    int main( )
    {
        ClassFoo::UnOrderedMapExample2();
        return 0;
    }

    输出

    插入元素后的foo1:(0,32.8)(1,33.2)(2,35.8)(3,36.4)(4,37.8)(5,35.4)(6,38)(7,36.4) 
    修改键值为5的元素后的foo1:(0,32.8)(1,33.2)(2,35.8)(3,36.4)(4,37.8)(5,100.1)(6,38)(7,36.4) 
    foo1.find(4):(4,37.8)
    删除主键为4的元素后的foo1:(0,32.8)(1,33.2)(2,35.8)(3,36.4)(5,100.1)(6,38)(7,36.4) 
    bucket_count:8
    max_bucket_count:8
    bucket_size:1
    load_factor:0.75
    max_load_factor:1
    删除主键为2的元素后的foo1:(0,32.8)(1,33.2)(3,36.4)(5,100.1)(6,38)(7,36.4) 
    清空后的foo1:​

    主键及被映射值都为对象

    下面这个例子实现了最简单的电话簿功能:

    #include <iostream>
    #include <unordered_map>
    #include <string>
    
    namespace ClassFoo{
    using namespace std;
    class name {
        string str;
    public:
        name() {}
        name(string s) { str = s; }
        string& get() { return str; }
    
    };
    
    class phoneNum {
        string str;
    public:
        phoneNum() { }
        phoneNum(string s) { str = s; }
        string& get() { return str; }
    };
    
    struct ClassFooHash{
        size_t operator()(name a) {
            hash<string> sh;
            return sh(a.get());
        }
    };
    
    struct ClassFooEqual{
        bool operator()(name a,name b) {
            return a.get() == b.get();
        }
    };
    void UnOrderedMapExample3() {
        unordered_map<name, phoneNum,ClassFooHash,ClassFooEqual> directory;
    
        directory.insert(pair<name, phoneNum>(name("A"), phoneNum("555-1111")));
        directory.insert(pair<name, phoneNum>(name("B"), phoneNum("555-2222")));
        directory.insert(pair<name, phoneNum>(name("C"), phoneNum("555-3333")));
        directory.insert(pair<name, phoneNum>(name("D"), phoneNum("555-4444")));
    
    
        unordered_map<name, phoneNum,ClassFooHash,ClassFooEqual>::iterator p;
    
        p = directory.find(name("A"));
        if(p != directory.end())
            cout << "A的电话号码为: " <<  p->second.get() << endl;
        else
            cout << "未发现A的电话号码" <<endl;
    }
    }
    int main()
    {
        ClassFoo::UnOrderedMapExample3();
        return 0;
    }

    输出

    A的电话号码为: 555-1111