map 学习(下)——C++ 中的 hash_map, unordered_map

map 学习(下)——C++ 中的 hash_map, unordered_map

接上篇《map 学习(一)——C++中 map 的使用》

一、hash_map

参考《C++ STL中哈希表 hash_map介绍》即可。博主写的很详细。

注: hash_map 不是标准的。笔者写该文档时本来想尝试些一个 hash_map 例程,但发现自己用 Qt + MSVC2010 编译器出现了编译错误。网上原因好像说是 STL 加入标准C++之时,hash_map系列当时还没有完全实现,所以很多平台上虽然安装了 g++ 编译器,但不一定有 hash_map 的实现。所以如果有平台移植的内容,尽量少用 hash_map

二、unordered_map

以下内容翻译自《unordered_map - C++ Reference》

1. 原型

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

2. 说明

unordered_map 是一种关联容器,用于存储由关键值 (Key Value,以下称为Key 值) 映射值 (Mapped Value,以下称为映射值) 组成的元素,并且允许根据其 Key 值快速检索各个元素。 在 unordered_map 容器中,Key 值通常用来唯一标识元素,映射值是与该 Key 值关联内容的对象。Key 值与映射值的类型可能不同。 在 unordered_map 内部,元素没有按照其 Key 值与映射值的任何顺序进行排序 ,而是根据它们的 Hash 值组织成桶,允许它们通过其 Key 值直接快速访问单个元素(通常具有常数等级的平均时间复杂度)。 unordered_map 容器与 map 容器相比,通过 Key 值访问各个元素的速度更快,然而通过其元素子集进行范围迭代的效率通常较低。 unordered_map 实现了直接访问操作符 (operator[]),它允许使用 Key 值作为输入参数,直接访问映射值。 容器中的迭代器至少是前向迭代器。

3. 容器属性

  • 关联性
    • 关联容器中的元素的参考地址指的是其 Key 值,而不是他们在容器中的绝对地址;
  • 无序性
    • 无序容器使用 Hash 表来组织元素,这些 Hash 表允许无序容器通过 Key 值快速访问元素;
  • 映射
    • 每个元素将一个 Key 值与映射值关联起来,Key 值用于标识其主要内容是映射值的元素;
  • 唯一关键值
    • 容器中不存在同时拥有相同 Key 值的两个元素;
  • 分配器感知
    • map 容器使用分配器对象动态处理其存储需求。

4. 模板参数

  • Key
    • Key 值的类型。在 unordered_map 中的每个元素都是由其 Key 值唯一指定的。
    • 别名为成员类型 unordered_map::key_type
  • T
    • 映射值的类型。在 unordered_map 中的每个元素,都存储了一些数据作为其映射值。
    • 别名为成员类型 unordered_map::mapped_type(注:不同于 unordered_map::value_type,详细见下面)
  • Hash
    • 一个一元函数对象类型,它将与为 Key 值同类型的对象作为参数,并以此为基础返回类型为 size_t 的唯一值。它可以使实现函数调用符的类,或是指向函数的指针(具体请详细参阅示例的构造函数)。它的默认值是 hash <Key>,它返回一个碰撞概率接近于1.0/std::numeric_limits<sizet>::max()1.0 / std::numeric\_limits <size_t>::max() 的 Hash 值。
    • unordered_map 对象使用该函数返回的散列值,并在内部组织元素,加速了定位各个元素的过程。
    • 别名为成员类型 unordered_map::hasher
  • Pred
    • 一个二元值,它接受两个 Key 类型的参数,并返回一个布尔值。表达式 pred(a, b) 中,pred 是该类型的对象,a, b 是 Key 值,如果 a 被认为与 b 等价,则返回 true。它可以使实现了函数调用运算符的类,或者指向函数的指针(具体请详细参阅示例的构造函数)。它的默认值是 equal_to <Key>,它返回与等号运算符 operator(a==b) 相同的值。
    • unordered_map 对象使用该表达式,来确定两个元素的 Key 值是否等价。在 unordered_map 容器中,没有任何两个元素可以使用该断定产生 true 值(原句:No two elements in an unordered_map container can have keys that yield true using this predicate. ,也许翻译的不对)。
    • 别名为成员类型 unordered_map::key_equal
  • Alloc(通常使用默认值)
    • 用于定义存储分配模型的分类器对象的类型。默认情况下,使用分配器类模板,它定义了最简单的内存分配模型,并且与值无关。
    • 别名为成员类型 unordered_map::allocator_type

