当前位置:  编程技术>c/c++/嵌入式

关于STL中set容器的一些总结

    来源: 互联网  发布时间:2014-10-20

    本文导语:  1.关于set C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了...

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内部采用的就是一种非常高效的平衡检索二叉树:红黑树,也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树,所以被STL选择作为了关联容器的内部结构。

 关于set有下面几个问题:

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

大部分人说,很简单,因为对于关联容器来说,不需要做内存拷贝和内存移动。说对了,确实如此。set容器内所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。结构图可能如下:

  A
   /
  B C
 / /
  D E F G

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

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

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

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

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

2.set中常用的方法

--------------------------------------------------------------------------------

begin()        ,返回set容器的第一个元素

end()      ,返回set容器的最后一个元素

clear()          ,删除set容器中的所有的元素

empty()    ,判断set容器是否为空

max_size()   ,返回set容器可能包含的元素最大个数

size()      ,返回当前set容器中的元素个数

rbegin     ,返回的值和end()相同

rend()     ,返回的值和rbegin()相同

写一个程序练一练这几个简单操作吧:

代码如下:

#include
#include

using namespace std;

int main()
{
    set s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);
    cout


    
 
 

您可能感兴趣的文章:

  • c++ stl容器set成员函数介绍及set集合插入,遍历等用法举例
  • 请问STL中的所有容器(map,multimap,list,queue,vector,set,multiset.......)在BOOST中都可以找到么
  • c++ stl容器vector删除(erase),遍历等基本用法介绍及头文件
  • STL各个容器性能详细比较
  • c++ stl栈容器stack的pop(),push()等用法介绍及头文件
  • 过河小兵,求救各位大哥,我想把stl中的map,vector等容器,做成内存共享方式,希望大哥大姐们指点一下
  • c++ STL关联式容器Map成员函数介绍及查找(find()),插入(insert()),删除(erase())等操作代码举例
  • 浅析stl序列容器(map和set)的仿函数排序
  • 双向队列Deque 类成员函数列表参考(c++ STL 容器)
  • stl容器set,map,vector之erase用法与返回值详细解析
  • STL常用容器详细解析
  • 深入解析C++ STL中的常用容器
  • 关于STL中list容器的一些总结
  • c++ STL容器总结之:vertor与list的应用
  • 关于STL中的map容器的一些总结
  • 关于STL中vector容器的一些总结
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 我想把STL中的vector,map,set,multimap,multiset的所有操作修改成线程安全的,可以么
  • 想把STL中set放到LINUX的共享内存里, 不知道怎么办
  • C++ STL Bitsets构造函数及成员函数解释及代码示例
  • SGI的STL库 SGI STL
  • STL vector+sort排序和multiset/multimap排序比较
  • 在UNIX中可以包含STL算法吗?
  • C++ STL标准模板库类String成员详细列表参考及示例代码
  • linux完全支持C++STL嗎?
  • C++ stl队列Queue用法介绍:删除,插入等操作代码举例
  • 是不是只有C++才可以使用STL?
  • c/c++/嵌入式 iis7站长之家
  • STL 在 UNIX 多线程 中不能用?
  • c++ stl multimap基本操作使用技巧详细介绍
  • Linux系统下如何获取STL帮助
  • c++ STL List查找遍历及各成员函数用法详细介绍
  • STL实现 EASTL
  • C++ STL MultiSet类成员函数介绍及具体用法示例
  • 在COMPAQ TRUE64 UNIX用C++编程,使用Gcc,支不支持stl?
  • 哪儿能下载aix4.3的c++ stl库
  • 请问在linux下面编程怎样查询stl类的成员函数
  • 关于stl源代码
  • 请问如果要同时使用STL和多线程,会很麻烦么
  • linux下用c语言写的程序,其中可以使用STL模板吗?先谢谢各位




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3