SGI

upper_bound

类别: 算法 组件类型: 函数

原型

Upper_bound是一个重载名称;实际上有两个upper_bound函数。
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);

描述

Upper_bound是二分搜索的一种变体:它试图找到元素在有序范围内[first, last) [1]. 具体来说,它返回最后一个可以插入的位置,而不会破坏排序。[2] 第一个版本使用运算符<upper_bound用于比较,第二个版本使用 函数对象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).

类型要求

对于第一个版本

ForwardIterator

正向迭代器 的模型。StrictWeakOrdering

是一个有效的范围。

正向迭代器 的模型。StrictWeakOrdering

升序排序的。

复杂度比较次数是对数级的:最多log(last - first) + 1LessThanComparable。如果随机访问迭代器,则遍历范围的步数也是对数级的;否则,步数与. [3]

last - first

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对于 随机访问迭代器 是常数时间,而对于 正向迭代器 是线性时间。

另请参阅

lower_bound, equal_range, binary_search
[Silicon Surf] [STL Home]
版权所有 © 1999 Silicon Graphics, Inc. 保留所有权利。 商标信息