欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-21 14:27:34
...

第十一章 关联容器

梗概:本章主要介绍了两个关联容器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);

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

相关标签: C primer