开发者社区> 华章计算机> 正文

后台开发:核心技术与应用实践3.5.1 set是什么

简介:
+关注继续查看

3.5 set


3.5.1 set是什么


C++ STL之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector、string、list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量

常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

关于set,必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一的,而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set、multiset、map、multimap内部采用的都是红黑树。红黑树的统计性能要好于一般平衡二叉树,所以被STL选择作为了关联容器的内部结构。

关于set有下面几个问题需要注意。

(1)为何map和set的插入删除效率比用其他序列容器高?

表面上看,因为对于关联容器来说,不需要做内存拷贝和内存移动。set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点,set的结构图如图3-6所示。

因此插入的时候只需要稍做变换,把节点的指针指向新的节点就可以了。删除的时候类似,稍做变换后把指向删除节点的指针指向其他节点即可。这里的一切操作就是指针换来换去,和内存移动没有关系。

(2)为何每次insert之后,以前保存的iterator不会失效?

iterator这里就相当于指向节点的指针,内存没有变,指向内存的指针怎么会失效呢(当然被删除的那个元素本身已经失效了)。相对于vector来说,每一次删除和插入,指针都有可能失效,调用push_back在尾部插入也是如此。因为为了保证内部数据的连续存放,iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使用push_back的时候,容器内部空间可能不够,需要一块新的更大的内存,只有把以前的内存释放,并申请新的更大的内存,并复制已有的数据元素到新的内存,最后把需要插入的元素放到最后来解决,那么以前的内存指针自然就不可用了。特别是在和f?ind等算法在一起使用的时候,牢记这个原则:不要使用过期的iterator。 

(3)当数据元素增多时,set的插入和搜索速度变化如何?

如果知道log2的关系就应该彻底了解这个答案。在set中查找是使用二分查找,也就是说,如果有16个元素,最多需要比较4次就能找到结果,有32个元素,最多比较5次。那么有10?000个元素时为log10?000,即最多为14次,如果是20000个元素呢?最多不过15次。可见,当数据量增大一倍的时候,搜索次数只不过多了1次。当明白这个道理后,就可以安心往里面放入元素了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《BREW进阶与精通——3G移动增值业务的运营、定制与开发》连载之67---BREW 应用中的SVG技术
版权声明:本文为半吊子子全栈工匠(wireless_com,同公众号)原创文章,未经允许不得转载。
583 0
JavaWeb开发中Setvlet的部署以及应用
    JavaScript 和 Java  Applet  是运行在客户端浏览器中。Servlet是运行在服务器端的程序 ,他不像 JSP有有辅助工具辅助编码,所以说 Servlet的开发效率是比较低的  但是他对程序员的水平的要求要比JSP程序员的要求高很多 ,因为Servlet中涉及到很多底层的东西,一种典型的开发模式就是  MVC开发模式 利用Setvlet进行流程的控制 。
723 0
一起谈.NET技术,SharePoint开发笔记-SharePoint2010添加ASP.NET应用程序
大家可能在sharepoint开发webpart会引入一些asp.net的控件,这时候就会需要添加dll引用..下图所示CRSWebControls便是我添加的.   部署这个项目到sharepoint后.
800 0
10059
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载