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;

这段代码的输出如下：

第一行显示的是元素原始的顺序，第二行显示的是分区之后的顺序。两次分区操作改变了元素的顺序，但改变的并不多，现在我们可以将 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;
}

输出结果为：

values 容器中有一些值为 22 的元素，22 也是 wanted 的值。equal_range() 返回了 wanted 在这个序列中的三个实例。这个序列只是被分区了，并不是完全有序的，当序列完全有序时，显然也同样适应。

所以当序列像上边示例那样分区并且不是完全有序时，为什么 equal_range() 会返回 wanted 的所有匹配项？为了弄明白这一点，需要理解 2 个 partition() 调用的作用：

1) 第一个分区操作保证严格小于 wanted 的所有元素都在左分区中，这些元素不需要是有序的。这个操作也保证所有大于等于 wanted 的元素都在右分区中，所以它们都在 wanted 的后面，而且也不需要是有序的。wanted 的所有匹配项都在右分区中，但是和大于 wanted 的元素混合在了一起。前一段代码中，在第一次调用 partition() 后，values 中的元素为：

17、11、13 是仅有的小于 wanted 的几个值，它们显然在左分区中。分区并不能以任何特别的方式来确定和 wanted 所对应值的位置。22 的全部实例可能出现在右分区的任何位置。

2) 第二个分区操作会被应用到第一个操作的结果上。表达式 !(wanted<value) 等同于 (value <=wanted)。因此作为结果，小于等于 wanted 的所有元素会出现在左分区中，而且所有严格大于 wanted 的元素会在右分区中。这个操作的效果是将所有 wanted 的实例移到左分区中，所以它们被一起作为左分区的最后一个元素。在第二次调用 partition() 后，values 包含的元素如下：

equal_range() 找到的下边界指向 22 的第一个匹配项，上边界指向 22 的最后一个匹配项的后面，即值为 48 的元素。