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
測試值是否存在於已排序序列中 （函式模板）