在 unordered_map 成员函数的参考中,模板函数假定了相同的名称:Key, T, Hash, Pred, Alloc。 unordered_map 容器元素的迭代器可以访问 Key 值与映射值。为此 unordered_map 定义了一个对应的类 value_type,它的第一个值对应于 Key 值类型的常量版本,第二个值对应于映射值(即模板参数 T):

typedef pair<const Key, T> value_type;

unordered_map 容器的迭代器指向该 value_type 的元素。因此对于一个调用 value_type 的迭代器而言,迭代器指向 unordered_map 的一个元素,它的 Key 值与映射值可以分别用下面的方式进行访问:

unordered_map<Key,T>::iterator it;
(*it).first;             // the key value (of type Key)
(*it).second;            // the mapped value (of type T)
(*it);                   // the "element value" (of type pair<const Key,T>)

当然可以用任何其他的直接访问运算符,如 -> 或 []。例程如下:

it->first;               // same as (*it).first   (the key value)
it->second;              // same as (*it).second  (the mapped value) 

5. 常用函数

(1) bucket

以下内容译自《unordered_map::bucket - C++ Reference》

原型

size_type bucket ( const key_type& k ) const;

说明 定位元素所在的桶,返回 Key 值为输入参数 k 的元素的所在桶号。 桶是容器内部 Hash 表中的一个槽,槽中的元素根据 Key 值分配元素。桶号的编号从 0 到 (bucket_count - 1)。 桶中单个元素可以通过 unordered_map::begin 和 unordered_map::end 返回的范围迭代器进行访问。

例程 下面例程片段摘自后面的程序示例:

    for (auto& x : mymap3) {
        std::cout << "Element [" << x.first << ":" << x.second << "]";
        // 返回元素所在桶号
        std::cout << " is in bucket #" << mymap3.bucket(x.first) << std::endl;
    }

(2) count

以下内容译自《unordered_map::count - C++ Reference》

原型

size_type count ( const key_type& k ) const;

说明 使用给定的 Key 值计算元素。 搜索容器中 Key 值为输入参数 k 的元素,并返回找到元素的数量。由于 unordered_map 容器不允许存在重复的 Key 值,这说明如果容器中存在具有该 Key 值的元素,则该函数返回 1,否则返回 0。

(3) 其他

其他操作函数基本和 map 相同:

  • clear
    • 清除 map 中所有元素;
  • erase
    • 删除 map 中指定位置的元素;
  • insert
    • 在 map 指定位置添加 pair 类型的元素;
  • find
    • 获取 map 中元素的迭代器;
  • begin, end
    • map 的正向迭代器的起始位置与终点位置;

6. 示例

(1) 示例 1

以下示例从《C++11中std::unordered_map的使用》挑选,并加以注释说明。

#include <iostream>
#include <string>
#include <unordered_map>

// reference: http://www.cplusplus.com/reference/unordered_map/unordered_map/at/
typedef std::unordered_map<std::string, std::string> stringmap;

// 将 a, b 融合为一个 unordered_map
stringmap merge(stringmap a, stringmap b) {
    // unordered_map 复制构造函数
    stringmap temp(a);
    // 范围插入,将 b 全部插入进 a 中
    temp.insert(b.begin(), b.end());
    return temp;
}

