初探stl

发布于 2022-09-14  254 次阅读


碎碎念

一些在csp赛前的临死反扑

主要是因为在做上一次的csp真题时,发现T4的题解很少

仅有的题解还是写的pair二分,不是我能写出来的东西呜呜呜

于是自己总结了一下怎么在set上二分

update

又做了上上一次的真题,这次没看T4题解,但是用了百度

上一道T4是map里套set再二分

这一次T4是map里套set然后取map的尾set的头

总结了一下一些《高端》的指针操作

set二分

set

set.begin()指向第一个元素,set.end()指向最后一个元素

但是在c++中,几乎所有的操作都是含头不含尾的

所以set.end()指向的最后一个元素实际上是一个不存在的元素

可以理解为某种意义上的空指针

二分

set.lower_bound()返回第一个大于等于某个数的指针

set.upper_bound()返回第一个大于某个数的指针

相同点是如果没找到就返回end

二分时分为如下四种情况:

如果我们想找大于一个数的数,直接用upper_bound判断返回指针是否为end即可

如果我们想找大于等于一个数的数,直接用lower_bound判断返回指针是否为end即可

如果我们想找小于一个数的数,用lower_bound判断返回指针是否为begin,然后指针-1

如果我们想找小于等于一个数的数,用upper_bound判断返回指针是否为begin,然后指针-1

map

如果想取一个map的尾

auto it=mp.end();it--;

此时的it是一个指向map最后一个元素的指针

*it是一个pair类型的变量,first储存key值,second储存value

*it.first的一种等价写法是it->first