SGISTL源码探究-stl_alog.h中的二分查找算法
方光华
前言
在上一小节中我们分析了stl_algo.h中的部分算法。本小节中我们将继续分析其中关于二分查找类的算法,即lower_bound、upper_bound、binary_search、equal_range。这些算法相比于上一节的要稍微复杂些,如果你对二分法比较了解,这一小节应该也很轻松。
STL中的二分查找算法
lower_bound
使用该函数的前提是传入的区间必须有序,这也是二分法的唯一要求。lower_bound的作用是在[first, last)中寻找第一个大于或者等于value值的元素,然后返回指向该元素的迭代器;也可以理解为在不破坏排序的前提下,寻找value可以插入的点(如果没有则返回last),比如{1, 3, 5, 5, 7, 9},value = 4,那么返回的迭代器应该指向第一个值为5的元素。
在它的源码实现中,同样有两个不同的版本,其中一个版本是使用<操作符进行比较,另一种是传入仿函数comp进行比较,这里我们只分析版本一,另外一个版本与其十分类似。
首先从大体上来看,lower_bound调用了__lower_bound,而__lower_bound有两个不同的版本,其中一个针对迭代器类型为ForwardIterator,另一个针对RandomAccessIterator类型的。这样的区分已经很常见了。
下面让我们来看看它的源码是如何实现的:
//迭代器类型为ForwardIterator版
template <class ForwardIterator, class T, class Distance>
ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
const T& value, Distance*,
forward_iterator_tag) {
//len表示区间的长度
Distance len = 0;
distance(first, last, len);
//half表示中间位置
Distance half;
ForwardIterator middle;
while (len > 0) {
half = len >> 1;
//让middle指向中间位置
middle = first;
advance(middle, half);
/* 若中间位置的元素的值小于value
* 证明大于或者等于value的元素在另外一半区间
* 将first指向中间位置的下一个元素
* 更新len,重进循环判断
* 否则证明大于或等于value的元素就在本区间内
* 更新len,重进循环判断
*/
if (*middle < value) {
first = middle;
++first;
len = len - half - 1;
}
else
len = half;
}
return first;
}
//RandomAccessIterator版
template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __lower_bound(RandomAccessIterator first,
RandomAccessIterator last, const T& value,
Distance*, random_access_iterator_tag) {
//计算len的长度,RandomAccessIterator才支持last - first这种写法
Distance len = last - first;
Distance half;
RandomAccessIterator middle;
while (len > 0) {
//计算half
half = len >> 1;
//将middle指向中间位置,RandomAccessIterator才支持first + half这种写法
middle = first + half;
if (*middle < value) {
//同样的,RandomAccessIterator才支持这样
//不然就只能写成first = middle;++first;这样了
first = middle + 1;
len = len - half - 1;
}
else
len = half;
}
return first;
}
//调用__lower_bound,使用distance_type以及iterator_category获取到迭代器的相关类型
template <class ForwardIterator, class T>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
const T& value) {
return __lower_bound(first, last, value, distance_type(first),
iterator_category(first));
}upper_bound
该函数也同样要求区间有序,它的作用是在不破坏有序的前提下,寻找可插入value的最后一个合适的位置。
即假如区间中有value的值,它会返回指向所有值为value的最后一个元素的下一个位置;假如区间中没有value,这个和lower_bound一样,返回指向第一个大于value的元素的位置。
它的实现同样也有两个版本,一个是根据<操作符进行比较,另一个是根据传入的comp进行比较。在lower_bound中,我们是分析的版本一,为了对称比较,这里我们也只分析版本一。
下面是它的源码实现:
//ForwardIterator版
template <class ForwardIterator, class T, class Distance>
ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
const T& value, Distance*,
forward_iterator_tag) {
//这部分是完全相同的
Distance len = 0;
distance(first, last, len);
Distance half;
ForwardIterator middle;
while (len > 0) {
half = len >> 1;
//将middle指向中间位置
middle = first;
advance(middle, half);
/* 如果中间位置的元素值大于value
* 证明要找的元素就在本区间内了,更新len
* 否则证明要找的元素在另外一个区间
* 将first指向middle的下一个元素,更新len
*/
if (value < *middle)
len = half;
else {
first = middle;
++first;
len = len - half - 1;
}
}
return first;
}
//RandomAccessIterator版
template <class RandomAccessIterator, class T, class Distance>
RandomAccessIterator __upper_bound(RandomAccessIterator first,
RandomAccessIterator last, const T& value,
Distance*, random_access_iterator_tag) {
//仅RandomAccessIterator支持last - first
Distance len = last - first;
Distance half;
RandomAccessIterator middle;
//以下实现逻辑与ForwardIterator版相同
//只是操作更简单,效率更高
while (len > 0) {
half = len >> 1;
middle = first + half;
if (value < *middle)
len = half;
else {
first = middle + 1;
len = len - half - 1;
}
}
return first;
}
template <class ForwardIterator, class T>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
const T& value) {
return __upper_bound(first, last, value, distance_type(first),
iterator_category(first));
}binary_search
该函数的作用即在有序的区间[first, last)中寻找值为value的元素,若有则返回true,否则返回false
它通过内部调用lower_bound实现,并且对应lower_bound,也有两个版本,版本二使用仿函数comp进行比较,而不是通过<操作符。至于为什么不用upper_bound,这是因为就算区间中有等于value的元素,upper_bound返回的迭代器也是最后一个值为value的元素的下一个位置,不满足要求。
源码实现如下:
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value) {
//调用lower_bound,取得指向等于或者第一个大于value的元素的迭代器
ForwardIterator i = lower_bound(first, last, value);
//由于不一定是等于value的元素,所以需要比较判断一下
//如果等于last,证明没有找到符合条件的元素,或者当*i>value代表也没有值为value的元素,都返回false
return i != last && !(value < *i);
}
//使用仿函数comp的版本
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
Compare comp) {
ForwardIterator i = lower_bound(first, last, value, comp);
return i != last && !comp(value, *i);
}equal_range
该函数依然要求区间有序,作用是在[first, last)中寻找value,并返回一对迭代器left,right,left指向在不破坏有序的条件下,value可以插入的第一个位置;right指向在不破坏有序的条件下,value可以插入的最后一个位置。
因此,在[first, last)区间内,[left, right)的区间的元素都等于value。它的实现首先也分两个版本,另一个是使用仿函数comp进行比较,我们不作考虑。在版本一的实现中,根据迭代器类型的不同也有不同的实现。
源码如下:
//ForwardIterator版
template <class ForwardIterator, class T, class Distance>
pair<ForwardIterator, ForwardIterator>
__equal_range(ForwardIterator first, ForwardIterator last, const T& value,
Distance*, forward_iterator_tag) {
//len表示区间总长度
Distance len = 0;
distance(first, last, len);
Distance half;
ForwardIterator middle, left, right;
while (len > 0) {
half = len >> 1;
//middle指向中间位置
middle = first;
advance(middle, half);
//若中间值小于value,证明value可能存在于另外一半区间
if (*middle < value) {
first = middle;
++first;
len = len - half - 1;
}
//若中间值大于value,证明value可能存在本区间内
else if (value < *middle)
len = half;
/* value == *middle
* 调用lower_bound找到value第一次出现的位置
* 调用upper_bound找到value最后一次出现的下一个位置
* 然后构建pair并返回
*/
else {
/* middle将区间分成两半,第一半的最大值不会大于middle
* 由于我们要寻找value第一次出现的位置,所以应该在第一半区间寻找
* 于是lower_bound寻找的区间是[first, middler)
* 关于寻找value最后一次出现的下一个位置
* 很明显该从剩下的那一半区间寻找
* 所以upper_bound寻找的区间是[++middle, last)
*/
left = lower_bound(first, middle, value);
//将first指向last
advance(first, len);
right = upper_bound(++middle, first, value);
return pair<ForwardIterator, ForwardIterator>(left, right);
}
}
//整个区间内没有值为value的元素,则返回一对迭代器,指向第一个大于value的元素(因为first更新时指向大于value的另外一半区间的首个元素)
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 > 0) {
half = len >> 1;
//RandomAccessIterator独有的操作
middle = first + half;
if (*middle < value) {
//RandomAccessIterator独有的操作
first = middle + 1;
len = len - half - 1;
}
else if (value < *middle)
len = half;
else {
left = lower_bound(first, middle, value);
//RandomAccessIterator独有的操作
right = upper_bound(++middle, first + len, value);
return pair<RandomAccessIterator, RandomAccessIterator>(left,
right);
}
}
return pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}
//根据iterator_category的结果调用合适的__equal_range函数
template <class ForwardIterator, class T>
inline pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
return __equal_range(first, last, value, distance_type(first),
iterator_category(first));
}小结
关于二分查找部分的算法到此为止,在下一小节中我们将分析stl_algo.h中的排列算法部分。
类似资料：