Skip to content

Latest commit

 

History

History
144 lines (109 loc) · 6.97 KB

ch11.md

File metadata and controls

144 lines (109 loc) · 6.97 KB

第十一章 关联容器

  • 关联容器和顺序容器的不同:关联容器中的元素时按照关键字来保存和访问的。
  • 关联容器支持通过关键字来高效地查找和读取元素,基本的关联容器类型是 mapset

关联容器类型

容器类型 解释
按顺序存储
map 关键数组:保存关键字-值
set 关键字即值,即只保存关键字的容器
multimap 支持同一个键多次出现的map
multiset 支持同一个键多次出现的set
无序集合
unordered_map 用哈希函数组织的map
unordered_set 用哈希函数组织的set
unordered_multimap 哈希组织的map,关键字可以重复出现
unordered_multiset 哈希组织的set,关键字可以重复出现

关联容器概述

定义关联容器

  • 需要指定元素类型。
  • 列表初始化:
    • mapmap<string, int> word_count = {{"a", 1}, {"b", 2}};
    • setset<string> exclude = {"the", "a"};

关键字类型的要求

  • 对于有序容器,关键字类型必须定义元素比较的方法。默认是<
  • 如果想传递一个比较的函数,可以这样定义:multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

pair

  • utility头文件中定义。
  • 一个pair保存两个数据成员,两个类型不要求一样。

pair的操作

操作 解释
pair<T1, T2> p; p是一个pair,两个类型分别是T1T2的成员都进行了值初始化。
pair<T1, T2> p(v1, v2); firstsecond分别用v1v2进行初始化。
pair<T1, T2>p = {v1, v2}; 等价于`p(v1, v2)
make_pair(v1, v2); pair的类型从v1v2的类型推断出来。
p.first 返回p的名为first的数据成员。
p.second 返回p的名为second的数据成员。
p1 relop p2 运算关系符按字典序定义。
p1 == p2 必须两对元素两两相等
p1 != p2 同上

关联容器操作

关联容器额外的类型别名

类型别名 解释
key_type 此容器类型的关键字类型
mapped_type 每个关键字关联的类型,只适用于map
value_type 对于map,是pair<const key_type, mapped_type>; 对于set,和key_type相同。

关联容器迭代器

  • 解引用一个关联容器迭代器时,会得到一个类型为容器的value_type的值的引用。
  • set的迭代器是const的。
  • 遍历关联容器:使用beginend,遍历mapmultimapsetmultiset时,迭代器按关键字升序遍历元素。

添加元素

关联容器insert操作

insert操作 关联容器
c.insert(v) c.emplace(args) vvalue_type类型的对象;args用来构造一个元素。 对于mapset,只有元素的关键字不存在c中才插入或构造元素。函数返回一个pair,包含一个迭代器,指向具有指定关键字的元素,以及一个指示插入是否成功的bool值。对于multimapmultiset则会插入范围中的每个元素。
c.insert(b, e) c.insert(il) be是迭代器,表示一个c::value_type�类型值的范围;il是这种值的花括号列表。函数返回void。对于 mapset,只插入关键字不在c中的元素。
c.insert(p, v) c.emplace(p, args) 类似insert(v),但将迭代器p作为一个提示,指出从哪里开始搜索新元素应该存储的位置。返回一个迭代器,指向具有给定关键字的元素。

map添加元素:

  • word_count.insert({word, 1});
  • word_count.insert(make_pair(word, 1));
  • word_count.insert(pair<string, size_t>(word, 1));
  • word_count.insert(map<string, size_t>::value_type (word, 1));

删除元素

从关联容器中删除元素

操作 解释
c.erase(k) c中删除每个关键字为k的元素。返回一个size_type值,指出删除的元素的数量。
c.erase(p) c中删除迭代器p指定的元素。p必须指向c中一个真实元素,不能等于c.end()。返回一个指向p之后元素的迭代器,若p指向c中的尾元素,则返回c.end()
c.erase(b, e) 删除迭代器对be所表示范围中的元素。返回e

下标操作

mapunordered_map的下标操作

操作 解释
c[k] 返回关键字为k的元素;如果k不在c中,添加一个关键字为k的元素,对其值初始化。
c.at(k) 访问关键字为k的元素,带参数检查;若k不存在在c中,抛出一个out_of_range异常。

查找元素

在一个关联容器中查找元素:

操作 解释
c.find(k) 返回一个迭代器,指向第一个关键字为k的元素,若k不在容器中,则返回尾后迭代器
c.count(k) 返回关键字等于k的元素的数量。对于不允许重复关键字的容器,返回值永远是0或1。
c.lower_bound(k) 返回一个迭代器,指向第一个关键字不小于k的元素。
c.upper_bound(k) 返回一个迭代器,指向第一个关键字大于k的元素。
c.equal_range(k) 返回一个迭代器pair,表示关键字等于k的元素的范围。若k不存在,pair的两个成员均等于c.end()
  • lower_boundupper_bound不适用于无序容器。
  • 下标和at操作只适用于非constmapunordered_map

无序容器

  • 有序容器使用比较运算符来组织元素;无序容器使用哈希函数和关键字类型的==运算符。
  • 理论上哈希技术可以获得更好的性能。
  • 无序容器在存储上组织为一组桶(bucket),每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。

无序容器管理操作

操作 解释
桶接口
c.bucket_count() 正在使用的桶的数目
c.max_bucket_count() 容器能容纳的最多的桶的数目
c.bucket_size(n) n个桶中有多少个元素
c.bucket(k) 关键字为k的元素在哪个桶中
桶迭代
local_iterator 可以用来访问桶中元素的迭代器类型
const_local_iterator 桶迭代器的const版本
c.begin(n)c.end(n) n的首元素迭代器
c.cbegin(n)c.cend(n) 与前两个函数类似,但返回const_local_iterator
哈希策略
c.load_factor() 每个桶的平均元素数量,返回float值。
c.max_load_factor() c试图维护的平均比桶大小,返回float值。c会在需要时添加新的桶,以使得load_factor<=max_load_factor
c.rehash(n) 重组存储,使得bucket_count>=n,且bucket_count>size/max_load_factor
c.reverse(n) 重组存储,使得c可以保存n个元素且不必rehash