equal_range

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

原型

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

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

描述

的第一个版本equal_range返回一对迭代器[i, j). i是[first, last)中满足以下条件的最远迭代器：对于k中的每个迭代器[first, i), *k < value. j是[first, last)中满足以下条件的最远迭代器：对于k中的每个迭代器[first, j), value < *k为false。对于每个迭代器k中的每个迭代器[i, j)，既不value < *k也不*k < value为true. [2]

的第二个版本equal_range返回一对迭代器[i, j). i是[first, last)中满足以下条件的最远迭代器：对于k中的每个迭代器[first, i), comp(*k, value)为true. j是[first, last)中满足以下条件的最远迭代器：对于k中的每个迭代器[first, j), comp(value, *k)为false。对于每个迭代器k中的每个迭代器[i, j)，既不comp(value, *k)也不comp(*k, value)为true. [2]

定义

类型要求

• 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.

复杂度

成正比

int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 2; i <= 4; ++i) {
    pair<int*, int*> result = equal_range(A, A + N, i);

    cout << endl;
    cout << "Searching for " << i << endl;
    cout << "  First position where " << i << " could be inserted: "
         << result.first - A << endl;
    cout << "  Last position where " << i << " could be inserted: "
         << result.second - A << endl;
    if (result.first < A + N)
      cout << "  *result.first = " << *result.first << endl;
    if (result.second < A + N)
      cout << "  *result.second = " << *result.second << endl;
  }
}    

Searching for 2
  First position where 2 could be inserted: 1
  Last position where 2 could be inserted: 2
  *result.first = 2
  *result.second = 3

Searching for 3
  First position where 3 could be inserted: 2
  Last position where 3 could be inserted: 5
  *result.first = 3
  *result.second = 5

Searching for 4
  First position where 4 could be inserted: 5
  Last position where 4 could be inserted: 5
  *result.first = 5
  *result.second = 5

输出为

注释x和y使得x < y, x > y，并且x == y都为false。（请参阅 小于可比较 要求以了解更多信息。）因此，在范围内查找值在范围内[first, last)，并不意味着找到一个等于值的元素，而是找到一个等价于值的元素：一个既不大于也不小于值的元素。但是，如果您使用的是全序（例如，如果您使用的是strcmp，或者如果您对整数使用普通的算术比较），那么您可以忽略此技术上的区别：对于全序，相等和等价是相同的。

[2] 请注意，equal_range可能会返回一个空范围；也就是说，它可能返回一对元素，这两个元素都是相同的迭代器。Equal_range当且仅当范围[first, last)不包含与值等价的元素时，才会返回空范围。值可以插入而不违反范围排序的位置只有一个，因此返回值是一对元素，这两个元素都是指向该位置的迭代器。

[3] 随机访问迭代器 和 前向迭代器 之间的这种差异仅仅是因为advance对于 随机访问迭代器 是常数时间，对于 前向迭代器 是线性时间。

另请参阅