网站程序制作软件,怎样做p2p网站,河南网站建设推广,深圳坪山新闻关联容器
关联容器支持高效的关键字查找和访问。 两个主要的关联容器#xff08;associative container#xff09;类型是 map 和 set。 map 中的元素是一些关键字——值对。 关键字起到索引的作用#xff0c;值则表示与索引相关联的数据。 set 中的每个元素只包含一个关键…关联容器
关联容器支持高效的关键字查找和访问。 两个主要的关联容器associative container类型是 map 和 set。 map 中的元素是一些关键字——值对。 关键字起到索引的作用值则表示与索引相关联的数据。 set 中的每个元素只包含一个关键字。 set 支持高效的关键字查询操作——检查一个给定关键字是否在 set 中。 标准库提供 8 个关联容器
容器功能map关联数组保存关键字——值对set关键字即值即只保存关键字的容器multimap关键字可重复出现的mapmultiset关键字可重复出现的setunordered_map用哈希函数组织的mapunordered_set用哈希函数组织的setunordered_multimap哈希函数组织的map关键字可重复出现unordered_multiset哈希函数组织的set关键字可重复出现
允许重复关键字的容器的名字中包含 mutli不保持关键字按顺序存储的容器的名字都以单词 unordered 开头。 map 和 mutlimap 定义在头文件 map 中set 和 mutliset 定义在头文件 set 中无序容器则定义在头文件 unordered_map 和 unordered_set 中。
关联容器概述
定义关联容器
默认初始化 map int, string M1;set char Set; 列表初始化
当初始化一个 map 时必须提供关键字类型和值类型每一个关键字—值对包围在花括号中‘{ key , value }’来指出它们一起构成了 map 中的一个元素。 map int, string M1 {{1,C},{2,Java},{5,Python}};当初始化一个 set 时只需提供关键字类型关键字类型就是元素类型。 set char Set1 { A,B,C };一个 map 或 set 中的关键字必须是唯一的容器 mulitmap 和 mulitset 没有这个限制它们都允许多个元素具有相同的关键字。 map int, string M1{{100,C},{2,Java},{100,Python},{100,C}};cout M1.size() endl; // 内含 2 个元素multimap int, string M2{{100,C},{2,Java},{100,Python},{100,C}};cout M2.size() endl; // 内含 4 个元素set char Set1{ A,B,C,B,B };cout Set1.size() endl; // 内含 3 个元素multiset char Set2{ A,B,C,B,B };cout Set2.size() endl; // 内含 5 个元素将一个新容器创建为另一个容器的拷贝
拷贝整个容器 map int, string M1 {{1,C},{2,Java},{5,Python}};map int, string M2{ M1 };set char Set1 { A,B,C };set char Set2 { Set1 };拷贝迭代器指定范围中的元素 map int, string M1 {{1,C},{2,Java},{5,Python}};map int, string M2{ M1.begin(),M2.end() };set char Set1 { A,B,C };set char Set3{ Set1.begin(),Set1.end() };有序容器的关键字类型的要求
对于有序容器关键字类型必须定义元素比较的方法。 默认情况下标准库使用关键字类型的运算符来比较两个关键字。 向算法提供的自定义比较操作必须在关键字类型上定义一个严格偌序strict weak ordering。 自定义的比较操作必须具备如下基本性质
两个关键字不能同时“小于等于”对方如果 k1 “小于等于” k2那么 k2 绝不能“小于等于” k1。如果 k1 “小于等于” k2且 k2 “小于等于” k3那么 k1 必须“小于等于” k3。如果存在两个关键字任何一个都不“小于等于”另一个那么我们称这两个关键字是“等价”的。如果 k1 “等价于” k2且 k2 “等价于” k3那么 k1 必须“等价于” k3。
pair 类型
名为 pair 的标准库类型定义在头文件 utility 中。 pair 是一个用来生成特定类型的模版。 一个 pair 保存两个数据成员。 当创建一个 pair 时必须提供两个类型名两个类型不要求一样。 pair int, char p; //未指定成员的初始值则进行值初始化pair int, char p{ 10,A }; //指定成员的初始值auto p make_pair(1,A); //返回一个指定了成员初始值的 pairpair 的两个数据成员是 public 的两个成员分别命名为 first 和 second使用普通的成员访问符来访问它们。 pair int, char p{ 10,A };cout p.first endl; //输出 10cout p.second endl; //输出 A关联容器迭代器
当解引用一个关联容器迭代器时会得到一个类型为容器的 value_type 值的引用。 对于 map 而言value_type 是一个 pair 类型其 first 成员保存 const 的关键字second 成员保存值。 map int, string M1{{1,C},{2,Java},{100,Python},{100,C}};auto map_it M1.begin(); //value_type 值的引用cout map_it-first endl; //输出 1关键字值不允许修改cout map_it-second endl; //输出 C对于 set 而言value_type 与 key_type 相同。 set char Set1 {A, B, C};auto set_it Set1.begin();cout *set_it endl; //输出 A关键字值不允许修改遍历关联容器
当使用迭代器遍历有序容器时迭代器按关键字升序遍历元素。 map map int, string M1{{5,C},{2,Java},{100,Python},{10,C}};auto map_it M1.cbegin();while ( map_it ! M1.cend() ){cout { map_it-first , map_it-second } ;map_it;}/*输出{2,Java} {5,C} {10,C} {100,Python}*/set set char Set1 {D, B, A,C};auto set_it Set1.cbegin();while ( set_it ! Set1.cend() ){cout *set_it ;}/*输出A B C D*/map的下标操作
map 和 unordered_map 容器提供了下标运算符和一个对应的 at 函数。 不能对一个 mutlimap 或 unordered_mutlimap 进行下标操作因为该容器中可能有多个值与一个关键字相关联。 set 容器不支持下标访问因为 set 中没有与关键字相关的值。 map 下标运算符接收一个索引即关键字获取与此索引相关联的值。 map char, string M1{{A,C},{C,Java},{D,Python},{F,C}};cout M1[A] endl; //输出 Ccout M1.at(C) endl; //输出 Java如果索引关键字并不在 map 中下标运算符会为它创建一个元素并插入到 map 中关联值将进行值初始化。 map int, char M1{{1,A},{3,B},{5,F}};cout (int)M1[2] endl; //输出 0如果索引关键字并不在 map 中at 函数会抛出一个 out_of_range 异常。 当对一个 map 进行下标操作时会获得一个 mapped_type 对象。 下标运算符和 at 函数只适用于非 const 的 map 和 unordered_mutlimap。
关联容器查找
对 map 使用 find 代替下标操作
成员函数 find 返回一个迭代器指向第一个关键字为 k 的元素若 k 不在容器中则返回尾后迭代器 map char, string M1{{A,C},{C,Java},{D,Python},{F,C}};auto map_it M1.find(C);cout map_it-second endl; //输出 Javalower_bound 和 upper_bound
成员函数 lower_bound 和 upper_bound 不适用于无序容器。 成员函数 lower_bound 返回一个迭代器指向第一个关键字不小于 k 的元素。 map char, string M1{{A,C},{C,Java},{D,Python},{F,C}};auto map_it M1.lower_bound(C);cout map_it-second endl; //输出 Java成员函数 upper_bound 返回一个迭代器指向第一个关键字大于 k 的元素。 map char, string M1{{A,C},{C,Java},{D,Python},{F,C}};auto map_it M1.upper_bound(C);cout map_it-second endl; //输出Python在 multimap 或 multiset 中查找元素
方法一 成员函数 count 返回关键字等于 k 的元素的数量对于不允许重复关键字的容器返回值永远是 0 或 1. multimap char, string M1{{A,C},{B,Java},{B,Python},{B,C}};/*输出所有与关键字B相关联的值 */auto map_it M1.find(B);for (int i 0; i M1.count(B); i){cout map_it-second ;map_it;}方法二 multimap char, string M1{{A,C},{B,Java},{B,Python},{B,C}};/*输出所有与关键字B相关联的值 */auto map_it M1.lower_bound(B);/*如果 lower_bound 和 upper_bound 返回相同的迭代器则给定关键字不在容器中*/while ( map_it ! M1.upper_bound(B) ){cout map_it-second endl;map_it;}方法三 成员函数 equal_range 返回一个迭代器 pair表示关键字等于 k 的元素的范围若 k 不存在pair 的两个成员均等于尾后迭代器。 multimap char, string M1{{A,C},{B,Java},{B,Python},{B,C}};/*输出所有与关键字B相关联的值 */auto p M1.equal_range(B);multimap char, string::iterator map_it p.first;while ( map_it ! p.second ){cout map_it-second endl;map_it;}向关联容器添加元素
向关联容器中插入一个元素。 map 的元素类型是 pair 类型。 map char, string M1;M1.insert( {A,C} );M1.insert( make_pair(B,Java) );M1.insert( pair char, string {C, Python} );M1.insert( map char, string::value_type{ D,C } );set char Set;Set.insert(B);Set.insert(A);成员函数 insert 的返回值。 对于不包含重复关键字的容器添加单一元素的 insert 的版本返回一个 pair 对象。 pair 的 first 成员是一个迭代器指向具有给定关键字的元素 pair 的 second 成员是一个 bool 值 如果关键字已存在容器中则 insert 什么都不做bool 值为 false。 如果关键字不在容器中则元素被插入到容器中bool 值为 true。 map char, string M1;M1.insert( {A,C} );M1.insert( make_pair(B,Java) );auto p M1.insert( { A,C } );cout p.first-second endl; // 输出 Ccout p.second endl; // 输出 0向关联容器中插入一个花括号包围的元素值列表。 vector int V1{ 1,3,5,7,9 };set int Set;Set.insert({ 2,4,6,8,10 });向关联容器中插入一对迭代器指定范围的所有元素第一个迭代器指向要插入的第一个元素第二个迭代器指向要插入的最后一个元素之后的位置。 vector int V1{ 1,3,5,7,9 };set int Set;Set.insert( V1.begin(), V1.end() );删除元素
成员函数 erase 从容器中删除每个与关键字 k 相关联的元素返回一个 size_type 值指出删除的元素的数量。 map char, string M1{{A,C},{C,Java},{D,Python},{F,C}};M1.erase(A); //删除 {A,C}set char Set{ B,C,D,E,A };Set.erase(B); //删除 B成员函数 erase 从容器中删除迭代器 p 指向的元素p 必须指向容器中一个真实元素返回一个指向 p 之后元素的迭代器。 map char, string M1{{A,C},{C,Java},{D,Python},{F,C}};M1.erase( M1.begin(),M1.end() ); //删除所有元素set char Set{ B,C,D,E,A };auto set_its Set.end();--set_its;Set.erase( Set.begin(),set_its ); //删除 A B C D
成员函数 erase 删除一对迭代器指定范围内的所有元素返回指向被删除的元素之后位置的迭代器。 map char, string M1{{A,C},{C,Java},{D,Python},{F,C}};auto map_its M1.begin();map_its;M1.erase(map_its); //删除 {C,Java}set char Set{ B,C,D,E,A };auto set_its Set.end();--set_its;Set.erase( set_its ); //删除 E删除容器内所有的元素
成员函数 clear 删除容器内所有元素。 set char Set{ B,C,D,E,A };Set.clear();无序容器
有序容器使用关键字类型的比较运算符来组织元素。 无序容器使用哈希函数和关键字类型的运算符来组织元素。
管理桶
无序容器在存储上组织为一组桶每个桶保存零个或多个元素。 无序容器使用一个哈希函数将元素映射到桶。 无序容器将具有一个特定哈希值的所有元素都保存在相同的桶中如果容器允许重复关键字所有具有相同关键字的元素也都会在同一个桶中。 为了访问容器中一个元素容器首先计算元素的哈希值它指出应该搜索哪个桶。 无序容器提供了一组管理桶的函数
桶接口
成员函数功能bucket_count ()正在使用的桶的数目max_bucket_count ()容器能容纳的最多的桶的数量bucket_size (n)第 n 个桶中有多少个元素bucket (k)关键字为 k 的元素在哪个桶中
桶迭代
成员功能local_iterrator可以用来访问桶中元素的迭代器类型const_local_iterrator桶迭代器的 const 版本begin (n)桶 n 的首元素迭代器end (n)桶 n 的尾后迭代器cbegin (n)桶 n 的首元素迭代器返回 const_local_iterratorcend (n)桶 n 的尾后迭代器返回 const_local_iterrator
哈希策略
成员函数功能load_factor ()每个桶的平均元素数量返回 float 值max_load_factor ()容器试图维护的平均桶大小返回 float 值容器会在需要时添加新桶使得 load_factor () max_load_factor ()rehash (n)重组存储使得 bucket_count n 且 bucket_count size/max_load_factor ()reserve (k)重组存储使得容器可以保存 n 个元素且不必 rehash
这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。 文章转载自： http://www.morning.rdtq.cn.gov.cn.rdtq.cn http://www.morning.nxzsd.cn.gov.cn.nxzsd.cn http://www.morning.hjwkq.cn.gov.cn.hjwkq.cn http://www.morning.lsgsn.cn.gov.cn.lsgsn.cn http://www.morning.yprnp.cn.gov.cn.yprnp.cn http://www.morning.osshjj.cn.gov.cn.osshjj.cn http://www.morning.lsnhs.cn.gov.cn.lsnhs.cn http://www.morning.srzhm.cn.gov.cn.srzhm.cn http://www.morning.mfrb.cn.gov.cn.mfrb.cn http://www.morning.lpsjs.com.gov.cn.lpsjs.com http://www.morning.fkwp.cn.gov.cn.fkwp.cn http://www.morning.jtmql.cn.gov.cn.jtmql.cn http://www.morning.pphbn.cn.gov.cn.pphbn.cn http://www.morning.hxhrg.cn.gov.cn.hxhrg.cn http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.nfmtl.cn.gov.cn.nfmtl.cn http://www.morning.qineryuyin.com.gov.cn.qineryuyin.com http://www.morning.dongyinet.cn.gov.cn.dongyinet.cn http://www.morning.lgkbn.cn.gov.cn.lgkbn.cn http://www.morning.jwbfj.cn.gov.cn.jwbfj.cn http://www.morning.plcyq.cn.gov.cn.plcyq.cn http://www.morning.kjgdm.cn.gov.cn.kjgdm.cn http://www.morning.fmtfj.cn.gov.cn.fmtfj.cn http://www.morning.jbhhj.cn.gov.cn.jbhhj.cn http://www.morning.mrbzq.cn.gov.cn.mrbzq.cn http://www.morning.tfrmx.cn.gov.cn.tfrmx.cn http://www.morning.zdsqb.cn.gov.cn.zdsqb.cn http://www.morning.jfwrf.cn.gov.cn.jfwrf.cn http://www.morning.jjxnp.cn.gov.cn.jjxnp.cn http://www.morning.fosfox.com.gov.cn.fosfox.com http://www.morning.qcfgd.cn.gov.cn.qcfgd.cn http://www.morning.mhxlb.cn.gov.cn.mhxlb.cn http://www.morning.dywgl.cn.gov.cn.dywgl.cn http://www.morning.wwkft.cn.gov.cn.wwkft.cn http://www.morning.ampingdu.com.gov.cn.ampingdu.com http://www.morning.splcc.cn.gov.cn.splcc.cn http://www.morning.mjjty.cn.gov.cn.mjjty.cn http://www.morning.zyrp.cn.gov.cn.zyrp.cn http://www.morning.wdhzk.cn.gov.cn.wdhzk.cn http://www.morning.qhjkz.cn.gov.cn.qhjkz.cn http://www.morning.qyhcm.cn.gov.cn.qyhcm.cn http://www.morning.mrcpy.cn.gov.cn.mrcpy.cn http://www.morning.wrtw.cn.gov.cn.wrtw.cn http://www.morning.nlkhr.cn.gov.cn.nlkhr.cn http://www.morning.jycr.cn.gov.cn.jycr.cn http://www.morning.ynlpy.cn.gov.cn.ynlpy.cn http://www.morning.pwksz.cn.gov.cn.pwksz.cn http://www.morning.cldgh.cn.gov.cn.cldgh.cn http://www.morning.xykst.cn.gov.cn.xykst.cn http://www.morning.smqjl.cn.gov.cn.smqjl.cn http://www.morning.mxnhq.cn.gov.cn.mxnhq.cn http://www.morning.tygn.cn.gov.cn.tygn.cn http://www.morning.gqfbl.cn.gov.cn.gqfbl.cn http://www.morning.qkzdc.cn.gov.cn.qkzdc.cn http://www.morning.tdcql.cn.gov.cn.tdcql.cn http://www.morning.lwbhw.cn.gov.cn.lwbhw.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.skrxp.cn.gov.cn.skrxp.cn http://www.morning.njpny.cn.gov.cn.njpny.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.fpczq.cn.gov.cn.fpczq.cn http://www.morning.mmqhq.cn.gov.cn.mmqhq.cn http://www.morning.plqsc.cn.gov.cn.plqsc.cn http://www.morning.gllhx.cn.gov.cn.gllhx.cn http://www.morning.kjfsd.cn.gov.cn.kjfsd.cn http://www.morning.ykswq.cn.gov.cn.ykswq.cn http://www.morning.rqwwm.cn.gov.cn.rqwwm.cn http://www.morning.fnmtc.cn.gov.cn.fnmtc.cn http://www.morning.npmcf.cn.gov.cn.npmcf.cn http://www.morning.tgxrm.cn.gov.cn.tgxrm.cn http://www.morning.mhrzd.cn.gov.cn.mhrzd.cn http://www.morning.mnbcj.cn.gov.cn.mnbcj.cn http://www.morning.tpssx.cn.gov.cn.tpssx.cn http://www.morning.klzdy.cn.gov.cn.klzdy.cn http://www.morning.lxbml.cn.gov.cn.lxbml.cn http://www.morning.wbfg.cn.gov.cn.wbfg.cn http://www.morning.rwmq.cn.gov.cn.rwmq.cn http://www.morning.tfei69.cn.gov.cn.tfei69.cn http://www.morning.txmlg.cn.gov.cn.txmlg.cn http://www.morning.jcfdk.cn.gov.cn.jcfdk.cn
