cellular automata
STL函数,内部用二分查找实现
有关lower_bound()函数的使用
lower_bound()函数需要加载头文件#include
函数原型:
template<class ForwardIterator, class Type>
ForwardIterator lower_bound(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val
);
template<class ForwardIterator, class Type, class BinaryPredicate>
ForwardIterator lower_bound(
ForwardIterator _First,
ForwardIterator _Last,
const Type& _Val,
BinaryPredicate _Comp
);传入参数说明:
_First 要查找区间的起始位置
_Last 要查找区间的结束位置
_Val 给定用来查找的值
_Comp 自定义的表示小于关系的函数对象,根据某个元素是否满足小于关系而返回true或者false
函数介绍
例如,有如下序列:
$a[i]={12,15,17,19,20,22,23,26,29,35,40,51}$;
用值21调用lower_bound(),返回一个指向22的iterator。用值22调用lower_bound(),也返回一个指向22的iterator。第一个版本使用底层 < (小于)操作符,第二个版本根据comp进行排序和比较。
lower_bound(k)返回一个迭代器,指向键不小于k的第一个元素
upper_bound(k)返回一个迭代器,指向键大于k的第一个元素
注意事项
调用lower_bound之前必须确定序列为有序序列,否则调用出错。第一个版本排序根据底层的 <(小于)操作符,第二个版本根据comp进行排序。
举例说明
#include <bits/sdtc++.h>
using namespace std;
vector<int> v;
int main()
{
for (int i = 1; i < 4; i++)
v.push_back(2 * i);//注意此时v中的元素本身就是有序的
vector<int>::iterator it = lower_bound(v.begin(), v.end(), 3);
cout << *it << endl;
return 0;
}
上面的例子是针对容器的,注意返回的是距离元素3最近的指针it,输出的是*it结果为元素4,假如我想得到位置而非具体的元素应该怎么办呢?这里有一个指针偏移的技巧,只需要减去起始位置的指针即可,代码如下:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v;
int main()
{
for (int i = 1; i < 4; i++)
v.push_back(2 * i);//注意此时v中的元素本身就是有序的
//vector<int>::iterator it = lower_bound(v.begin(), v.end(), 3);
int pos = lower_bound(v.begin(), v.end(), 3)-v.begin();
cout << pos<< endl;
return 0;
}
结果和容器的时候是一样的。
对于4个参数的情形,最后一个参数的自己定义的表示大小关系函数的对象,常用的逆序可以加载头文件#include
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
vector<int> v;
int main()
{
for (int i = 4; i >0; i--)
v.push_back(2 * i);//注意此时v中的元素本身就是有序的
vector<int>::iterator it = lower_bound(v.begin(), v.end(), 3,greater<int>());
cout << *it << endl;
return 0;
}
补充
我们知道map容器是根据键值进行排序的
lower_bound(k)返回一个迭代器,指向键不小于k的第一个元素
upper_bound(k)返回一个迭代器,指向键大于k的第一个元素
这两个函数常用于multimap容器,用来获取某个键对应的所有元素
#include <bits/stdc++.h>
using namespace std;
int main()
{
multimap<string,int> m;
m.insert(make_pair((string)"China",1));
m.insert(make_pair((string)"China",2));
m.insert(make_pair((string)"China",3));
m.insert(make_pair((string)"English",1));
m.insert(make_pair((string)"English",2));
multimap<string,int>::iterator it = m.begin();
while(it != m.end())
{
cout<<it->first<<" "<<it->second<<endl;
it++;
}
cout<<endl;
multimap<string,int>::iterator it1 = m.lower_bound("China"),it2 = m.upper_bound("China");
cout<<it1->first<<" "<<it1->second<<endl;
cout<<it2->first<<" "<<it2->second<<endl;
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!