✏️
CPP-17-STL-Cookbook
  • Introduction
  • 前言
  • 关于本书
  • 各章梗概
  • 第1章 C++17的新特性
    • 使用结构化绑定来解包绑定的返回值
    • 将变量作用域限制在if和switch区域内
    • 新的括号初始化规则
    • 构造函数自动推导模板的类型
    • 使用constexpr-if简化编译
    • 只有头文件的库中启用内联变量
    • 使用折叠表达式实现辅助函数
  • 第2章 STL容器
    • 擦除/移除std::vector元素
    • 以O(1)的时间复杂度删除未排序std::vector中的元素
    • 快速或安全的访问std::vector实例的方法
    • 保持对std::vector实例的排序
    • 向std::map实例中高效并有条件的插入元素
    • 了解std::map::insert新的插入提示语义
    • 高效的修改std::map元素的键值
    • std::unordered_map中使用自定义类型
    • 过滤用户的重复输入,并以字母序将重复信息打印出——std::set
    • 实现简单的逆波兰表示法计算器——std::stack
    • 实现词频计数器——std::map
    • 实现写作风格助手用来查找文本中很长的句子——std::multimap
    • 实现个人待办事项列表——std::priority_queue
  • 第3章 迭代器
    • 建立可迭代区域
    • 让自己的迭代器与STL的迭代器兼容
    • 使用迭代适配器填充通用数据结构
    • 使用迭代器实现算法
    • 使用反向迭代适配器进行迭代
    • 使用哨兵终止迭代
    • 使用检查过的迭代器自动化检查迭代器代码
    • 构建zip迭代适配器
  • 第4章 Lambda表达式
    • 使用Lambda表达式定义函数
    • 使用Lambda为std::function添加多态性
    • 并置函数
    • 通过逻辑连接创建复杂谓词
    • 使用同一输入调用多个函数
    • 使用std::accumulate和Lambda函数实现transform_if
    • 编译时生成笛卡尔乘积
  • 第5章 STL基础算法
    • 容器间相互复制元素
    • 容器元素排序
    • 从容器中删除指定元素
    • 改变容器内容
    • 在有序和无序的vector中查找元素
    • 将vector中的值控制在特定数值范围内——std::clamp
    • 在字符串中定位模式并选择最佳实现——std::search
    • 对大vector进行采样
    • 生成输入序列的序列
    • 实现字典合并工具
  • 第6章 STL算法的高级使用方式
    • 使用STL算法实现单词查找树类
    • 使用树实现搜索输入建议生成器
    • 使用STL数值算法实现傅里叶变换
    • 计算两个vector的误差和
    • 使用ASCII字符曼德尔布罗特集合
    • 实现分割算法
    • 将标准算法进行组合
    • 删除词组间连续的空格
    • 压缩和解压缩字符串
  • 第7章 字符串, 流和正则表达
    • 创建、连接和转换字符串
    • 消除字符串开始和结束处的空格
    • 无需构造获取std::string
    • 从用户的输入读取数值
    • 计算文件中的单词数量
    • 格式化输出
    • 使用输入文件初始化复杂对象
    • 迭代器填充容器——std::istream
    • 迭代器进行打印——std::ostream
    • 使用特定代码段将输出重定向到文件
    • 通过集成std::char_traits创建自定义字符串类
    • 使用正则表达式库标记输入
    • 简单打印不同格式的数字
    • 从std::iostream错误中获取可读异常
  • 第8章 工具类
    • 转换不同的时间单位——std::ratio
    • 转换绝对时间和相对时间——std::chrono
    • 安全的标识失败——std::optional
    • 对元组使用函数
    • 使用元组快速构成数据结构
    • 将void*替换为更为安全的std::any
    • 存储不同的类型——std::variant
    • 自动化管理资源——std::unique_ptr
    • 处理共享堆内存——std::shared_ptr
    • 对共享对象使用弱指针
    • 使用智能指针简化处理遗留API
    • 共享同一对象的不同成员
    • 选择合适的引擎生成随机数
    • 让STL以指定分布方式产生随机数
  • 第9章 并行和并发
    • 标准算法的自动并行
    • 让程序在特定时间休眠
    • 启动和停止线程
    • 打造异常安全的共享锁——std::unique_lock和std::shared_lock
    • 避免死锁——std::scoped_lock
    • 同步并行中使用std::cout
    • 进行延迟初始化——std::call_once
    • 将执行的程序推到后台——std::async
    • 实现生产者/消费者模型——std::condition_variable
    • 实现多生产者/多消费者模型——std::condition_variable
    • 并行ASCII曼德尔布罗特渲染器——std::async
    • 实现一个小型自动化并行库——std::future
  • 第10章 文件系统
    • 实现标准化路径
    • 使用相对路径获取规范的文件路径
    • 列出目录下的所有文件
    • 实现一个类似grep的文本搜索工具
    • 实现一个自动文件重命名器
    • 实现一个磁盘使用统计器
    • 计算文件类型的统计信息
    • 实现一个工具:通过符号链接减少重复文件,从而控制文件夹大小
