c++ primer 笔记第十一章关联容器

第十一章 关联容器

梗概：本章主要介绍了两个关联容器map和set以及其延伸版本。

关联容器支持高效关键字查找访问，主要包括map和set以及他们的无序版本以及multi版本共八种。

 

11.1 使用关联容器

map类型的元素是一个pair，pair中包含一个key一个value，分别是first和second公有成员。支持下标操作。

set类型是一堆关键字的集合，自动去重。

 

11.2 关联容器概述

关联容器不支持位置相关操作如push_back。也不支持使用一个元素值和一个数量值的构造操作。

11.2.1 定义关联容器

map定义时需指定关键字和值类型，set只指定一个关键字类型即可。

初始化方式：1.默认初始化  2.从另一个容器构造 3. 值范围  4.列表初始化

multiset和multimap允许关键字重复。

 

11.2.2 关键字类型的要求

有序容器的元素必须定义元素比较的方法，默认调用<运算符。map中比较关键字key，set中比较元素。

有序容器的元素需要定义一个严格弱序的函数，一般等价于小于等于。运算需要有自反性，传递性。

可以自定义比较函数，在定义时需要指明类型并传递函数指针做初始化参数， 如multiset<Sales_data, decltype(compareIsbn)*> bookStore(compareIsbn);

 

11.2.3 pair类型

pair类型包含两个成员，定义时需要尖括号指定类型。

pair的成员是public的，first和second可以直接.调用。

使用元素的关系运算支持pair的关系运算。

初始化：1.默认初始化  2.圆括号初始化  3.花括号值初始化 4. make_pair自动生成。

 

11.3 关联容器操作

关联容器有三种元素类型： value_type key_type 和 mapped_type。 set中value_type和key_type相同，map中value_type是相应的pair且pair中第一个元素是const类型。map的key_type是关键字类型，mapped_type是关联值的类型。

11.3.1 关联容器迭代器

解引用关联容器迭代器得到value_type类型的引用。

map的value_type是一个pair，pair的第一个元素类型是const因此不能修改第一个元素的值。set的value_type是const类型。

map和set都支持begin和end迭代器，用来自加遍历容器元素。

一般将泛型算法用到关联容器，用到时关联容器一般作为源序列范围或者目标位置。

 

11.3.2 添加元素

使用成员函数insert来添加元素，接受一对迭代器或者一个初始化值列表。

map使用insert函数时参数是一个pair，因此可以接收四种构造pair的参数。

insert返回一个pair，first是迭代器，second是布尔值。当插入的元素关键字已存在，second是false且不做任何操作。

 

11.3.3 删除元素

erase函数删除一个迭代器，一个迭代器，返回void。

删除一个关键字返回size_t类型表示删除的元素数量。

 

11.3.4 map的下标操作

map支持下标操作和at操作。

对于不存在的关键字下表操作插入一个新生成的默认初始化元素。at操作报异常。

下标运算符可能改变对象，因此不能作用于const对象。

下标运算返回值类型是mapped_type的左值。

 

11.3.5 访问元素

find接收关键字返回迭代器。 count接收关键字返回计数值。

lower_bound接收关键字返回第一个大于等于的迭代器。upper_bound接收关键字返回第一个大于的迭代器。

equal_range返回一个左闭右开的迭代器范围。pair类型。

map下标可能产生添加对象的副作用，因此搜索使用find。

三种查找某个元素的方法：

• find+count 逐个遍历
• lower_bound + upper_bound得到范围
• equal_range得到范围

 

11.4 无序容器

无序容器需要调用元素定义的哈希函数以及==操作。

无序容器将关键字哈希然后分配到对应的桶中保存，因此简单快速。

无序容器提供桶管理的操作。

无序容器可以使用含有可以带起哈希函数和==操作的函数的类型。

如  

using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
SD_multiset bookstore(42, hasher, eqOp);

定义时需要传入类型和函数本身。若元素含有==操作，第三个类型和第三个参数可以省略。