行业知识
C++从零开始的打怪升级之路(day47)
这���关于一个普通双非本科大一学生的C++的学习记录贴
()在此前,我学了一点点C语言还有简单的数据结构,如果有小伙伴想和我一起学习的,可以私信我交流分享学习资料
那么开启正题
()今天分享的是关于set和map的知识点
1.关联式容器
在前面,我们已经学习了STL的部分容器,如vector,list,deque,这些容器被称为序列式容器,因为底层是线性序列的数据结构,里面存储的是元素本身,那么什么是关联式容器呢?
关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是结构的键值对,在数据检索时比序列式容器效率更高
2.键值对
键值对是用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息
如:假设我们现在要建立一个英汉互译的字典,那么该字典中必然有英文单词与其对应的信息,而且它们是一一对应的关系,即通过单词可以找到其对应的中文
templatestruct paic{typedef T1 first_type;typedef T2 second_tyde;T1 first;T2 second;paic():first(T1()),second(T2()){}paic(const T1& a, const T2& b):first(a),frist(b){}}; 3.树形结构的关联式容器
根据应用场景不同,STL实现了两种不同结构的管理式容器,树型结构与哈希结构,树形结构的关联式容器主要有四种:map,set,multimap,multiset,这四种容器的公共特点是:使用平衡搜索树(即红黑树)作为其底层的结果,容器中的元素是一个有序的序列
4.set
4.1关于set
1.与map/multimpa中存储真正的键值对不同,set中只放value,但在底层实际存放的是构成的键值对
2.set中插入元素时,直接插入value即可,不需要构造键值对
3.set中的元素不可以重复(multi_set不同),因此可以利用set进行去重
4.使用set的迭代器遍历set的元素,可以得到有序序列
5.set中查找元素的时间复杂度为:O(logN)
6.set在底层是用二叉搜索树(红黑树)实现的
4.2set的使用
4.2.1set的构造
set (const Compare& comp = Compare(), const Allocator& = Allocator() ); //构造空的setset ( const set& x);//set的拷贝构造
4.2.2set的修改操作
pair insert ( const value_type& x )//在set中插入元素x,实际插入的是构成的键值对,如果插入成功,返回,如果插入失败,说明x在set中已经存在,返回void erase ( iterator position )//删除set中position位置上的元素void swap ( set& st );//交换set中的元素void clear ( )//将set中的元素清空iterator find ( const key_type& x ) const//返回set中值为x的元素的位置
4.2.3set的迭代器
set迭代器用法很简单,这里不在给出,后面模拟实现再详细理解底层是如何实现的
4.2.4举例代码
void Print(set& s){set::iterator it = s.begin();while (it != s.end()){cout