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,里边有一个greater()函数即可对逆序求最近位置。假如说像上边一样元素为2 4 6 8,逆序则是8 6 4 2,那么求距离3最近表示的是与3最近的小于等于3的元素,输出结果则是元素2了,代码如下:

#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 协议 ,转载请注明出处!