binary_search(二分查找）
//版本一:调用operator<进行比较
template <class ForwardIterator,class StrictWeaklyCompareable>
bool binary_search(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)
{
ForwardIterator i = lower_bound(first, last, value);
return i != last && !(value < *i);
}
//版本二：调用自己定义的function object
template <class ForwardIterator,class T,class StrictWeaklyCompareable>
bool binary_search(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
若找到值==value的，返回true，否则返回false（if and only if [first,last)中存在一个iterator i，使得*i<value&&vale<*i（cmp(*i,value)和cmp(value,*i)）都不成立返回true）
对于RandomAccessIterator和其他的Iterator复杂度不同，advance对于RandomAccessIterator为常量，对于ForwardIterator为线性
lower_bound
如果[first,last]中有于value相等的元素，便返回指向第一个元素的迭代器，否则返回指向第一个不小于value的元素。如果大于区间内的所有元素则返回last
//版本一:调用operator<进行比较
template <class ForwardIterator,class StrictWeaklyCompareable>
bool lower_bound(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)
{
return __lower_bound(first, last, value,distance_type(first), iterator_category(first));
}
// forward iterator 版本
template <class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first,ForwardIterator last,const T &value,Distance*,forward_iterator_tag)
{
Distance len = ;
distance(first, last, len);
Distance half;
ForwardIterator middle;
while(len > ) {
half = len >> ;
advance(middle, half); if(*middle < value) {
first = middle;
++first;
len = len - half - ;
} else
len = half;
}
return first;
}
//random access iterator 版本
template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,RandomAccessIterator last,const T &value,Distance*,random_access_iterator_tag)
{
Distance len = last - first;
Distance half;
RandomAccessIterator middle;
while(len > )
{
half = len >> ;
middle = first + half;
if(*middle < value)
{
first = middle + ;
len = len - half - ;
} else
len = half;
}
return first;
}//版本二：调用自己定义的function object
template <class ForwardIterator,class T,class StrictWeaklyCompareable>
bool lower_bound(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
为二分查找的一种
- 若存在，返回的iterator指向第一个值为value的元素
- 若不存在，返回第一个不小于value的元素（也即是不破坏元素顺序下第一个可安插value的位置）
- 若比range中的所有元素都大，则指向end
upper_bound
返回在不破坏元素顺序的情况下可插入value的最后一个位置。
//版本一：operator<
template <class BidirectionalIterator>
bool prev_premutation(BidirectionalIterator first,BidirectionalIterator last);
//版本二：用自定义的function object
template <class BidirectionalIterator,class StrictweakOrdering>
bool prev_premutation(BidirectionalIterator first,BidirectionalIterator last,StrictweakOrdering cmo);//版本一:调用operator<进行比较
template <class ForwardIterator,class StrictWeaklyCompareable>
bool upper_bound(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)
{
return __upper_bound(first, last, value,distance_type(first), iterator_category(first));
}
// forward iterator 版本
template <class ForwardIterator, class T, class Distance>
ForwardIterator __upper_bound(ForwardIterator first,ForwardIterator last,const T &value,Distance*,forward_iterator_tag)
{
Distance len = ;
distance(first, last, len);
Distance half;
ForwardIterator middle;
while(len > )
{
half = len >> ;
advance(middle, half); if(value < *middle)
len = half;
else {
first = middle;
++first;
len = len - half - ;
}
}
return first;
}
// random access iterator 版本
template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __upper_bound(RandomAccessIterator first,RandomAccessIterator last,const T &value,Distance*,random_access_iterator_tag)
{
Distance len = last - first;
Distance half;
RandomAccessIterator middle; while(len > ) {
half = len >> ;
middle = first + half; if(value < *middle)
len = half;
else {
first = middle + ;
len = len - half - ;
}
}
return first;
}//版本二：调用自己定义的function object
template <class ForwardIterator,class T,class StrictWeaklyCompareable>
bool upper_bound(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
为二分查找的一种
- 若存在，返回最后一个元素的下一位置
- 若不再在，返回最后一个可安插value的位置
- 若比range中的所有元素都大，则指向end
equal_range
返回值是一对i，j，以pair的形式返回，i是第一个可安插value的位置，j是不破坏原来顺序下最后一个可安插的位置，[i,j)中的每个元素都与value相等，所以equal_range的返回值是[first,last)的一个子区间，若range内没有任何一个元素与value等价，返回的是个空range；不破坏原来的range下只有一个位置可安插value，pair的两个元素都指向该位置。
//版本一:由iterator i，j构成的pair，i为[fisrt,last)中最远的iterator，使得[fisrt,i)中每个iterator k都满足*k<=value
//j是[fisrt,last)最远的iterator，使得[fisrt,j)中每个iterator k都满足value<*k不为真，对于[i,j)中每个iterator k，满足value
//<*k和*k<value都不为真
template <class ForwardIterator,class StrictWeaklyCompareable>
pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last,const StrictWeaklyCompareable &value)
{
return __equal_range(first, last, value, distance_type(first),iterator_category(first));
}
// ForwardIterator 版本
template <class ForwardIterator, class T, class Distance>
pair<ForwardIterator, ForwardIterator>
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
Distance*, forward_iterator_tag) {
Distance len = ;
distance(first, last, len);
Distance half;
ForwardIterator middle, left, right;
while (len > ) { // 奇怪？ 为什么不直接用 lower_bound 、 upper_bound ， 而是等找到值再用？
// --> 我觉得是效率方面的考虑。先找 value ，这时左右两个区间可能已经缩小了许多，
// 再利用 lower_bound 和 upper_bound 代价小很多
half = len >> ;
middle = first;
advance(middle, half);
if (*middle < value) {
first = middle;
++first;
len = len - half - ;
}
else if (value < *middle)
len = half;
else {
left = lower_bound(first, middle, value);
advance(first, len);
right = upper_bound(++middle, first, value);
return pair<ForwardIterator, ForwardIterator>(left, right);
}
}
return pair<ForwardIterator, ForwardIterator>(first, first);
}
// RandomAccessIterator 版本
template <class RandomAccessIterator, class T, class Distance>
pair<RandomAccessIterator, RandomAccessIterator>
__equal_range(RandomAccessIterator first, RandomAccessIterator last,
const T& value, Distance*, random_access_iterator_tag) {
Distance len = last - first;
Distance half;
RandomAccessIterator middle, left, right; while (len > ) {
half = len >> ;
middle = first + half;
if (*middle < value) {
first = middle + ;
len = len - half - ;
}
else if (value < *middle)
len = half;
else {
left = lower_bound(first, middle, value);
right = upper_bound(++middle, first + len, value);
return pair<RandomAccessIterator, RandomAccessIterator>(left,
right);
}
}
return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}
//版本二：调用自己定义的function object
template <class ForwardIterator,class T,class StrictWeaklyCompareable>
pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,ForwardIterator last,const T& value,StrictWeaklyCompareable cmp);
