首页 > 其他分享 >珂朵莉树总结

珂朵莉树总结

时间:2024-12-25 21:13:00浏览次数:4  
标签:总结 返回 set end 迭代 元素 iter 朵莉树

常常用于维护颜色段。随机数据下表现优秀,但构造数据随便卡。一定要看是否保证了数据随机

前置

STL之set

set内部是红黑树,内部不会出现值相同的元素。可重集使用multiset,用法基本与set一致。

插入删除

以下简写set<type>::iteratoriter

  • s.insert(x),插入值为x的元素,返回pair<iter,bool>类型,前一个是指向插入元素的指针,后一个是返回插入是否成功(set中已有等值元素时插入失败)。

  • s.erase(x),删除值为x所有元素,返回删除的元素个数。

  • s.erase(iter p),删除迭代器为p的元素,要求迭代器合法。

  • s.erase(iter l,iter r),删除迭代器在\([l,r)\)的元素。

  • s.clear(),清空s

迭代器

  • begin()/cbegin(),指向首元素的迭代器。

  • end()/cend(),指向尾端占位符的迭代器,注意此处没有元素。

  • rbegin()/crbegin(),指向逆向的首元素,可以理解为最后一个元素。

  • rend()/crend(),指向逆向的尾端占位符,对应正向首元素的前一个位置,注意此处没有元素。

以上带c的迭代器为只读类型。

查找

  • s.count(x),返回键值为x的元素个数。

  • s.find(x),返回值为x的元素的迭代器,如果不存在则返回end()

  • s.lower_bound(x),返回s中首个不小于x的元素的迭代器,如果不存在则返回end()。\(O(\log n)\),但是如果用lower_bound(s.begin(),s.end(),x)则\(O(n)\)。

  • s.upper_bound(x),返回s中首个大于x的元素的迭代器,如果不存在则返回end()。复杂度同上。

  • set没有自带的nth_element,于是只能手写平衡树或者权值线段树或者pb_ds来\(O(\log n)\)查询第\(k\)大。直接使用nth_element(s.begin(),s.end(),k)是\(O(n)\)的。

  • s.empty(),返回容器是否为空;s.size(),返回容器内元素个数。

标签:总结,返回,set,end,迭代,元素,iter,朵莉树
From: https://www.cnblogs.com/EmilyDavid/p/18631388

相关文章

  • 透视网络世界:计算机网络习题的深度解析与总结【后2章】
    ​第四章4-04试简单说明下列协议的作用:IP,ARP,RARP和ICMP。IP协议:实现网络互连。使参与互连的性能各异的网络从用户看起来好像是一个统一的网络。网际协议IP是TCP/IP体系中两个最主要的协议之一,与IP协议配套使用的还有四个协议。ARP协议:是解决同一个局域网上的主机或路由......
  • C#使用Python.NET执行Python脚本文件踩坑总结
    在VS,Nuget包管理器搜索“Python.NET”,安装pythonnet包,如下图:C#使用Python.NET执行Python脚本文件,C#代码如下:1publicclassPythonExecuter2{3privatereadonlystring_pythonDllPath;4privatereadonlystring_workDir;56publicPythonExecute......
  • 微信小程序开发总结
    业务需要,最近又搞起了微信小程序,之前从来没有参与过小程序的开发,对于开发中的流程也是知之甚少,正好学习一下,开搞...前提:使用企业注册小程序微信认证小程序备案 [本地开发]1.获取appid和secret管理>开发管理获取即可,需要管理员扫码确认这里获取到的appid在......
  • 总结24个Python接单赚钱平台与详细教程,兼职月入5000+
    如果说当下什么编程语言最靠谱或者比较适合搞副业?答案肯定100%是:Python。python是所有语法中最简单易上手的语言,不需要特别的的英语词汇量,逻辑思维也不需要很差就能上手。而且学会了之后就能编写代码爬取各种数据,制作各种图表,提升工作效率。而且还能利用业余时间接点私活,......
  • Week 15:“物品复活”软件开发总结
    软件工程课程总结:基于Tkinter的物品管理系统开发体会1.项目背景与功能概述在《软件工程》课程的学习中,我完成了一个基于Tkinter的物品管理系统的开发。该程序的主要功能包括物品的添加、编辑、删除、恢复,以及搜索管理等操作,同时提供了回收站功能以便用户可以管理已删除的物品。......
  • “物品复活”软件开发(Final) 总结文章
    在开发物品复活系统过程中,我深刻体会到软件工程中的一些关键概念和技术方法的应用。以下将从多个维度,结合软件工程的理论,回顾开发过程中的经验与收获。需求分析与功能设计在开发开始时,需求分析是整个软件工程过程中至关重要的一步。在这一步,我明确了系统的主要目标,即为用户提供......
  • 蓝桥杯-嵌入式-总结版本
    写往年嵌入式真题自己所遇到一些小细节的错误---------------------------------------------------UART----------------------------------------------------------------------当接收到中断时:stm32g4xx_it.c文件中的函数voidHardFault_Handler(void)将会调用voidHAL_UA......
  • 终于!有人总结了大模型学习资料!
    LLM基础知识前排提示,文末有大模型AGI-CSDN独家资料包哦!1.机器学习之数学基石在踏足机器学习的殿堂之前,深入理解其背后的数学原理至关重要。线性代数:它如同桥梁,连接着算法与数据世界。向量、矩阵、行列式、特征值与特征向量、向量空间及线性变换等概念,均为深度学习中......
  • vue3 - vite 对于是否生成 xxx.js.map文件的开关设置-总结
    有3个办法可以设置不生成map文件1.package.json文件里的打包语句"build:docker":"vue-tsc--noEmit&&vitebuild--modedev",中,添加--noEmit参数,则不会生成map包2.vite.config.ts文件里的build.sourcemap属性,设置为false,则不会生成map包3.tsconfig.json文件里的c......
  • MySQL NDB Cluster 日常运维命令总结
    一、数据备份物理备份:在管理节点使用ndb_mgm客户端工具启动备份:[root@管理节点mysql-cluster]#ndb_mgm--NDBCluster--ManagementClient--ndb_mgm>startbackup备份过程中,可通过ndb_mgm>showbackup;查看备份进度。备份完成后,数据文件会存储在各数......