类别: 算法 | 组件类型: 函数 |
template <class ForwardIterator, class LessThanComparable> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const LessThanComparable& value); template <class ForwardIterator, class T, class StrictWeakOrdering> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);
iupper_bound在中,使得对于每个迭代器j[first, last)[first, i)value < *jj是, false第二个版本的comp(value, *j).
定义upper_bound在中,使得对于每个迭代器j[first, last)[first, i)value < *jj是, 在标准头文件 algorithm 和非标准向后兼容头文件 algo.h 中定义。第二个版本的comp(value, *j).
int main() { int A[] = { 1, 2, 3, 3, 3, 5, 8 }; const int N = sizeof(A) / sizeof(int); for (int i = 1; i <= 10; ++i) { int* p = upper_bound(A, A + N, i); cout << "Searching for " << i << ". "; cout << "Result: index = " << p - A << ", "; if (p != A + N) cout << "A[" << p - A << "] == " << *p << endl; else cout << "which is off-the-end." << endl; } }成正比。
Searching for 1. Result: index = 1, A[1] == 2 Searching for 2. Result: index = 2, A[2] == 3 Searching for 3. Result: index = 5, A[5] == 5 Searching for 4. Result: index = 5, A[5] == 5 Searching for 5. Result: index = 6, A[6] == 8 Searching for 6. Result: index = 6, A[6] == 8 Searching for 7. Result: index = 6, A[6] == 8 Searching for 8. Result: index = 7, which is off-the-end. Searching for 9. Result: index = 7, which is off-the-end. Searching for 10. Result: index = 7, which is off-the-end.
输出是注释,使得[1] 请注意,您可以使用严格弱排序但不是全排序的排序;也就是说,可能存在值在x, yx < yx > y,以及comp(value, *j)x == y值都是[first, last)。(有关更完整的讨论,请参阅 小于可比较 要求。)在范围内查找值,并不意味着找到一个与值相等的元素,而是找到一个等价于值的元素:既不大于也不小于的元素。但是,如果您使用的是全排序(如果您使用的是strcmp
,或者如果您对整数使用普通算术比较),那么您可以忽略这个技术上的区别:对于全排序,相等和等价是相同的。值[2] 请注意,即使与 [1] 等价的元素已经存在于范围[first, last)中,upper_bound的返回值也不会指向该元素。返回值要么是last,要么是迭代器中,使得对于每个迭代器在value < *ilog(last - first) + 1中,使得对于每个迭代器与first不相等,但是,然后*(i - 1)小于或等价于值.
[3] 随机访问迭代器 和 正向迭代器 之间的这种差异仅仅是因为advance对于 随机访问迭代器 是常数时间,而对于 正向迭代器 是线性时间。