lower_bound

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

原型

template <class ForwardIterator, class LessThanComparable>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const LessThanComparable& value);

template <class ForwardIterator, class T, class StrictWeakOrdering>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                            const T& value, StrictWeakOrdering comp);

描述

第一个版本lower_bound返回最远的迭代器i在[first, last)这样，对于每个迭代器j在[first, i), *j < value.

第二个版本lower_bound返回最远的迭代器i在[first, last)这样，对于每个迭代器j在[first, i), comp(*j, value)是true.

定义

类型要求

• ForwardIterator是 正向迭代器 的模型。
• LessThanComparable是 小于可比较 的模型。
• 类型对象的排序LessThanComparable是一个严格弱排序，如 小于可比较 要求中定义的那样。
• ForwardIterator的值类型与LessThanComparable.

• ForwardIterator是 正向迭代器 的模型。
• StrictWeakOrdering是 严格弱排序 的模型。
• ForwardIterator的值类型与T.
• ForwardIterator的值类型可转换为StrictWeakOrdering的参数类型。

先决条件

• [first, last)是一个有效的范围。
• [first, last)根据operator<按升序排序。 也就是说，对于每一对迭代器i和j在[first, last)这样i在j, *j < *i是false.

• [first, last)是一个有效的范围。
• [first, last)根据 函数对象comp按升序排序。 也就是说，对于每一对迭代器i和j在[first, last)这样i在j, comp(*j, *i)是false.

按升序排序

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 = lower_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 = 0, A[0] == 1
Searching for 2.  Result: index = 1, A[1] == 2
Searching for 3.  Result: index = 2, A[2] == 3
Searching for 4.  Result: index = 5, A[5] == 5
Searching for 5.  Result: index = 5, A[5] == 5
Searching for 6.  Result: index = 6, A[6] == 8
Searching for 7.  Result: index = 6, A[6] == 8
Searching for 8.  Result: index = 6, A[6] == 8
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和falsex == y值都是[first, last)。 （有关更完整的讨论，请参阅 小于可比较 要求。） 查找值在范围内值，然后，并不意味着找到一个与值相等的元素，而是找到一个与等效的元素：一个既不大于也不小于的元素。 但是，如果您使用的是全排序（如果您使用的是

strcmp值，例如，或者如果您对整数使用普通的算术比较），那么您可以忽略这种技术区别：对于全排序，相等和等效是相同的。[first, last)[2] 如果一个与 [1]lower_bound等效的元素已存在于范围内

，那么的返回值将是一个指向该元素的迭代器。[3] 随机访问迭代器 和 正向迭代器 之间的这种差异仅仅是因为

advance