int main()
{
    //============================
    //   1. unordered_map 元素计算与基础遍历
    //============================
    // 定义第一个 unordered_map
    std::unordered_map<std::string, int> mymap = { { "Mars", 3000 }, { "Saturn", 60000 }, { "Jupiter", 70000 } };

    // 对元素进行计算
    mymap.at("Mars") = 3396;
    mymap.at("Saturn") += 272;
    mymap.at("Jupiter") = mymap.at("Saturn") + 9638;

    // auto:自动判断类型
    // 基于范围的 for 循环,遍历 mymap
    for (auto& x : mymap) {
        std::cout << x.first << ": " << x.second << std::endl;
    }
    std::cout << "mymap.size() is " << mymap.size() << std::endl << std::endl;

    //============================
    //   2. iterator, 迭代器遍历
    //============================
    // 定义第二个 unordered_map
    std::unordered_map<std::string, std::string> mymap2 = { { "Australia", "Canberra" }, { "U.S.", "Washington" }, { "France", "Paris" } };
    std::cout << "mymap2 contains:" << std::endl;

    // 遍历 mymap2
    for (auto it = mymap2.begin(); it != mymap2.end(); ++it)
        std::cout << " " << it->first << ":" << it->second << std::endl;
    std::cout << std::endl;

    // mymap2 分配的各桶中的元素
    std::cout << "mymap2's buckets contain:\n";
    for (unsigned i = 0; i < mymap2.bucket_count(); ++i) {
        std::cout << "bucket #" << i << " contains:";
        for (auto local_it = mymap2.begin(i); local_it != mymap2.end(i); ++local_it)
            std::cout << " " << local_it->first << ":" << local_it->second;
        std::cout << std::endl;
    }

    //============================
    //   3. bucker, 桶操作
    //============================
    // 定义第三个 unordered_map
    std::unordered_map<std::string, std::string> mymap3 = {
            { "us", "United States" },
            { "uk", "United Kingdom" },
            { "fr", "France" },
            { "de", "Germany" }
    };

    // 遍历 mymap3
    for (auto& x : mymap3) {
        std::cout << "Element [" << x.first << ":" << x.second << "]";
        // 返回元素所在桶号
        std::cout << " is in bucket #" << mymap3.bucket(x.first) << std::endl;
    }

    //============================
    //   4. count ,判断元素是否在容器中
    //============================
    // 定义第四个 unordered_map
    std::unordered_map<std::string, double> mymap4 = {
            { "Burger", 2.99 },
            { "Fries", 1.99 },
            { "Soda", 1.50 } };

    // 遍历 mymap4
    for (auto& x : { "Burger", "Pizza", "Salad", "Soda" })
    {
        // 判断 x 是否在容器中
        if (mymap4.count(x)>0)
            std::cout << "mymap4 has " << x << std::endl;
        else
            std::cout << "mymap4 has no " << x << std::endl;
    }

    //============================
    //   5. erase ,删除操作
    //============================
    // 定义第五个 unordered_map
    std::unordered_map<std::string, std::string> mymap5;
    mymap5["U.S."] = "Washington";
    mymap5["U.K."] = "London";
    mymap5["France"] = "Paris";
    mymap5["Russia"] = "Moscow";
    mymap5["China"] = "Beijing";
    mymap5["Germany"] = "Berlin";
    mymap5["Japan"] = "Tokyo";

    // 通过迭代器删除
    mymap5.erase(mymap5.begin());
    // 通过 Key 值删除
    mymap5.erase("France");
    // 通过迭代器范围删除
    mymap5.erase(mymap5.find("China"), mymap5.end());

    // 基于范围的 for 循环,遍历展示删除后的 mymap
    for (auto& x : mymap5)
        std::cout << x.first << ": " << x.second << std::endl;

    //============================
    //   6. find ,搜索操作
    //============================
    // 定义第六个 unordered_map
    std::unordered_map<std::string, double> mymap6 = {
            { "mom", 5.4 },
            { "dad", 6.1 },
            { "bro", 5.9 } };

    std::string input;
    std::cout << "who? ";
    // 输入 mom, dad, bro 中的一个,否则搜索失败返回 Not Found
    getline(std::cin, input);

    // 根据输入参数 Key 值进行搜索,返回一个迭代器
    std::unordered_map<std::string, double>::const_iterator got = mymap6.find(input);

    // find 返回值若为 unordered_map 的尾部,则没有在容器中找到
    if (got == mymap6.end())
        std::cout << "not found";
    else
        std::cout << got->first << " is " << got->second;
    std::cout << std::endl;

    //============================
    //   6. insert ,插入操作
    //============================
    // 定义第七、八个 unordered_map
    std::unordered_map<std::string, double>
        myrecipe,
        mypantry = { { "milk", 2.0 }, { "flour", 1.5 } };

    // 定义插入元素,类型为 pair 的对象
    std::pair<std::string, double> myshopping("baking powder", 0.3);

    // 复制插入
    myrecipe.insert(myshopping);
    // 移动插入
    myrecipe.insert(std::make_pair<std::string, double>("eggs", 6.0));
    // 范围插入
    myrecipe.insert(mypantry.begin(), mypantry.end());  // range insertion
    // 初始化列表插入
    myrecipe.insert({ { "sugar", 0.8 }, { "salt", 0.1 } });    // initializer list insertion

    std::cout << "myrecipe contains:" << std::endl;
    for (auto& x : myrecipe)
        std::cout << x.first << ": " << x.second << std::endl;

    std::cout << std::endl;

    //============================
    //   7. 等于运算符 = 操作
    //============================
    // 初始化列表
    stringmap first = { { "AAPL", "Apple" }, { "MSFT", "Microsoft" } };
    stringmap second = { { "GOOG", "Google" }, { "ORCL", "Oracle" } };
    // 移动
    stringmap third = merge(first, second);
    // 复制
    first = third;

    std::cout << "first contains:";
    for (auto& elem : first) std::cout << " " << elem.first << ":" << elem.second;
    std::cout << std::endl;

    return 0;
}

(2) 示例 2

