怎样建设与维护自己的平台网站,海南疾控发布问卷调查,网站设计职业工作室,shopify可以做企业网站嘛文章目录1.关联式容器2.键值对3.树形结构的关联式容器3.1 set3.1.1 set的介绍3.1.2 set的模板参数列表3.1.3 set的使用3.2 mapmap的介绍map的模板参数列表map的使用关于map的元素访问总结3.3multimap1.关联式容器
我们接触过STL中的部分容器#xff0c;比如#xff1a;vecto…
文章目录1.关联式容器2.键值对3.树形结构的关联式容器3.1 set3.1.1 set的介绍3.1.2 set的模板参数列表3.1.3 set的使用3.2 mapmap的介绍map的模板参数列表map的使用关于map的元素访问总结3.3multimap1.关联式容器
我们接触过STL中的部分容器比如vector,list,deque,forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。那么什么是关联式容器它与序列式容器有什么区别
关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key,value结构的键值对在数据检索时比序列式容器效率更高。
2.键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该单词在词典就可以找到与其对应的中文含义比如每个学生的学号跟他的姓名年龄专业类型可定义成数组存在对应关系找到学号就可以查到这个学生的相关信息。
SGI-STL中关于键值对的定义
//STL中关于键值对的定义
templateclass T1,class T2
struct pair
{typedef T1 first_type;typedef T2 first_type;T1 first;T2 second;//构造函数初始化pair():first(T1())//key,second(T2())//value{}//拷贝构造函数,使用实例pairstring,intpair(const T1 a,const T2 b):first(a),second(b){}
};3.树形结构的关联式容器
根据应用场景不同STL总共实现了两种不同结构的关联式容器树形结构与哈希结构。树形结构的关联式容器主要有四种mapsetmultimapmultiset。这四种容器的共同点是使用平衡二叉树即红黑树作为底层容器中的元素是一个有序的序列。下面依次介绍每一个容器。
3.1 set
3.1.1 set的介绍
1.set翻译为集合是一个内部自动有序且不含重复元素的关联式容器。当我们想要去重就可以利用到set是一个很直观的接口并且加入set之后可以实现自动排序需要注意的是set的元素默认按照小于比较。 2、在set中每个value必须是唯一的。set中的元素不能在容器中修改元素总是const但是可以在容器中插入或删除数据。一般的做法是先删除旧元素然后添加新元素这当然是为了维护里面元素的有序性。 3.set在底层使用二叉搜索树红黑树实现的。 4.与map/multimap不同map/multimap中存储的是真正的键值对key,value,而set中只放value但在底层实际存放的是由value,value构成的键值对。 5.在set中查找某个元素时间复杂度为log2N
3.1.2 set的模板参数列表
//头文件
#includeset
std::set
templateclass T,class Compare lessT,class Alloc allocatorTT:set中存放元素的类型实际在底层存储value, value的键值对。 Compare仿函数set中元素默认按照小于来比较 Allocset中元素空间的管理方式使用STL提供的空间配置器管理
3.1.3 set的使用
点此进入-set的文档 我在下列代码一一解释了关于set常见的函数该如何使用 #includeiostream
#includeset
using namespace std;
int main()
{setint myset;//定义//迭代器的使用setint::iterator itlow, itup;for (int i 1; i 10; i){//插入数据//注意set会将元素自动排序myset.insert(i * 10);//10 20 30 40 50 60 70 80 90}//删除35-75之间的数据itlow myset.lower_bound(35);//返回第一个大于等于key_value的定位器itup myset.upper_bound(75);//返回最后一个小于等于key_value的定位器//注意set中的删除操作不进行错误检查所以用的时候最好用一下find()函数,//返回给定值定位器如果没找到则返回end()。myset.erase(itlow, itup);/*for (auto it myset.begin(); it ! myset.end(); it){cout *it ;}*///这里可以使用范围for需要加因为拷贝也是存在一定代价的不需要修改的话也尽量加const//范围for的底层是迭代器,操作由编译器完成for (auto s : myset){cout s ;}cout endl;//count() 用来查找set中某个键值出现的次数。这个函数在set并不是很实用在map中的用处比较大//因为一个键值在set只可能出现0或1次这样就变成了判断某一键值是否在set出现过。cout myset.count(100) endl;//0不存在cout myset.count(30) endl;//1存在return 0;
}3.2 map
map的介绍
点此进入-map的官方文档
1.map是关联式容器它按照特定的次序按照key来排序存储由key和value组合而成的元素。 2.map中是真正的键值对key,value,键值key和值value的类型可能不同并且在map内部key与value通过成员类型value_type绑定在一起取名为pair。
typedef pairconst key,T value_type在内部map中的元素总是按照键值key进行比较排序的。map支持下标访问即在[]中放入key就可以找到与key对应的value。在map中key不允许修改key对应的value可以修改。map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
map的模板参数列表
相比setmap多了一个参数
#includemap
std::map
templateclass key,class T,class Compare lesskey,class Alloc allocatorpairconst Key,Tkey: 键值对中key的类型 T 键值对中value的类型 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比 较 Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的 空间配置器 注意在使用map时需要包含头文件。
map的使用
map的官方文档已包括所有关于map的接口函数现在我们来尝试使用它的常用接口。 最重要的应该有插入函数insert[ ]下标访问操作符对于pair的理解迭代器的使用删除函数。
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{//定义一个map对象mapint, string Stu;//1.用insert函数插入pairStu.insert(pairint, string(01, 张三));Stu.insert(pairint, string(02, 李四));Stu.insert(pairint, string(03, 王五));//但是我们发现在这里写一个pair很不方便因此我们可以用make_pair//make_pair的底层是一个函数模板还是调用pair去构造/*templateclass T1,class T2pairT1,T2 make_pair(T1 x,T2 y){return (pairT1, T2(x, y));}*/Stu.insert(make_pair(04, 李芳));//3.第三种用[]的方式插入数据Stu[123] 王五;//4.map的迭代器//mapint, string::iterator it Stu.begin();auto it Stu.begin();while (it ! Stu.end()){cout it-first : it-second endl;it;}//最好加上引用如果不修改的话把const加上更好for (const auto kv : Stu){cout kv.first : kv.second endl;}cout endl;return 0;
}活学活用统计水果出现的次数 //利用map统计水果出现的次数string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e: arr){//mapstring, int::iterator it countMap.find(e);auto it countMap.find(e);//find函数找不到则返回end()if (it countMap.end()){countMap.insert(make_pair(e,1));}else{it-second;}}//有个更简洁的方法//for (auto e : arr)//{// countMap[e];//}for (const auto e : countMap){cout e.first : e.second;}关于map的元素访问总结
map中的元素是键值对我们需要学习pair然后学会使用map容器插入数据管理数据。map中的key是唯一的并且不能修改。map默认按照小于升序的方式并且是对key排序的。map中的元素如果用迭代器去遍历是采用中序遍历的方式可以得到一个有序序列。map的底层是一个平衡二叉树红黑树查找效率很高O(logN)。map中[ ]下标访问操作符是一个大头它支持查找修改插入。operator[ ]向map中插入元素的原理用key,T()构造一个键值对然后调用insert()函数将该键值对插入到map中map中的键值对key一定是唯一的如果key已经存在插入失败insert函数返回该key所在位置的迭代器。如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器。operator[ ]函数最后将insert返回值键值对中的value返回。也就是pair类中的second成员注意在元素访问时有一个与operat[ ]类似的函数是at()函数但是这个函数不常用它们都是通过key找到与key对应的value然后返回其引用不同的是当key不存在时operator[]会用默认的pair插入返回该默认的value而at函数会直接抛异常。operator[]底层实现如下-
3.3multimap
注意multimap和map的唯一不同就是map中的key是唯一的而multimap中key是可以重复的。
multimap中的接口可以参考map功能都是类似的。 注意
multimap中的key是可以重复的。multimap中的元素默认将key按照小于来比较。multimap中没有重载operator[]操作。使用时与map包含的头文件相同。