Powered by GitBook
On this page
  • How to do it...
  • How it works...

Was this helpful?

  1. 第2章 STL容器

std::unordered_map中使用自定义类型

当我们使用std::unordered_map代替std::map时,对于键的选择要从另一个角度出发。std::map要求键的类型可以排序。因此,元素可以进行排序。不过,当我们使用数学中的向量作为键呢?这样一来就没有判断哪个向量大于另一个向量,比如向量(0, 1)和(1, 0)无法相比较,因为它们指向的方向不同。在std::unordered_map中这都不是问题,因为不需要对键的哈希值进行排序。对于我们来说只要为类型实现一个哈希函数和等同==操作符的实现,等同操作符的是实现是为了判断两个对象是否完全相同。本节中,我们就来实验一下这个例子。

How to do it...

本节中,我们要定义一个简单的coord数据结构,其没有默认哈希函数,所以我们必须要自行定义一个。然后我们会使用coord对象来对应一些值。

  1. 包含使用std::unordered_map所必须的头文件

    #include <iostream>
    #include <unordered_map>
  2. 自定义数据结构,这是一个简单的数据结构,还不具备对应的哈希函数:

    struct coord {
        int x;
        int y;
    };
  3. 实现哈希函数是为了能让类型作为键存在,这里先实现比较操作函数:

    bool operator==(const coord &l, const coord &r)
    {
        return l.x == r.x && l.y == r.y;
    }
  4. 为了使用STL哈希的能力,我们打开了std命名空间,并且创建了一个特化的std::hash模板。其使用using将特化类型进行别名。

    namespace std
    {
    template <>
    struct hash<coord>
    {
        using argument_type = coord;
        using result_type = size_t;
  5. 下面要重载该类型的括号表达式。我们只是为coord结构体添加数字,这是一个不太理想的哈希方式,不过这里只是展示如何去实现这个函数。一个好的散列函数会尽可能的将值均匀的分布在整个取值范围内,以减少哈希碰撞。

        result_type operator()(const argument_type &c) const
        {
            return static_cast<result_type>(c.x)
                      + static_cast<result_type>(c.y);
        }
    };
    }
  6. 我们现在可以创建一个新的std::unordered_map实例,其能结构coord结构体作为键,并且对应任意值。例子中对std::unordered_map使用自定义的类型来说,已经很不错了。让我们基于哈希进行实例化,并填充自定义类型的map表,并打印这个map表:

    int main()
    {
        std::unordered_map<coord, int> m { 
            { {0, 0}, 1}, 
            { {0, 1}, 2},
            { {2, 1}, 3}
        };
        for (const auto & [key, value] : m) {
            std::cout << "{(" << key.x << ", " << key.y
                     << "): " << value << "} ";
        }
        std::cout << '\n';
    }
  7. 编译运行这个例子,就能看到如下的打印信息:

    $ ./custom_type_unordered_map
    {(2, 1): 3} {(0, 1): 2} {(0, 0): 1}

How it works...

通常实例化一个基于哈希的map表(比如: std::unordered_map)时,我们会这样写:

std::unordered_map<key_type, value_type> my_unordered_map;

编译器为我们创建特化的std::unordered_map时,这句话背后隐藏了大量的操作。所以,让我们来看一下其完整的模板类型声明:

template<
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map;

这里第一个和第二个模板类型,我么填写的是coord和int。另外的三个模板类型是选填的,其会使用已有的标准模板类。这里前两个参数需要我们给定对应的类型。

对于这个例子,class Hash模板参数是最有趣的一个:当我们不显式定义任何东西时,其就指向std::hash<key_type>。STL已经具有std::hash的多种特化类型,比如std::hash<std::string>、std::hash<int>、std::hash<unique_ptr>等等。这些类型中可以选择最优的一种类型类解决对应的问题。

不过,STL不知道如何计算我们自定义类型coord的哈希值。所以我们要使用我们定义的类型对哈希模板进行特化。编译器会从std::hash特化列表中,找到我们所实现的类型,也就是将自定义类型作为键的类型。

如果新特化一个std::hash<coord>类型,并且将其命名成my_hash_type,我们可以使用下面的语句来实例化这个类型:

std::unordered_map<coord, value_type, my_hash_type> my_unordered_map;

这样命名就很直观,可读性好,而且编译器也能从哈希实现列表中找到与之对应的正确的类型。

Previous高效的修改std::map元素的键值Next过滤用户的重复输入,并以字母序将重复信息打印出——std::set

Last updated 4 years ago

Was this helpful?