华亭县门户网站,艾瑞网的网站架构,关于我的大学的网站建设模板,外包网络安全技术措施这是关于一个普通双非本科大一学生的C的学习记录贴
在此前#xff0c;我学了一点点C语言还有简单的数据结构#xff0c;如果有小伙伴想和我一起学习的#xff0c;可以私信我交流分享学习资料
那么开启正题
今天分享的是关于set和map的知识点
1.关联式容器
在前面#…这是关于一个普通双非本科大一学生的C的学习记录贴
在此前我学了一点点C语言还有简单的数据结构如果有小伙伴想和我一起学习的可以私信我交流分享学习资料
那么开启正题
今天分享的是关于set和map的知识点
1.关联式容器
在前面我们已经学习了STL的部分容器如vectorlistdeque这些容器被称为序列式容器因为底层是线性序列的数据结构里面存储的是元素本身那么什么是关联式容器呢
关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key value结构的键值对在数据检索时比序列式容器效率更高
2.键值对
键值对是用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息
如假设我们现在要建立一个英汉互译的字典那么该字典中必然有英文单词与其对应的信息而且它们是一一对应的关系即通过单词可以找到其对应的中文
templateclass T1, class T2
struct 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实现了两种不同结构的管理式容器树型结构与哈希结构树形结构的关联式容器主要有四种mapsetmultimapmultiset这四种容器的公共特点是使用平衡搜索树即红黑树作为其底层的结果容器中的元素是一个有序的序列
4.set
4.1关于set
1.与map/multimpa中存储真正的键值对keyvalue不同set中只放value但在底层实际存放的是valuevalue构成的键值对
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() );
//构造空的set
set ( const setKey,Compare,Allocator x);
//set的拷贝构造
4.2.2set的修改操作
pairiterator,bool insert (
const value_type x )
//在set中插入元素x实际插入的是x, x构成的
键值对如果插入成功返回该元素在set中的
位置true,如果插入失败说明x在set中已经
存在返回x在set中的位置falsevoid erase ( iterator position )
//删除set中position位置上的元素void swap (
setKey,Compare,Allocator
st );
//交换set中的元素void clear ( )
//将set中的元素清空iterator find ( const
key_type x ) const
//返回set中值为x的元素的位置
4.2.3set的迭代器
set迭代器用法很简单这里不在给出后面模拟实现再详细理解底层是如何实现的
4.2.4举例代码
void Print(setint s)
{setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;
}void Test_set1()
{setint s;s.insert(1);s.insert(9);s.insert(3);s.insert(1);s.insert(1);Print(s);s.erase(1);Print(s);setint::iterator pos s.find(5);s.erase(5);pos find(s.begin(), s.end(), 5);if (pos ! s.end()){s.erase(pos);}
}
5.map
5.1关于map
1.在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的 内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型 value_type绑定在一起为其取别名称为pair
2.在内部map中的元素总是按照键值key进行比较排序的
3.map支持下标访问符即在[]中放入key就可以找到与key对应的value
4.map通常被实现为二叉搜索树红黑树
5.2的使用
5.2.1map的构造
map() //构造一个空的map5.2.2map的容量与元素访问
bool empty ( ) const
//检测map中的元素是否为空是返回
//true否则返回falsesize_type size() const
//返回map中有效元素的个数mapped_type operator[] (const
key_type k)
//返回去key对应的value5.2.3map的修改操作
pairiterator,bool insert (
const value_type x )
//在map中插入键值对x注意x是一个键值
对返回值也是键值对iterator代表新插入
元素的位置bool代表释放插入成功void erase ( iterator position )
//删除position位置上的元素size_type erase ( const
key_type x )
//删除键值为x的元素void erase ( iterator first,
iterator last )
//删除[first, last)区间中的元素void swap (
mapKey,T,Compare,Allocator
mp )
//交换两个map中的元素void clear ( )
//将map中的元素清空iterator find ( const key_type x
)
//在map中插入key为x的元素找到返回该元
素的位置的迭代器否则返回end
5.2.4map的迭代器
map迭代器用法很简单这里不在给出后面模拟实现再详细理解底层是如何实现的
5.2.5举例代码
void Test_map1()
{mapstring, int m;m.insert(make_pair(苹果, 1));m.insert(make_pair(香蕉, 3));m.insert(make_pair(桃子, 5));m.insert(make_pair(樱桃, 4));mapstring, int::iterator it m.begin();while (it ! m.end()){cout it-first : it-second endl;it;}cout endl;
}
新手写博客有不对的位置希望大佬们能够指出也谢谢大家能看到这里让我们一起学习进步吧
