高端大气的网站首页,烟台产品网站建设,大学生求职简历模板免费下载,微信手机网页登录入口1.lower_bound( )和upper_bound( )
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的
在从小到大的排序数组中#xff0c;
lower_bound( begin,end,num)#xff1a;从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字
lower_bound( begin,end,num)从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字找到返回该数字的地址不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)从数组的begin位置到end-1位置二分查找第一个大于num的数字找到返回该数字的地址不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小的排序数组中重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greatertype() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字找到返回该数字的地址不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num,greatertype() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字找到返回该数字的地址不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。greaterint()表示内置类型从大到小排序lessint()则是从小到大。
#includebits/stdc.h
using namespace std;
const int maxn10000010;
const int INF2*int(1e9)10;
#define LL long long
int cmd(int a,int b){return ab;
}
int main(){int num[6]{1,2,4,7,15,34}; sort(num,num6); //按从小到大排序 int pos1lower_bound(num,num6,7)-num; //返回数组中第一个大于或等于被查数的值 int pos2upper_bound(num,num6,7)-num; //返回数组中第一个大于被查数的值coutpos1 num[pos1]endl;coutpos2 num[pos2]endl;sort(num,num6,cmd); //按从大到小排序int pos3lower_bound(num,num6,7,greaterint())-num; //返回数组中第一个小于或等于被查数的值 int pos4upper_bound(num,num6,7,greaterint())-num; //返回数组中第一个小于被查数的值 coutpos3 num[pos3]endl;coutpos4 num[pos4]endl;return 0;
}
2.优先队列(priority_queue)
top 访问队头元素empty 队列是否为空size 返回队列内元素个数push 插入元素到队尾 (并排序)emplace 原地构造一个元素并插入队列pop 弹出队头元素swap 交换内容
1定义priority_queueType, Container, Functional Type 就是数据类型Container 就是容器类型Container必须是用数组实现的容器比如vector,deque等等但不能用 list。STL里面默认用的是vectorFunctional 就是比较的方式当需要用自定义的数据类型时才需要传入这三个参数使用基本数据类型时只需要传入数据类型默认是大顶堆 一般是
#includeiostream
#include queue
using namespace std;
int main()
{//对于基础类型 默认是大顶堆priority_queueint a; //等同于 priority_queueint, vectorint, lessint a;// 这里一定要有空格不然成了右移运算符↓priority_queueint, vectorint, greaterint c; //这样就是小顶堆priority_queuestring b;for (int i 0; i 5; i) {a.push(i);c.push(i);}while (!a.empty()) {cout a.top() ;a.pop();} cout endl;while (!c.empty()) {cout c.top() ;c.pop();}cout endl;b.push(abc);b.push(abcd);b.push(cbd);while (!b.empty()) {cout b.top() ;b.pop();} cout endl;return 0;
}注从小到大排序是大顶堆从大到小排序是小顶堆而.top()取的是堆顶。
2对于自定义类型
#include iostream
#include queue
using namespace std;//方法1
struct tmp1 //运算符重载
{int x;tmp1(int a) {x a;}bool operator(const tmp1 a) const{return x a.x; //大顶堆}
};//方法2
struct tmp2 //重写仿函数
{bool operator() (tmp1 a, tmp1 b) {return a.x b.x; //大顶堆}
};int main()
{tmp1 a(1);tmp1 b(2);tmp1 c(3);priority_queuetmp1 d;d.push(b);d.push(c);d.push(a);while (!d.empty()) {cout d.top().x \n;d.pop();}cout endl;priority_queuetmp1, vectortmp1, tmp2 f;f.push(c);f.push(b);f.push(a);while (!f.empty()) {cout f.top().x \n;f.pop();}
}转自https://blog.csdn.net/weixin_36888577/article/details/79937886
