目录
lower_bound(应用于有序区间)
upper_bound（应用于有序区间）
binary_search（应用于有序区间）
next_permutation
prev_permutation
lower_bound(应用于有序区间)
这是二分查找(binary search)的一种版本，试图在已排序的[first,last)中寻找元素value。如果[first,last)具有与value相等的元素(s)，便返回一个迭代器，指向其中第一个元素。如果没有这样的元素存在，便返回“假设这样的元素存在时应该出现的位置”。也就是说，它会返回一个迭代器，指向第一个“不小于value”的元素。如果value大于[first,last)内的任何一个元素，则返回last。以稍许不同的观点来看lower_bound,其返回值是“不破坏排序状态的原则下，可插入value的第一个位置”。如下图所示
这个算法有两个版本，版本一采用operator<进行比较，版本二采用仿函数comp。更正式地说，版本一返回[first,last)中最远的迭代器i，是的[first,i)中的每个迭代器j都满足*j < value。版本二，满足上述迭代区间每个迭代器j，满足“comp(*j, value)为真”。
//版本一
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));
}
//版本二
template <class ForwardIterator, class T, class Compare>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
return __lower_bound(first, last, value, comp, 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 = 0;
distance(first, last, len);
Distance half;
ForwardIterator middle;
while(len > 0) {
half = len >> 1;
middle = first;
advance(middle, half);
if (*middle < value) {
first = middle;
++first;
len = len - half - 1;
}
else len = half;
}
return first;
}
// 版本一的random_access_iterator版本
template <class RandomAccessIterator, class T, class Distance>
ForwardIterator __lower_bound(RandomAccessIterator first, RandomAccessIterator last, const T& value, Distance*, random_access_iterator_tag) {
Distance len = 0;
distance(first, last, len);
Distance half;
RandomAccessIterator middle;
while(len > 0) {
half = len >> 1;
middle = first + half;
if (*middle < value) {
first = middle + 1;
len = len - half - 1;
}
else len = half;
}
return first;
}对于版本二的两个辅助函数，只需将*middle < value,修改成comp(*middle, value)即可，此处不在赘述。
upper_bound（应用于有序区间）
算法upper_bound是二分查找(binary search)法的一个版本。它试图在已排序的[first,last)中寻找value。更明确地说，它会返回“不在破坏顺序的情况下，可插入value的最后一个合适位置”。（lower_bound(应用于有序区间)中有图说明）
由于STL规范“区间圈定”时的起头和结尾并不对称,前开后必，所以upper_bound与lower_bound返回值意义不同。如果你查找某值，而它的确出现在区间之内，则lower_bound返回的是一个指向该元素的迭代器。而uppder_bound不这么做。因为upper_bound所返回的是在不破坏排序状态的情况下，value可被插入的“最后一个”合适位置。如果value存在，那么它返回的迭代器将指向value的下一个位置，而非指向value本身。
upper_bound有两个版本，版本一采用operator<进行比较，版本二采用仿函数comp。更正式地说，版本一返回[first,last)区间内最远的迭代i，使得[first,i)内的每个迭代器j都满足“value <*j不为真”。版本二是上述区间内的每个迭代器j都满足“comp(value, *j)不为真”。
//版本一
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));
}
//版本二
template <class ForwardIterator, class T, class Compare>
inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
return __upper_bound(first, last, value, comp, 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 = 0;
distance(first, last, len);
Distance half;
ForwardIterator middle;
while(len > 0) {
half = len >> 1;
middle = first;
advance(middle, half);
if (value < *middle)
len = half;
else {
first = middle;
++first;
len = len - half - 1;
}
}
return first;
}
// 版本一的random_access_iterator版本
template <class RandomAccessIterator, class T, class Distance>
ForwardIterator __upper_bound(RandomAccessIterator first, RandomAccessIterator last, const T& value, Distance*, random_access_iterator_tag) {
Distance len = 0;
distance(first, last, len);
Distance half;
RandomAccessIterator middle;
while(len > 0) {
half = len >> 1;
middle = first + half;
if (value < *middle)
len = half;
else {
first = middle + 1;
len = len - half - 1;
}
}
return first;
}对于版本二的两个辅助函数，只需将value < *middle,修改成comp(value, *middle)即可，此处不在赘述。
binary_search（应用于有序区间）
算法binary_search是一种二分查找法，试图在已排序的[first, last)中寻找元素value。如果[first,last)内有等同于value的元素，便返回true，否则返回false。
返回单纯的bool或许不能满足需求，前面所介绍的lower_bound,upper_bound能提供额外信息。事实上binary_search便是利用lower_bound先找出迭代器，而后对迭代器进行解引用并于value进行比较，判断值是否存在。
binary_search的第一个版本采用operator<进行比较，第二版本采用仿函数comp进行比较。
正式地说，当且仅当[first,last)中存在一个迭代器i是的*i<value和value<*i皆不为真，则第一个版本返回true。第二个版本则是上述迭代器i，满足comp(*i, value)和comp(value,*i)皆不为真，则第二版本返回true。
//版本一
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value) {
ForwardIterator I = lower_bound(first, last, value);
return I != last && !(value < *I);
}
//版本二
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);
}next_permutation
STL提供了两个用来计算排列组合关系的算法，分别是next_permutation和pre_permutation.首先我们必须了解什么是“下一个”排列组合，什么事“前一个”排列组合。考虑三个字符所组成的序列{a,b,c}。这个序列有六个可能得排列组合：abc，acb，bac，cab，cba。这些排列组合根据less-than操作符做字典顺序的排序。也就是，abc名列第一，因为每一个元素都小于其后的元素。acb是次一个排列组合，因为它是固定了a（序列内最小元素）之后所做的新组合。同样的道理，那些固定b而做的排列组合，在次序上将先于那些固定c而做的排列组合。以bac和bca为例。bac在bca之前，因为序列ac小于ca。面对bca，我们可以说前一个排列组合是bac。而其后一个排列组合是cab。序列abc没有前一个排列组合，cba没有后一个排列组合。
next_permutation()会取得[first,last)所标示之序列的下一个排列组合。如果没哟下一个排列组合，便返回false；否则返回true。
这个算法有两个版本。版本一使用元素型别所提供的less-than操作符来决定下一个排列组合，版本二则是以仿函数comp来决定。
稍后将出现的实现，简述如下，符号如下图所示：
首先，从尾端往前寻找两个相邻的元素，令第一个元素为*i，第二个元素为*ii,且满足*i<*ii.找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个大于*i的元素，令为*j，将i，j元素对调，再将II之后的所有元素颠倒排序。此即所求值下一个排列组合。
举个实例，假设手上有序列{0,1,2,3,4}，下图便是套用上述演算法则，一步一步获得“下一个”排列组合。图中只框出那符合“第一元素为I，第二元素为*ii，且满足*i<*ii”的相邻元素。
以下便是版本一的实现细节。
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator I = first;
++I;
if (I = last) return false;
I = last;
--I;
for (;;) {
BidirectionalIterator II = I;
--I;
if (*I < *II) {
BidirectionalIterator J = last;
while(!(*I < *--J);
iter_swap(I,J);
reverse(II, last);
return true;
}
if (I == first) { // 进行到了最前面都未找到符合条件的元素
reverse(first, last); // 全部重排，重新再来一遍?
return false;
}
}
}版本二只是将operator<用comp替换，此处不在罗列代码。
prev_permutation
所谓“前一个”排列组合，其意义已在上一节阐述。实际做法简述如下，从最尾端开始往前寻找两个相邻元素，令第一个元素为*i，第二个元素为*ii，且满足*i>*ii.找到这样一组相邻元素后，再从尾端开始往前检验，找到第一个小于*i的元素，令为*j，将i，j元素对调，再将ii之后的所有元素颠倒排序。此即前一个排列组合。
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator I = first;
++I;
if (I = last) return false;
I = last;
--I;
for (;;) {
BidirectionalIterator II = I;
--I;
if (*II < *I) {
BidirectionalIterator J = last;
while(!(*--J < *I );
iter_swap(I, J);
reverse(II, last);
return true;
}
if (I == first) { // 进行到了最前面都未找到符合条件的元素
reverse(first, last); // 全部重排，重新再来一遍?
return false;
}
}
}代码如下：版本二只是将operator<用comp替换，此处不在罗列代码。
参考文档《STL源码剖析》---侯捷
