equal_range-c和c++中文资料站

C&C++标准库

std::

equal_range

函数模板 <algorithm>

default (1)

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

custom (2)

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

获取相等元素的子范围的边界

返回子范围的边界，其中包括范围[first,last)中值等于val的所有元素。。

第一个版本使用操作符<比较元素，第二个版本使用comp操作符比较元素。如果 (!(a<b) && !(b<a))或如果 (!comp(a,b) && !comp(b,a)),两个元素a和b被认为是等价的。

这个范围内的元素应该已经按照同样的标准排序(操作符<或comp)，或者至少根据val进行分区。

如果val不等于范围内的任何值，则返回的子范围的长度为0，两个迭代器都指向比val更大的最近的值(如果有)，或者最后指向比val更大的所有元素 (如果val比较大于范围内的所有元素)。

这个函数模板的行为相当于:

template <class ForwardIterator, class T>
  pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it = std::lower_bound (first,last,val);
  return std::make_pair ( it, std::upper_bound(it,last,val) );
}

☲ 参数

first, last: 指向一个已排序(或正确分区)序列初始和最终位置的前向迭代器。使用的范围是[first,last)，它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
val: 该范围中要搜索的子范围的边界值。
对于(1)，T是支持与range [first,last)的元素作为operator<的右侧操作数进行比较的类型。
comp: 二元函数，接受两个由ForwardIterator指向的类型参数(和T类型)，并返回一个可转换为bool类型的值。返回的值表示第一个参数是否被认为在第二个参数之前。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。

☉ 返回值

pair对象，其成员pair::first是指向相等值子范围下界的迭代器， pair::second是指向其上界的迭代器。这些值分别与lower_bound和upper_bound函数返回的值相同。

☣ 示例

// equal_range example
// equal_range example
#include <iostream>     // std::cout
#include <algorithm>    // std::equal_range, std::sort
#include <vector>       // std::vector

bool mygreater (int i,int j) { return (i>j); }

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  std::vector<int> v(myints,myints+8);                         // 10 20 30 30 20 10 10 20
  std::pair<std::vector<int>::iterator,std::vector<int>::iterator> bounds;

  // using default comparison:
  std::sort (v.begin(), v.end());                              // 10 10 10 20 20 20 30 30
  bounds=std::equal_range (v.begin(), v.end(), 20);            //          ^        ^

  // using "mygreater" as comp:
  std::sort (v.begin(), v.end(), mygreater);                   // 30 30 20 20 20 10 10 10
  bounds=std::equal_range (v.begin(), v.end(), 20, mygreater); //       ^        ^

  std::cout << "bounds at positions " << (bounds.first - v.begin());
  std::cout << " and " << (bounds.second - v.begin()) << '\n';

  return 0;
}

输出:
bounds at positions 2 and 5

✥ 复杂度

平均而言， first and last之间的距离为2倍对数:执行大约log2(N)+1个元素比较(其中N是距离)。
在非随机访问迭代器上，迭代器的前进平均会给自己带来高达两倍的线性复杂度(N)。

⇄ 数据竞争

范围[first,last)中的对象将被访问。

☂ 异常安全性

如果元素比较或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。

🍄 另请参阅

lower_bound	返回迭代器下界(函数模板)
upper_bound	返回迭代器上界(函数模板)
binary_search	测试value是否存在于排序序列中(函数模板)