C++

参考

<algorithm>

function template
<algorithm>

std::equal_range

默认 (1)
template <class ForwardIterator, class T>  pair<ForwardIterator,ForwardIterator>    equal_range (ForwardIterator first, ForwardIterator last, const T& val);
自定义 (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 等价的所有元素的子范围的界限。

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

范围内的元素应已根据相同的标准（operator< 或 comp）排序，或者至少相对于 val 分区。

如果 val 不等价于范围内的任何值，则返回的子范围长度为零，两个迭代器均指向大于 val 的最近值（如果存在），或者指向 last（如果 val 与范围内的所有元素都大于 val）。

此函数模板的行为等同于
1
2
3
4
5
6
7
 
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
Forward iterators 指向 排序（或正确 分区）序列的初始和最终位置。使用的范围是 [first,last)，它包含 first 和 last 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
val
要搜索的子范围的值。
对于(1)，T 应该是可以与范围 [first,last) 的元素进行比较的类型，作为 operator< 的操作数。
comp
二元函数，接受由 ForwardIterator 指向的类型（以及 T 类型）的两个参数，并返回一个可转换为 bool 的值。返回的值指示第一个参数是否应排在第二个之前。
该函数不得修改其任何参数。
这可以是函数指针或函数对象。

返回值

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

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
// 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 和 last 之间 距离的两次对数：执行大约 2*log2(N)+1 次元素比较（其中 N 是此距离）。
对于非随机访问迭代器，迭代器 前进本身会产生额外的、平均高达 N 的线性复杂度。

数据竞争

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

异常

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

另见

lower_bound
返回指向下界的迭代器 （函数模板）
upper_bound
返回指向上界的迭代器 （函数模板）
binary_search
测试值是否存在于已排序序列中 （函数模板）