STL中的二分查找(binary_search)
STL中对于有序序列(vector,list等)提供了相当相当强大的二分搜索Binary search算法。对于可以随机访问容器(如vector等),binary search负载度为对数级别(LogN),对于非随机访问容器(如list),则算法复杂度为线性。现在简要介绍一下几种常用的binary search算法:Iterator lower_bound (Iterator first,
STL中对于有序序列(vector,list等)提供了相当相当强大的二分搜索Binary search算法。对于可以随机访问容器(如vector等),binary search负载度为对数级别(LogN),对于非随机访问容器(如list),则算法复杂度为线性。现在简要介绍一下几种常用的binary search算法:
Iterator lower_bound (Iterator first,Iterator last, const T& value)
Iterator lower_bound (Iterator first,Iterator last, const T& value, Compare comp)
//返回一个迭代器,指向键值>=value的第一个元素
Iterator upper_bound (Iterator first,Iterator last, const T& value)
Iterator upper_bound (Iterator first,Iterator last, const T& value, Compare comp)
//返回一个迭代器,指向键值>value的第一个元素(注意此处与上一个的区别).
pair equal_range(Iterator first, Iterator last, const T& value)
pair equal_range(Iterator first, Iterator last, const T& value, Compare comp)
//试图在已排序的[first,last)中寻找value,它返回一对迭代器i和j,其中i是在不破坏次序的前提下,value可插入的第一个位置(亦即lower_bound),j则是在不破坏次序的前提下,value可插入的最后一个位置(亦即upper_bound),因此,[i,j)内的每个元素都等同于value,而且[i,j)是[first,last)之中符合此一性质的最大子区间
bool binary_search (ForwardIterator first, ForwardIterator last, const T& value)
bool binary_search (ForwardIterator first, ForwardIterator last, const T& value, Compare comp)
// 查找是否在[first,last)中存在iterator i,满足 !(*i<value) && !(value<*i) or comp(*i,value)==false && comp(value,*i)==false
// 存在则返回true,否则返回false.
注:如果查找的是自定义类型,则需在定义类型的时候,重载'<'或者'>'运算符,使元素有序,或者在结构体外定义比较友元函数,在查找的时候,STL查找函数会自动调用比较函数,比较的时候只是根据定义的比较函数进行比较,如果比较函数中,只使用了结构体元素的一部分,则比较是也只是进行部分匹配,不会是结构体的完全匹配,如果要完全匹配只能是在比较函数中使用上结构体中的所有元素。
例:
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
typedef struct CInvNode{
int docId; //Doc Id
int frequecey; //Text frequency within
friend bool operator <(const CInvNode &key1,const CInvNode &key2)
{
if(key1.docId<key2.docId)return true;
else if(key1.docId<key2.docId)return false;
else return false;
}
CInvNode(){offset=NULL;}
}CInvNode;
void main()
{
CInvNode tmp;
set<CInvNode>invert_1;
tmp.docId=30;
tmp.frequecey=2;
invert_1.insert(tmp);
binary_search(invert.begin(),invert.end(),tmp);//此时会返回真值,如果将tmp.frequecey=5还是会返回真值,因为比较
//函数中没有使用到
}
更多推荐
所有评论(0)