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 条评论
登录 后参与评论

相关文章

来自专栏对角另一面

lodash源码分析之Hash缓存

本文为读 lodash 源码的第四篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

1887
来自专栏用户2442861的专栏

Nginx源码剖析之内存池,与内存管理

    Nginx(发音同 engine x)是一款轻量级的Web 服务器/反向代理服务器及电子邮件(IMAP/POP3)代理服务器,并在一个BSD-like...

914
来自专栏wOw的Android小站

[设计模式]之十二:状态模式

在很多情况下,一个对象的行为取决于一个或多个动态变化的属性,这样的属性叫做状态,这样的对象叫做有状态的(stateful)对象,这样的对象状态是从事先定义好的一...

411
来自专栏前端杂货铺

node中的Stream-Readable和Writeable解读

在node中,只要涉及到文件IO的场景一般都会涉及到一个类-Stream。Stream是对IO设备的抽象表示,其在JAVA中也有涉及,主要体现在四个类-Inpu...

3509
来自专栏wannshan(javaer,RPC)

dubbo路由代码分析3(condition路由器)

这篇说说,dubbo condition类型路由器的路由解析和执行过程 由 https://cloud.tencent.com/developer/artic...

3289
来自专栏

go 语言的序列化与反序列化

与c 语言一样, 在网络编程中, go语言同样需要进行序列化与反序列化 在c语言中, 通常需要一块内存缓冲区用来收 发数据。缓冲区一般定义成char *buff...

2767
来自专栏Golang语言社区

【Go 语言社区】Golang 高效字符串拼接

以下内容摘自许世伟《go语言程序设计》: 连接字符串使用" + "或者使用slice拼接,"这2个转换都不是无代价的" 虽然方便,但是使用+=操作符并不是在一个...

42512
来自专栏猿人谷

总结---3

Email relay 和Email access分别用了什么协议? 答:SMTP,POP3 1:多态是如何实现绑定的? 多态的绑定可以分为运行是多态和编译时多...

1827
来自专栏Python小屋

Python实现字符串与指定密钥循环异或加解密

异或运算在很多密码学算法中都有不同程度的应用,其运算特定在于一个数和另一个数连续异或两次仍得到原来的数。在实际使用中,因为要加密的信息和所使用的密钥在大多数情况...

2756
来自专栏java一日一条

Java 容器相关知识全面总结

Java实用类库提供了一套相当完整的容器来帮助我们解决很多具体问题。因为我本身是一名Android开发者,包括我在内很多安卓开发,最拿手的就是ListView(...

321

扫码关注云+社区