第11章_关联容器

使用关联容器

关联容器概述

• 关联容器中的元素是按关键字来保存和访问的
• 关联容器不支持顺序容器的位置相关的操作
• 关联容器的迭代器都是双向的

定义关联容器

map

set

multimap

multiset

关键字类型的要求

有序容器的关键字类型

• 对于有序容器(map, multimap, set, multiset), 关键字类型必须定义元素的比较方法
• 默认情况下, 标准库使用关键字类型的 < 运算符来比较两个关键字
• 可以提供自己定义的操作来代替关键字上的 < 运算符. 所提供的操作必须在关键字类型上定义一个严格弱序(可以将严格弱序看作小于等于)
  • 两个关键字不能同时小于等于对方
  • 如果 k1 <= k2, 且 k2 <= k3, 那么 k1 必须 <= k3
  • 如果存在两个关键字, 任何一个都不小于等于另一个, 那么这两个关键字等价. 若 k1 等价于 k2, k2 等价于 k3, 那么 k1 等价于 k3
• 在实际编程中, 重要的是, 如果一个类型定义了行为正常的 < 运算符, 则它可以用作关键字类型

pair 类型

• make_pair(v1, v2);

关联容器操作

关联容器迭代器

• 当解引用一个关联容器迭代器时, 会得到一个类型为容器的 value_type 的值的引用.
  • 对 map 而言, value_type 是一个 pair 类型, 其 first 成员保存 const 的关键字, second 成员保存值
  • set 的迭代器是 const 的

添加元素

删除元素

map 的下标操作

• map 下标运算符接受一个索引, 获取与此关键字相关联的值. 与其他下标运算符不同的是, 如果关键字并不在 map 中, 会为它创建一个元素并插入到 map 中, 关联值将进行值初始化
• map 下标运算符返回一个左值

访问元素

• find

无序容器

• 不是使用比较运算符来组织元素, 而是使用一个哈希函数和关键字类型的 == 运算符
• 无序容器在存储上组织为一组桶, 每个铜保存零个或多个元素
• 默认情况下, 无序容器使用关键字类型的 == 运算符来比较元素, 使用一个 hash 类型的对象来生成每个元素的哈希值(标准库为内置类型提供了 hash 模板)
• 直接定义关键字类型为自定义类类型的无序容器时, 需要提供 hash 模板版本和 == 运算符(或者在使用定义无序容器时传入这两种可调用对象)