C++ equel_range(STL equal_range)二分查詢演算法詳解

equal_range() 可以找出有序序列中所有和給定元素相等的元素。它的前兩個引數是指定序列的兩個正向疊代器，第三個引數是要查詢的元素。這個演算法會返回一個 pair 物件，它有兩個正向疊代器成員，其中的 first 指向的是不小於第三個引數的一個元素，second 指向大於第三個引數的一個元素，所以我們也可以通過在單個呼叫中呼叫 lower_bound() 和 upper_bound() 來得到同樣的結果。可以用下面這些語句來替換前一個程式碼段中的兩條輸出語句：

auto pr = std::equal_range(std::begin(values) , std::end(values), wanted);
std::cout << "the lower bound for " << wanted << " is " << *pr.first << std::endl;
std::cout << "Tthe upper bound for " << wanted << " is " << *pr.second << std::endl;

它和前一段程式碼的輸出完全相同。和前面的二分查詢演算法一樣，equal_range() 也有一個有額外引數的版本，這個引數可以為有序序列提供一些不同於 < 運算子的比較。

前面說過，本節的演算法要求它們所處理的序列的元素是有序的，但這並不是全部。所有的二分查詢演算法都可以用於以特殊方式分割區的序列。對於一個給定的希望值，序列中的元素必須按照 (element < wanted) 和 !(wanted < element) 來分割區。可以用 equal_range() 二分查詢演算法來做這些工作，在對 values 容器中的元素執行 equal_range() 之前，可以按如下方式對它進行分割區：

std::list<int> values {17, 11, 40, 36, 22, 54, 48, 70, 61, 82, 78, 89, 99, 92, 43};
// Output the elements in original order
std::copy(std::begin(values), std::end(values),std::ostream_iterator<int> {std::cout, " "});
std::cout << std::endl;
int wanted {22};    // What we are looking for
std::partition(std::begin(values), std::end(values),[wanted](double value) { return value < wanted; });
std::partition(std::begin(values), std::end(values),[wanted](double value) { return !(wanted < value); });
//Output the elements after partitioning
std::copy(std::begin(values), std::end(values),std::ostream_iterator<int>{std::cout," "});
std::cout<< std::endl;

這段程式碼的輸出如下：

17 11 40 36 22 54 48 70 61 82 78 89 99 92 43
17 11 22 36 40 54 48 70 61 82 78 89 99 92 43

第一行顯示的是元素原始的順序，第二行顯示的是分割區之後的順序。兩次分割區操作改變了元素的順序，但改變的並不多，現在我們可以將 equal_range() 應用到 values 容器的元素上，期望值為 wanted:

auto pr = std::equal_range(std::begin(values), std::end(values), wanted);
std::cout << "the lower bound for " << wanted << " is " << *pr.first << std::endl;
std::cout << "the upper bound for " << wanted << " is " << *pr.second << std::endl;

這段程式碼和前一段程式碼的輸出是相同的，在前一段程式碼中，用容器物件的成員函數 sort() 對元素進行了完全排序。本節的所有演算法都可以用於以這種方式分割區的序列上。顯然，如果分割區使用的是>，那麼在查詢演算法中使用的函數物件也必須和它保持一致。

在前一段程式碼中，將 equal_range() 應用到了一個只包含單個期望值的序列中。如果這個序列包含多個範例，pr.first 會指向 wanted 的第一個匹配項，所以 [pr.first, pr.second) 這個範圍包含的是所有的匹配項。下面是一個範例：

// Using partition() and equal_range() to find duplicates of a value in a range
#include <iostream>                              // For standard streams
#include <list>                                  // For list container
#include <algorithm>                             // For copy(), partition()
#include <iterator>                              // For ostream_iterator

int main()
{
    std::list<int> values {17, 11, 40, 13, 22, 54, 48, 70, 22, 61, 82, 78, 22, 89, 99, 92, 43};

    // Output the elements in their original order
    std::cout << "The elements in the original sequence are:n";
    std::copy(std::begin(values), std::end(values), std::ostream_iterator<int> {std::cout, " "});
    std::cout << std::endl;

    int wanted {22};                                         // What we are looking for

    std::partition(std::begin(values), std::end(values),[wanted](double value) { return value < wanted; });
    std::partition(std::begin(values), std::end(values),[wanted](double value) { return !(wanted < value); });

    // Output the elements after partitioning
    std::cout << "The elements after partitioning are:n";
    std::copy(std::begin(values), std::end(values), std::ostream_iterator<int> {std::cout, " "});
    std::cout << std::endl;

    auto pr = std::equal_range(std::begin(values), std::end(values), wanted);
    std::cout << "The lower bound for " << wanted << " is " << *pr.first << std::endl;
    std::cout << "The upper bound for " << wanted << " is " << *pr.second << std::endl;

    std::cout << "nThe elements found by equal_range() are:n";
    std::copy(pr.first, pr.second, std::ostream_iterator<int> {std::cout, " "});
    std::cout << std::endl;
}

輸出結果為：

The elements in the original sequence are:
17 11 40 13 22 54 48 70 22 61 82 78 22 89 99 92 43
The elements after partitioning are:
17 11 13 22 22 22 48 70 54 61 82 78 40 89 99 92 43
The lower bound for 22 is 22
The upper bound for 22 is 48

The elements found by equal_range() are:
22 22 22

values 容器中有一些值為 22 的元素，22 也是 wanted 的值。equal_range() 返回了 wanted 在這個序列中的三個範例。這個序列只是被分割區了，並不是完全有序的，當序列完全有序時，顯然也同樣適應。

所以當序列像上邊範例那樣分割區並且不是完全有序時，為什麼 equal_range() 會返回 wanted 的所有匹配項？為了弄明白這一點，需要理解 2 個 partition() 呼叫的作用：

1) 第一個分割區操作保證嚴格小於 wanted 的所有元素都在左分割區中，這些元素不需要是有序的。這個操作也保證所有大於等於 wanted 的元素都在右分割區中，所以它們都在 wanted 的後面，而且也不需要是有序的。wanted 的所有匹配項都在右分割區中，但是和大於 wanted 的元素混合在了一起。前一段程式碼中，在第一次呼叫 partition() 後，values 中的元素為：

17 11 13 40 22 54 48 70 22 61 82 78 22 89 99 92 43

17、11、13 是僅有的小於 wanted 的幾個值，它們顯然在左分割區中。分割區並不能以任何特別的方式來確定和 wanted 所對應值的位置。22 的全部範例可能出現在右分割區的任何位置。

2) 第二個分割區操作會被應用到第一個操作的結果上。表示式 !(wanted<value) 等同於 (value <=wanted)。因此作為結果，小於等於 wanted 的所有元素會出現在左分割區中，而且所有嚴格大於 wanted 的元素會在右分割區中。這個操作的效果是將所有 wanted 的範例移到左分割區中，所以它們被一起作為左分割區的最後一個元素。在第二次呼叫 partition() 後，values 包含的元素如下：

17 11 13 22 22 22 48 70 54 61 82 78 40 89 99 92 43

equal_range() 找到的下邊界指向 22 的第一個匹配項，上邊界指向 22 的最後一個匹配項的後面，即值為 48 的元素。