STLalgorithm算法lower_bound和upper_bound(31)
lower_bound原型:
function template
std::lower_bound
default (1)
template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2)
template <class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
该函数返回范围内第一个不小于(大于或等于)指定val的值。
如果序列中的值都小于val,则返回last.
序列应该已经有序!
使用operator<来比较两个元素的大小。
该函数优化了比较非连续存储序列的比较次数。
其行为类似于:
1 | template <class ForwardIterator, class T> |
一个简单的例子:
#include
#include
#include
using namespace std;
int main(int argv,char **argc)
{
vector
cout<<”v1=”;
for(int i:v1)
cout<<i<<” “;
cout<<endl;
auto it=lower_bound(v1.begin(),v1.end(),3);
cout<<”lower_bound(v1.begin(),v1.end(),3)=”<<*it<<endl;
auto it2=lower_bound(v1.begin(),v1.end(),5);
if(it2==v1.end())
cout<<”lower_bound(v1.begin(),v1.end(),5)=v1.end()”<<endl;
else
cout<<”lower_bound(v1.begin(),v1.end(),5)=”<<*it2<<endl;
}
运行截图:
upper_bound原型:
function template
std::upper_bound
default (1)
template <class ForwardIterator, class T>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val);
custom (2)
template <class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
该函数返回范围内第一个大于指定val的值。
如果序列中的值都小于val,则返回last.
序列应该已经有序!
使用operator<来比较两个元素的大小。
该函数优化了比较非连续存储序列的比较次数。
其行为类似于:
1 | template <class ForwardIterator, class T> |
一个简单的例子:
// lower_bound/upper_bound example
#include
#include
#include
int main () {
int myints[] = {10,20,30,30,20,10,10,20};
std::vector
std::sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
std::vector
low=std::lower_bound (v.begin(), v.end(), 20); // ^
up= std::upper_bound (v.begin(), v.end(), 20); // ^
std::cout << “lower_bound at position “ << (low- v.begin()) << ‘\n’;
std::cout << “upper_bound at position “ << (up - v.begin()) << ‘\n’;
return 0;
}
运行结果:
lower_bound和upper_bound返回的值刚好是equal_range对应的两个值!
——————————————————————————————————————————————————————————————————
//写的错误或者不好的地方请多多指导,可以在下面留言或者点击左上方邮件地址给我发邮件,指出我的错误以及不足,以便我修改,更好的分享给大家,谢谢。
转载请注明出处:http://blog.csdn.net/qq844352155
author:天下无双
Email:coderguang@gmail.com
2014-9-17
于GDUT
——————————————————————————————————————————————————————————————————
- 本文作者: royalchen
- 本文链接: http://www.royalchen.com/2016/02/24/stlalgorithm算法lower-bound和upper-bound31/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!