首页 > 其他分享 >STL-set

STL-set

时间:2024-10-07 15:34:08浏览次数:7  
标签:set 指向 迭代 STL 复杂度 元素 集合

STL set

头文件set主要包括set和multiset两个容器,分别是“有序集合”和“有序多重集合”

即前者的元素不能重复,而后者可以包含若干个相等的元素

set和multiset的内部实现是一棵红黑树,它们支持的函数基本相同

include声明
#include <set>
函数声明
set<int> s;

struct rec{…}; set<rec> s;	// 结构体rec中必须定义小于号

multiset<double> s;

/////

size/empty/clear

与vector类似

size()
empty()
clear()

/////

迭代器

set和multiset的迭代器称为“双向访问迭代器”,不支持“随机访问”,支持星号(*)解除引用,仅支持”++”和--“两个与算术相关的操作

设it是一个迭代器,例如

set<int>::iterator it;

若把it++,则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中,排在it下一名的元素

同理,若把it--,则it将会指向排在“上一个”的元素

/////

begin/end

返回集合的首、尾迭代器,时间复杂度均为O(1)。

begin() 
end() 

s.begin() 是指向s集合中最小元素的迭代器。

s.end() 是指向s集合中最大元素的下一个位置的迭代器

换言之,就像vector一样,因此s.end()是指向集合中最大元素的迭代器

/////

insert

insert()

s.insert(x)把一个元素x插入到集合s中,时间复杂度为O(logn)

在set中,若元素已存在,则不会重复插入该元素,对集合的状态无影响

/////

find

find()

s.find(x) 在集合s中查找等于x的元素,并返回指向该元素的迭代器

若不存在,则返回s.end()

时间复杂度为O(logn)

/////

lower_bound/upper_bound

lower_bound()
upper_bound()

这两个函数的用法与find类似,但查找的条件略有不同,时间复杂度为 O(logn)

s.lower_bound(x) 查找大于等于x的元素中最小的一个,并返回指向该元素的迭代器

s.upper_bound(x) 查找大于x的元素中最小的一个,并返回指向该元素的迭代器。

/////

erase

erase()

设it是一个迭代器,s.erase(it) 从s中删除迭代器it指向的元素,时间复杂度为O(logn)

设x是一个元素,s.erase(x) 从s中删除所有等于x的元素,时间复杂度为O(k+logn),其中k是被删除的元素个数

/////

count

count()

s.count(x) 返回集合s中等于x的元素个数,时间复杂度为 O(k +logn),其中k为元素x的个数

标签:set,指向,迭代,STL,复杂度,元素,集合
From: https://www.cnblogs.com/dianman/p/18450155

相关文章

  • STL-queue&deque&stack
    STLqueue&deque&stackqueue主要包括循环队列queue和优先队列priority_queue两个容器stack包含栈容器include头文件声明#include<queue>#include<deque>#include<stack>声明queue<int>q;deque<int>p;structabc{…};queue<abc>q; //结构体r......
  • ​解密 Go runtime.SetFinalizer 的使用
    解密Goruntime.SetFinalizer的使用原创 GoOfficialBlog GoOfficialBlog  2024年10月05日18:45 中国香港 听全文如果我们想在对象GC之前释放一些资源,可以使用returns.SetFinalizer。这就像在函数返回前执行 defer 来释放资源一样。例如:1:使用runtime.......
  • STL-vector
    STLvectorvector是动态数组,支持随机访问,不支持在任意位置O(1)插入为,元素的增删一般在末尾进行include头文件声明vectora;相当于声明一个长度动态变化的int数组vectorb[233];相当于声明一个第一维长233,第二维长度动态变化的int数组structabc{...};vectorc;自定......
  • STL-queue&stack
    STLqueue&stackqueue主要包括循环队列queue和优先队列priority_queue两个容器stack包含栈容器include头文件声明#include<queue>#include<stack>声明queue<int>q;structabc{…};queue<abc>q; //结构体rec中必须定义小于号priority_queue<int>q; //大根......
  • STL
    vector是动态数组,支持随机访问,不支持在任意位置O(1)插入为,元素的增删一般在末尾进行include头文件声明vectora;相当于声明一个长度动态变化的int数组vectorb[233];相当于声明一个第一维长233,第二维长度动态变化的int数组structabc{...};vectorc;自定义的结构体类......
  • ES6中扩展运算符...与Set结合使用
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>Document</title><......
  • [论文阅读报告] All pairs shortest paths using bridging sets and rectangular matr
    本篇文章介绍整数边权下\((\min,+)\)矩阵乘、APSP等问题的一些做法。若每个元素的权值在\([-M,M]\cap\mathbbZ\)中,\(n\timesn^r\)和\(n^r\timesn\)的\((\min,+)\)矩阵乘可做到\(\tildeO(Mn^{\omega(r)})\);有向图APSP可做到\(\tildeO(n^{2+\mu(t)})\),......
  • STL <vector>
    vector是动态数组,支持随机访问,不支持在任意位置O(1)插入为,元素的增删一般在末尾进行include 头文件声明vectora; 相当于声明一个长度动态变化的int数组vectorb[233]; 相当于声明一个第一维长233,第二维长度动态变化的int数组structabc{...};vectorc; 自定义的结构体......
  • netsh winsock reset catalog 和 netsh int ip reset reset.log 是两个常用的 Windows
    netshwinsockresetcatalog和netshintipresetreset.log是两个常用的Windows命令,用于网络故障排除和恢复网络设置。下面是对这两个命令的详细解释:1. netshwinsockresetcatalog功能:重置Winsock目录,以修复与网络相关的问题。Winsock的作用:Winsock(WindowsSocke......
  • [lnsyoj2378/luoguAT_arc107_d]Number of Multisets
    题意给出两个正整数\(N,K\),求有多少有理数集满足以下所有条件集合有且只有\(N\)个元素,并且元素和为\(K\);每个元素须可表示为\( \frac{1}{2^{i}}\) $(i\inN)$.sol考虑dp,容易想到记\(f_{i,j}\)表示选\(i\)个数恰好和为\(j\)考虑到会出现诸如\(\dfrac{1}......