摘选自 Leetcode 问题 Two Sum:给出一个整数数组,返回两个数的下标值,令其和等于一个指定的目标值。 例:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

有解如下:

#include <unordered_map>
class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target)
    {
        //Key is the number and value is its index in the vector.
        unordered_map<int, int> hash;
        vector<int> result;
        for (int i = 0; i < numbers.size(); i++) {
            int numberToFind = target - numbers[i];

            //if numberToFind is found in map, return them
            if (hash.find(numberToFind) != hash.end()) {
                result.push_back(hash[numberToFind]);
                result.push_back(i);            
                return result;
            }

            //number was not found. Put it in the map.
            hash[numbers[i]] = i;
        }
        return result;
    }
};

算法本身遍历一次,花费了 O(n) 的时间复杂度,遍历过程中的 find() 方法本身花费 O(log n),所以该算法总时间复杂度为 O(nlog n)。

三、map, hash_map, unordered_map 的区别

参考网址: 《c++中map与unordered_map的区别》 《C++中map和hash_map的区别》

1. 头文件

  • map
    • #include <map>
  • hash_map
    • #include <hash_map>
  • unordered_map
    • #include <unordered_map>

2. 内部实现机理

  • map
    • map 内部实现了一个红黑树,该结构具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素,因此,对于map进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行这样的操作,故红黑树的效率决定了map的效率,map只需要提供比较函数(一般为小于函数)即可完成比较;
  • hash_map
    • hash_map 需要提供 hash 函数,以及等于函数;
  • unordered_map
    • unordered_map 内部实现了一个 Hash 表,所以其元素的排列顺序是杂乱无序的。

3. 优缺点

  • map
    • 优点:
      • 有序性:这是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作;
      • 红黑树,内部实现一个红黑书使得 map 的很多操作在 log n 的时间复杂度下就可以实现,因此效率非常的高;
    • 缺点:
      • 空间占用率高,因为 map 内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点,子节点以及红/黑性质,使得每一个节点都占用大量的空间;
    • 适用于具有顺序要求的问题;
  • hash_map
    • 优点:
      • hash_map 查找速度会比map快,而且查找速度基本和数据量大小无关,属于常数级别(但不能说一定比 map 的 log n 级别快,因为 hash 函数本身也有耗时);
    • 缺点:
      • 空间占用多,如果对内存使用很严格,需要认真考虑是否使用 hash_map ;特别是当 hash_map 对象特别多时,更加难以控制;
    • 适用于对效率要求较高的环境;
  • unordered_map
    • 优点:
      • 内部实现了 Hash 表,所以查找速度很快;
    • 缺点:
      • Hash 表的建立比较比较费时;
    • 适用于查找问题;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python

python 三元表达式 if for 构建List 进阶用法

Python中,for...[if]...语句一种简洁的构建List的方法,从for给定的List中选择出满足if条件的元素组成新的List,其中if是可以省略...

930
来自专栏黑泽君的专栏

java中迭代器的原理图解和源码浅析

a:迭代器为什么定义了一个接口而不是实现类?   假如把迭代器定义为一个类,这样我们就可以创建该类的对象,调用该类的方法来实现集合的遍历了。 ...

511
来自专栏Jackson0714

C# 正则表达式

992
来自专栏Django中文社区

基于类的通用视图:ListView 和 DetailView

在开发网站的过程中,有一些视图函数虽然处理的对象不同,但是其大致的代码逻辑是一样的。比如一个博客和一个论坛,通常其首页都是展示一系列的文章列表或者帖子列表。对处...

2787
来自专栏光变

Java编程风格

Java编程的风格介绍,主要参考乐google的java code style。对模糊部分作出了明确的选择。

822
来自专栏大数据钻研

献给前端的小伙伴,祝大家面试顺利!

HTML相关问题 1.XHTML和HTML有什么区别 HTML是一种基本的WEB网页设计语言,XHTML是一个基于XML的置标语言 最主要的不同: XHTM...

2725
来自专栏xx_Cc的学习总结专栏

iOS-正则表达式的简单使用

3307
来自专栏丑胖侠

《Drools7.0.0.Final规则引擎教程》第4章 注释&错误信息

注释 像Java开发语言一样,Drools文件中也可以添加注释。注释部分Drools引擎是会将其忽略调的。单行注释使用“//”,示例如下: rule "Test...

2068
来自专栏琯琯博客

JavaScript 103 条技能

1、原生JavaScript实现字符串长度截取 function cutstr(str, len) { var temp; var ic...

2366
来自专栏ShaoYL

OC正则表达式的简单使用

33013

扫码关注云+社区