学步园

搜索第一个或最后一个可能位置

lower_bound(beg,end,const T& value)

lower_bound(beg,end,const T& vlaue,op)

upper_bound(beg,end,const T& value)

upper_bound(beg,end,const T& value,op)

(1)lower_bound()返回第一个“大于等于value”的元素位置，这里可插入“元素值为value”且“不破坏区间[beg,end)已序性”的第一个位置；

(2)upper_bound()返回第一个“大于value”的元素位置，这是可插入“元素值为value”且“不破坏区间[beg,end)已序性”的最后一个位置；

(3)如果不存在“其值为value”的元素，上述所有算法都返回end；

(4)op是个可有可无的二元判断式，被当作排序准则：

op(elem1,elem2)

(5)调用者必须确保进入算法之际，所有区间都已经按照排序准则排好序了；

(6)关联式容器(set，multiset，map，multimap)分别提供等效成员函数，性能更佳；

(7)复杂度：如果搭配随机存取迭代器，则为对数复杂度，否则为线性复杂度；

代码示例：

#include"fuzhu.h"

using namespace std;

int main()
{
	list<int> coll;

	INSERT_ELEMENTS(coll,1,9);
	INSERT_ELEMENTS(coll,1,9);

	coll.sort();

	PRINT_ELEMENTS(coll);

	list<int>::iterator pos1,pos2;

	pos1=lower_bound(coll.begin(),coll.end(),5);//返回第一个大于或等于5的位置
	pos2=upper_bound(coll.begin(),coll.end(),5);//返回第一个大于5的位置

	cout<<"5 could get position "<<distance(coll.begin(),pos1)+1<<" up to "<<distance(coll.begin(),pos2)+1<<" without breaking the sorting"<<endl;

	coll.insert(lower_bound(coll.begin(),coll.end(),3),3);//先找到第一个大于等于3的位置，再插入3

	coll.insert(upper_bound(coll.begin(),coll.end(),7),7);//先找到第一个大于3=7的位置，再插入7

	PRINT_ELEMENTS(coll);

	system("pause");
	return 0;
}

搜寻第一个和最后一个可能位置

pair<ForwardIterator,ForwardIterator>
equal_range(beg,end,const T& value)

pair<ForwardIterator,ForwardIterator>
equal_range(beg,end,const T& value,op)

(1)两种形式都返回“与value相等”的元素所形成的区间。在此区间内插入“其值为value”的元素，并不会破坏区间[beg,end)的已序性；

(2)和以下等效：

make_pair(lower_bound(...),upper_bound(...))
(3)op是个可有可无的二元判断式，被当作排序准则：

op(elem1,elem2)

(4)调用者必须确保在进入算法之际，区间已经按照排序准则排好序了；

(5)关联式容器(set,multiset,map,multimap)都提供有等效的成员函数，性能更佳；

(6)复杂度：如果搭配随机存取迭代器，则为对数复杂度，否则为线性复杂度；

代码示例：

#include"fuzhu.h"

using namespace std;

int main()
{
	list<int> coll;

	INSERT_ELEMENTS(coll,1,9);

	INSERT_ELEMENTS(coll,1,9);

	coll.sort();

	PRINT_ELEMENTS(coll);

	pair<list<int>::iterator,list<int>::iterator> range;

	range=equal_range(coll.begin(),coll.end(),5);

	cout<<"5 could get position "<<distance(coll.begin(),range.first)+1<<" up to "<<distance(coll.begin(),range.second)+1<<" without breaking the sorting"<<endl;

	system("pause");
	return 0;
}