关联容器 11.0 概述作者简介: 博主在读机器人研究生,目前研一。对计算机后端感兴趣,喜欢 c + + , g o , p y t h o n , 目前熟悉 c + + , g o 语言,数据库,网络编程,了解分布式等相关内容 textcolor{orange}{博主在读机器人研究生,目前研一。对计算机后端感兴趣,喜欢c++,go,python,目前熟悉c++,go语言,数据库,网络编程,了解分布式等相关内容} 博主在读机器人研究生,目前研一。对计算机后端感兴趣,喜欢c++,go,python,目前熟悉c++,go语言,数据库,网络编程,了解分布式等相关内容
个人主页: textcolor{gray}{个人主页:} 个人主页: 小呆鸟_coding
支持 : textcolor{gray}{支持:} 支持: 如果觉得博主的文章还不错或者您用得到的话,可以免费的关注一下博主,如果三连收藏支持就更好啦 textcolor{green}{如果觉得博主的文章还不错或者您用得到的话,可以免费的关注一下博主,如果三连收藏支持就更好啦} 如果觉得博主的文章还不错或者您用得到的话,可以免费的关注一下博主,如果三连收藏支持就更好啦 就是给予我最大的支持! textcolor{green}{就是给予我最大的支持!} 就是给予我最大的支持!
本文摘要文章目录
本专栏主要是对c++ primer这本圣经的总结,以及每章的相关笔记。目前正在复习这本书。同时希望能够帮助大家一起,学完这本书。 本文主要讲解第11章 关联容器
- 关联容器
- 11.0 概述
- 11.1 使用关联容器
- 11.2 关联容器概述
- 11.2.1 定义关联容器
- 11.2.2 关键字类型要求
- 11.2.3 pair类型
- 11.3 关联容器操作
- 11.3.1 关联容器迭代器
- 11.3.2 添加元素
- 11.3.3 删除元素
- 11.3.4 map的下标操作
- 11.3.5 访问与查找元素
- 11.4 无序容器
- 关联容器中的元素按关键字来保存和访问
- 顺序容器中的元素按他们在容器中的位置来保存和访问
- 关联容器与顺序容器许多行为相同,但是有着根本不同,不同之处反应关键字作用
关联容器支持高效的关键字查找和访问
关联容器包括map 和 set。
头文件定义
- map 和 multimap 在头文件 map 中,
- set 和 multiset 在头文件 set 中,
- 无序 map 和无序 set 分别在头文件 unordered_map 和 unordered_set 中。
容器类型 | 解释 |
---|---|
按关键字有序保存元素 | |
map | 关键数组:保存关键字-值对 |
set | 关键字即值,即只保存关键字的容器 |
multimap | 支持同一个键多次出现的map |
multiset | 支持同一个键多次出现的set |
无序集合 | |
unordered_map | 用哈希函数组织的map |
unordered_set | 用哈希函数组织的set |
unordered_multimap | 哈希组织的map,关键字可以重复出现 |
unordered_multiset | 哈希组织的set,关键字可以重复出现 |
使用map
- map一般用来保存关键字和值的映射,例如关键字是姓名,值是电话,爱好等。
- map 可以使用范围 for 循环,得到的结果是pair
mapword_count; while(cin>>word) ++word_count[word]; for(const auto &w : word_count) { cout << w.first << w.second }
使用set
- set通常用来判断一个值是否存在
- set 可以使用范围 for 循环
map11.2 关联容器概述word_count; set exclude = {"the","a","hello"}; while(cin>>word) if(exclude.find(word) == exclude.end()) ++word_count[word];
- 所有的有序、无序关联容器都支持下面这些普通容器的公共操作。
- 关联容器不支持顺序容器的位置相关的操作,例如push_front,push_back等关联容器中的元素是根据关键字存储的。
- 关联容器的迭代器都是双向的。
'类型别名' iterator const_iterator value_type //容器元素类型。定义方式: vector::value_type reference //元素类型的引用。定义方式: vector ::reference const_reference //元素的 const 左值类型 '构造函数'-'三种通用的构造函数:同类拷贝、迭代器范围初始化、列表初始化' C c1; // 默认构造函数,构造空容器。 C c1 (c2); // 拷贝构造函数,容器类型与元素类型必须都相同 C c1 (c2.begin(), c2.end()); // 要求两种元素类型可以转换即可。 C c1 {a, b, c, ...}; // 使用初始化列表,容器的大小与初始化列表一样大 // 只有顺序容器的构造函数可以接受大小参数,关联容器不行。 '赋值与swap' c1 = c2; c1 = {a,b,c,....} a.swap(b); swap(a,b);//两种 swap 等价 '大小' c.size(); c.max_size();//c 可以保存的最大元素数目,是整个内存层面的容量,不是已分配内存。不同于 caplity, caplity 只能用于 vector,queue,string c.empty(); '添加/删除元素(不适用于array)' c.insert(args); //将 args 中的元素拷贝进 c,args 是一个迭代器或迭代器范围 c.emplace(inits);//使用 inits 构造 c 中的一个元素 c.erase(args);//删除指定的元素,args 是一个迭代器或迭代器范围 c.clear(); '关系运算符' ==; !=; <; <=; >; >= //所有容器都支持相等和不等运算符。无序关联容易不支持大于小于运算符。 '获取迭代器' c.begin(); c.end(); c.cbegin(); c.cend(); //返回 const_iterator '反向容器的额外成员' reverse_iterator //逆序迭代器,这是一个和 iterator 不同的类型 const_reverse_iterator c.rbegin();c.rend(); c.crbegin();c.crend();
关联容器特有操作
'类型别名' key_type //关键字类型 mapped_type //每个关联的类型,只适用于 map value_type //对于 set,与 key_type 相同,对于 map,为 pair11.2.1 定义关联容器
- 需要指定元素类型。
- 关联容器的初始化可以使用直接初始化(使用小括号)、列表初始化(使用花括号)、拷贝初始化(使用等号)。
- 使用迭代器范围进行直接初始化时,如果迭代器范围中有重复关键字,生成的 set 和 map 会自动去除重复的元素。
值初始化
- 除了三种构造函数外,关联容器可以进行值初始化。初始化器必须能转换为容器中元素的类型。
mapword_count = {{"a", 1}, {"b", 2}}; set exclude = {"the", "a"};
注意:初始化map时需要将每个关键字-值包围在花括号中{key-value}
初始化 multiset 和 multimap
- 一个map和set中的关键字必须是唯一的,但是对于multiset和multmap可以有多个相同的关键字。
- 使用迭代器范围进行直接初始化时,无论有没有重复关键字,都会生成包含所有元素的 multiset 和 multimap。
- 对于有序容器,关键字类型必须定义元素比较的方法。默认是<。
有序容器关键字类型
- 对于有序容器,关键字类型必须定义元素比较的方法。默认是<。
- 可以使用如 vector 等容器的迭代器来作为有序容器的关键字。
- 重载了 < 运算符的类可以直接用作关键字。
- 可以向算法提供一个自己定义的比较操作,操作必须在关键字类型上定义一个严格弱序
- 两个关键字不能同时”小于等于“对方。
- A < B, B < C则A必须小于C(传递性)
- 如果两个关键字互不”小于等于“对方,那么两个就是等价的。容器将它们看做相等。
注意:当俩个关键字是等价的,容器会将这俩个看做相等,当用作map的关键字时,只能有一个元素与这俩个关键字关联,我们可以用俩着中的任意一个来访问
使用关键字类型的比较函数
- 当自己定义了比较操作,必须在定义关联容器时指出来
- 自定义的操作类型(函数指针类型)应在尖括号中紧跟元素类型给出。并将函数名作为参数传递给构造函数。
- 比较函数应该返回 bool 值,两个参数的类型应该都是容器的关键字类型。当第一个参数小于第二个参数时返回真。
'比较函数的定义方式' bool comp(const Sales_data &lhs, const Sales_data &rhs) { return lhs.isbn() < rhs.isbn(); } '定义容器对象' multisetbookstore(comp);
注意:当使用 decltype 获取函数指针时要加上 * 运算符。
11.2.3 pair类型- 在utility头文件中定义。
- 一个pair保存两个数据成员,两个类型不要求一样。
pair 定义
- pair的默认构造函数对数据成员进行值初始化,因此 string,vector 等类型会默认为空,int 会默认为 0。
'直接定义' pairp;//默认初始化 pair p(str, i); pair p{"lala", 16}; pair p = {"lala", 16}; '使用 make_pair' auto p = make_pari(v1, v2);//pair 的类型根据 v1 和 v2 的类型推断。
操作 | 解释 |
---|---|
pair | p是一个pair,两个类型分别是T1和T2的成员都进行了值初始化。 |
pair | first和second分别用v1和v2进行初始化。 |
pair | 等价于`p(v1, v2) |
make_pair(v1, v2); | pair的类型从v1和v2的类型推断出来。 |
p.first | 返回p的名为first的数据成员。 |
p.second | 返回p的名为second的数据成员。 |
p1 relop p2 | 运算关系符按字典序定义。 |
p1 == p2 | 必须两对元素两两相等 |
p1 != p2 | 同上 |
创建 pair 类型的返回值
- 如果一个函数返回一个 pair,可以对返回值进行列表初始化或隐式构造返回值
pair11.3 关联容器操作process(bool a){ if(a) return {"lala",16};//列表初始化 else return pair ();//隐式构造返回值 } '也可以使用make_pair' return make_pair(v.back, v.back.size());
- 关联容器还有特殊的类型别名
'类型别名' key_type //关键字类型 mapped_type //每个关联的类型,只适用于 map value_type //对于 set,与 key_type 相同,对于 map,为 pair
注意
- set 的 key_type 类型不是常量,pair 的 first 成员也不是常量,只有 map 的 value_type 中的 first 成员是常量。
- 由于不能改变一个元素的关键字,因此这些pair的关键字部分是const的
- 解引用一个关联容器迭代器时,会得到一个类型为容器的value_type的值的引用。
- 对于map来说value_type是一个pair类型,first成员保存const的关键字,second成员保存值
注意:一个map的value_type是一个pair,可以改变pair的值,但不能改变关键字成员的值
set的迭代器是const
- set 的关键值与 map 的关键值一样,都是不能改变的。
- 可以用 set 的迭代器读取元素值,但不能修改。
遍历关联容器
- map 和 set都支持 begin 和 end 操作
- 遍历关联容器:使用begin和end,遍历map、multimap、set、multiset时,迭代器按关键字升序遍历元素。
关联容器和算法
- 一般不对关联容器使用泛型算法,因为cosnt这一特性意味着不能将关联容器传递给修改或重排容器元素的算法。
- 当对关联容器使用泛型算法时,一般要么把它作为源序列,要么把它作为目的序列。比如从关联容器拷贝元素,向关联容器插入元素等。
- 要是用关联容器所特有的find算法
- 由于map和set(以及对应的无序类型)包含不重复的关键字,因此往容器中插入一个存在的元素对容器没有影响
像map中添加元素
- 关联容器添加元素一般使用 insert 成员,可以添加一个元素也可以添加一个元素范围,或者初始化列表。
mapm; '四种方法' m.insert({word, 1}); //最简单的方法,直接使用花括号 m.insert(make_pair(word, 1)); m.insert(pair (word, 1)); //pair 类型直接定义 m.insert(map ::value_type(word, 1));
使用 emplace 添加元素
s.emplace(args);//args用来构造一个元素,其他和 s.insert(10) 相同 s.emplace(iter, args);//除了 args 其他和 s.insert(iter, 10) 相同
检查insert的返回值
- insert 返回值依赖于容器的类型和参数
- 对于不重复的map和set,添加的单一元素的 insert 和 emplace 都返回一个 pair,pair 内是具有给定关键字的元素的迭代器和一个 bool 值
- 对于不重复的map和set,添加多个元素都返回 void在向 map 或 set 添加元素时,检测 insert 的返回值可以很有用,要灵活使用。
while(cin>>word){ auto ret = word_count.insert({word,1}); if(ret.second = false) ++ret.first->second; } '解释' ret : 保存insert返回的值,是一个pair ret.first : 是pair的第一个成员,是一个map迭代器,指向具有给定关键字的元素 ret.first-> : 解引用此迭代器,提取map中的元素,元素也是一个pair ret.first->second : map中元素的值部分 ++ret.first->second : 递增 '替换' pair
向 multiset 或 multimap 添加元素
- 在 multiset 或 multimap 上调用 insert 总会插入元素。
- 插入单个元素的 insert 返回一个指向新元素的迭代器。
- 关联容器定义了三个版本的erase,其中俩个与顺序容器相似的版本(通过传递迭代器或一个迭代器对来删除一个元素或一个元素范围,返回void)
- 与顺序容器相似版本:注意顺序容器会返回删除元素后一个元素的迭代器,而这里的 erase 返回 void
- 额外版本:输入参数为关键字(key_value 注意不是关键字的迭代器),返回删除的元素数量,对于非重复关键字的容器,返回值总是 1 或 0。
'与顺序容器相似版本的 erase' s.erase(iter); // 删除一个元素,返回 void s.erase(iter1, iter2) // 删除一个范围,返回 void '额外版本' auto cnt = s.erase("lala");//删除一个关键字,返回该关键字对应的元素的数量
删除关联容器的最后一个元素
m.erase(--m.end()); // 正确!m 的迭代器支持自增与自减 m.erase(m.rbegin()); // 错误!
遍历容器删除元素
'map' map11.3.4 map的下标操作m; for(auto iter = m.begin(); iter != m.end(); ){ if(iter->second == 0) m.erase(iter++); //这是循环map删除指定元素的唯一方式。利用了 i++ 的原理 else iter++; } 'vector' vector v; for(auto iter = v.begin(); iter != v.end(); ){ if(*iter == 0) iter = v.erase(iter);//vecotr 的 erase 操作返回所删除元素之后的迭代器 else iter++; }
- map 和 unordered_map 都支持下标操作和对应的 at 函数。
- set 类型则不支持下标。multimap 和 unordered_multimap 不支持下标操作。
- 如果关键字不再 map 中,会创建一个元素并插入到 map 中,关联值将进行值初始化。
注意:
- 因为关联值是值初始化,所以在单词计数程序中,可以直接 map[word]++ ,不必特意插入元素。
- map 的下标操作只能返回非常量引用(不同于顺序容器的下标操作),如果 map 本身是常量,则无法使用下标访问元素,这时要用 at() 函数。
c[k] 返回关键字为k的元素;如果k不在c中,添加一个关键字为k的元素,对其值初始化。 c.at(k) 访问关键字为k的元素,带参数检查;若k不存在在c中,抛出一个out_of_range异常。
使用下标操作的返回值
- 与vector和string不同,map下标运算符返回的类型与解引用map迭代器得到的类型不同
- 解引用一个map迭代器会得到一个value_type对象,对map进行下标操作得到一个mapped_type对象
访问元素
- map 可以通过下标或 at() 函数访问元素。
- set 只能通过迭代器来访问元素。
'基本的访问操作' c[k]; c.at(k);
访问 map/set 的最后一个元素:m.rbegin() 或 --m.end()。
查找元素
- 关联容器查找一个指定元素的方法有多种。一般 find 是最佳选择。
- 对于不允许重复关键字的容器,find 和 count 差别不大,对于允许重复关键字的容器,count 会统计有多少个元素有相同的关键字。
'查找操作' c.find(k);//返回一个迭代器,指向关键字为 k 的元素,如果 k 不在容器中,返回尾后迭代器。 c.count(k);//返回关键字等于 k 的元素数量。 c.lower_bound(k);//返回一个迭代器,指向第一个关键字不小于 k 的元素。 c.upper_bound(k);//返回一个迭代器,指向第一个关键字大于 k 的元素。 c.equal_range(k);//返回一个迭代器 pair,表示关键字等于 k 的元素范围。若干 k 不存在,pair 的两个成员相等,指向可以安全插入 k 的位置
注意
- lower_bound和upper_bound不适用于无序容器。
- 下标和at操作只适用于非const的map和unordered_map。
检查元素是否存在
- 检查元素是否存在用 find 或 count。
if(word_count.find("lala") == word_count.end()) if(word_count.count("lala") == 0)
在 multimap 或 multiset 中查找元素
- 在不允许重复关键字的关联容器查找一个元素简单,要在 multimap 或 multiset 中查找所有具有给定关键字的元素比较麻烦。
- 如果一个mutimap或mutiset中有多个元素具有给定关键字,则这些元素在容器中会相邻存储
三种方法:
- 使用 find 和 count 配合,找到第一个关键字为 k 的元素和所有关键字为 k 的元素数目,遍历完成。
- 使用 lower_bound 和 upper_bound 配合。注意当关键字 k 不存在时,这两个函数返回相同的迭代器,可能是尾后迭代器也可能不是。
- 使用 equal_range。最直接的方法
string a("hello world"); auto sum = authors.count(a); //此作者一共有几本书 suto iter = authors.find(a); //此作者第一本书 while (sum) cout << iter->second << endl; ++iter; -- sum;
for(auto bg = authors.lower_bound(a), ed = authors.upper_bound(a); bg != ed; ++bg) cout << beg->second << endl;
for(auto pos = authors.equal_range(a); pos.first != pos.second; ++pos.first) cout << pos.first->second;11.4 无序容器
- 有序容器使用比较运算符来组织元素;无序容器使用哈希函数和关键字类型的==运算符。
- 无序容器用于关键字类型不好排序的情况。
- 无序容器在存储上组织为一组桶(bucket),每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。
使用无序容器
- 无序容器也有 find,insert,迭代器等操作。
- 在大多数情况下,可以用无序容器替换对应的有序容器,反之亦然。但是注意无序容器中元素未按顺序存储。
管理桶
- 无序容器在存储上组织为一组桶,每个桶保存零个或多个元素。
- 无序容器使用哈希函数将元素映射到桶,并将具有一个特定哈希值的所有元素保存在相同的桶中。如果容器允许重复关键字,那所有具有相同关键字的元素也都在同一个桶中。不同关键字的元素也可能映射到相同的桶。
- 对于相同的参数,哈希函数总是产生相同的结果。
- 当一个桶中保存了多个元素,需要顺序搜索这些元素来查找想要的那个。计算一个元素的哈希值和在桶中搜索通常都很快。
'桶接口' c.bucket_count(); //返回正在使用的桶的数目 c.max_bucket_count(); //返回容器能容纳的最多的桶的数量 c.bucket_size(n); //返回第 n 个桶中有多少个元素 c.bucket(k); //返回关键字为 k 的元素所在的桶 '桶迭代' local_iterator //类型别名,可以用来访问桶中元素的迭代器类型 const_local_iterator //类型别名,桶迭代器的常量版本 c.begin(n), c.end(n) //返回桶 n 的首元素迭代器和尾后迭代器 c.cbegin(n),c.cend(n) '哈希策略' c.load_factor(); //返回每个桶的平均元素数量,类型为 float c.max_load_factor(); //返回 c 试图维护的平均桶大小,类型为 float。c 会在需要时添加新的桶,始终保持 load_factor <= max_loat_factor c.rehash(n); //重组存储,使得 bucket_count >= n 且 bucket_count > size / max_load_factor c.reserve(n); //重组存储,使得 c 可以保存 n 个元素而不必 rehash。
无序容器对关键字的要求
- 默认情况下,无序容器使用 == 运算符比较关键字,使用用一个 hash
(hash 模板)类型的对象来生成每个元素的哈希值。 - 标准库为内置类型(包括指针)和 string、智能指针等都定义了 hash,因此内置类型,string 和智能指针类型都能直接用来作为无序容器的关键字。
- 对于自定义的类类型,不能直接用来作为无序容器的关键字,因为他们不能直接使用 hash 模板,除非提供自己的 hash 模板版本。
'定义自己的 hash 模板版本' size_t hasher(const Sales_data &sd){ return hash() (sd.isbn());//这里采用了标准库的 hash 类型对象来计算 isbn 成员的哈希值,作为整个 Sale_data 对象的哈希值。 } '重载比较函数(这里是相等)' bool eq(const Sales_data &lhs, const Sales_data &rhs){ return lhs.isbn() == rhs.isbn(); } '定义 unordered_multiset' unordered_multiset< Sales_data, decltype(hasher)*, decltype(eq)* > sals;
无论是有序容器还是无序容器,具有相同关键字的元素都是相邻存储的。