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 的元素。