您现在的位置是:首页 > 正文

c++中set与map用法详解

2024-01-30 23:31:25阅读 1

关于STL

c++ STL之所以得到广泛赞誉,也被很多人使用,不只是提供了向vector,string,list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和常用的数据结构操作。vector封装了数组,list封装了链表,map和set封装了二叉树等。在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供了常用操作,如:插入,排序,删除,查找等。

1.set和map

set和map都是关联式容器,它的特点是增加或删除元素对迭代器的影响很小,除了操作的节点,其他节点都没有什么影响。
set也是用来存储同一数据类型的数据,在set中每个元素都是唯一的,而且能够根据元素的值自动进行排序。set中元素的值不能直接被改变。c++ STL中标准关联容器set,multiset,map,multimap 内部采用的就是一种非常高效的平衡二叉树:红黑树(RB树),其统计性能要好于一般的二叉树,所以被选择为了关联容器的内部结构。

1.1关于set的几个问题

  • map和set的插入删除效率要高于其他序列容器 il
    因为对于关联容器来说,不需要做内存的移动和拷贝,set容器内的所有元素都是以节点的方式来存储,其节点结构和链表差不多,指向父节点和子节点。因此插入时只需要把节点的指针指向新节点就可以了。删除的时候类似,把指向删除节点的指针指向其他节点就可以了,和内存移动没有关系。

  • 每次insert之后,以前的iterator不会失效
    iterator这里就相当于指向节点的指针,内存没有变,指向内存的指针自然不会改变,当然被删除的那个元素本身已经失效了。
    而对于vector来说,每一次删除和插入,iterator都可能会失效。因为为了保证内部数据的连续存放,iterator指向的那块内存在删除和插入过程中可能已经被其他内存覆盖或者内存已经被释放了。即使是push_back的时候,容器内部空间可能不够,需要一块新的更大的内训,只能把之前的内存释放掉,申请一个更大的内存,将已有元素复制到新的内存,最后把需要插入的元素放到最后。所以不用使用过期的iterator。

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

set中常用的方法

  • begin()
  • end()
  • clear()
  • empty()
  • max_size() 返回元素中可能包含的元素最大个数
  • size()
  • erase(iterator) 删除定位器iterator指向的值
  • erase(first, second) 删除定位器first,second之间的值
  • erase(key_value) 删除key_value的值
  • find() 返回给定值的定位器,没有找到返回end()
  • insert(key_value) 将key_value插入到set中 ,返回值 是pair<set::iterator,bool>,bool标志着插入是否成功,而iterator代表插入的位置,若key_value已经在set中,则iterator表示的key_value在set中的位置。
  • inset(first,second) 将定位器first到second之间的元素插入到set中,返回值是void.
  • lower_bound(key_value) 返回第一个大于等于key_value的定位器
  • upper_bound(key_value),返回最后一个大于等于key_value的定位器

参考:https://blog.csdn.net/yas12345678/article/details/52601454
https://www.cnblogs.com/fnlingnzb-learner/p/5833051.html

网站文章

  • JavaScript - 判断字符串中是否包含特殊字符与空格(正则表达式)

    我们在验证一个字符串是否为空或包含特殊字符时,可使用本文提供的正则表达式,省去很多校验代码。如下正则表达式,可保证字符串的合法性。

    2024-01-30 23:31:17
  • Linux signal()和kill()

    Linux signal()和kill()

    编写程序:用 fork( )创建两个子进程,再用系统调用 signal( )让父进程捕捉键盘上来的中断信号(即按^c 键);捕捉到中断信号后,父进程用系统调用 kill( )向两个子进程发出信号,子进...

    2024-01-30 23:30:47
  • 一步一步学Silverlight 2系列(32):图形图像综合实例—“功夫之王”剧照播放...

    版权声明:原创作品,允许转载,转载时请务必以超链接形式标明文章 原始出处 、作者信息和本声明。否则将追究法律责任。http://terrylee.blog.51cto.com/342737/68194 ...

    2024-01-30 23:30:40
  • 如何使用js来编写vue组件?

    如何使用js写vue组件?3分钟看懂,简单示例代码。完整代码。可复制直接进行运行

    2024-01-30 23:30:33
  • PAT 1039 Course List for Student (25 分)

    PAT 1039 Course List for Student (25 分)

    1039 Course List for Student (25 分) Zhejiang University has 40000 students and provides 2500 courses...

    2024-01-30 23:29:54
  • windows安装配置git和ToriseGit

    windows安装配置git和ToriseGit

    --------------------------安装完成,接下在是配置---------------------------------完成后,点击,下面的save public key和save...

    2024-01-30 23:29:45
  • springboot集合aciviti报错sun.reflect.annotation.TypeNotPresentExceptionProxy

    import org.activiti.spring.boot.SecurityAutoConfiguration;@SpringBootApplication(exclude = SecurityAutoConfiguration.class)

    2024-01-30 23:29:36
  • SPFA——路障Roadblocks

    将每条无向边拆成两条有向边 建图分别以1、n为原点SPFA求最短路 分别记为dis1[i]、dis2[i]枚举每一条有向边i(起点为u 终点为v 长度为w)经过该有向边i的最短路长即为 dis1[u]+w+dis2[v]求这些“最短路长”中比“真·最短路”长的最短长度

    2024-01-30 23:29:30
  • element-ui upload组件完美适配oss 解决方案

    element-ui upload组件完美适配oss 解决方案

    oss 存储方案1 oss 基础配置1 .1创建bucket1.2 创建子账户创建用户并授予编程访问权限:创建用户成功后的样式:1.3 授权完成oss所有的权限2 oss 官方文档地址2.1 官方帮助...

    2024-01-30 23:28:59
  • 解决a标签点击失效问题

    解决a标签点击失效问题

    问题描述:当鼠标移动到退出时,不发生变化且点击没有效果,在我更改样式后。 原因:a标签被其他层级覆盖了 设置a标签样式 a{ z-index: 9999; position: relative; display: inline-block; } 成功

    2024-01-30 23:28:52