C++ equel_range(STL equal_range)二分查找算法详解
equal_range() 可以找出有序序列中所有和给定元素相等的元素。它的前两个参数是指定序列的两个正向迭代器,第三个参数是要查找的元素。这个算法会返回一个 pair 对象,它有两个正向迭代器成员,其中的 first 指向的是不小于第三个参数的一个元素,second 指向大于第三个参数的一个元素,所以我们也可以通过在单个调用中调用 lower_bound() 和 upper_bound() 来得到同样的结果。可以用下面这些语句来替换前一个代码段中的两条输出语句:
前面说过,本节的算法要求它们所处理的序列的元素是有序的,但这并不是全部。所有的二分查找算法都可以用于以特殊方式分区的序列。对于一个给定的希望值,序列中的元素必须按照 (element < wanted) 和 !(wanted < element) 来分区。可以用 equal_range() 二分查找算法来做这些工作,在对 values 容器中的元素执行 equal_range() 之前,可以按如下方式对它进行分区:
在前一段代码中,将 equal_range() 应用到了一个只包含单个期望值的序列中。如果这个序列包含多个实例,pr.first 会指向 wanted 的第一个匹配项,所以 [pr.first, pr.second) 这个范围包含的是所有的匹配项。下面是一个示例:
输出结果为:
所以当序列像上边示例那样分区并且不是完全有序时,为什么 equal_range() 会返回 wanted 的所有匹配项?为了弄明白这一点,需要理解 2 个 partition() 调用的作用:
1) 第一个分区操作保证严格小于 wanted 的所有元素都在左分区中,这些元素不需要是有序的。这个操作也保证所有大于等于 wanted 的元素都在右分区中,所以它们都在 wanted 的后面,而且也不需要是有序的。wanted 的所有匹配项都在右分区中,但是和大于 wanted 的元素混合在了一起。前一段代码中,在第一次调用 partition() 后,values 中的元素为:
2) 第二个分区操作会被应用到第一个操作的结果上。表达式 !(wanted<value) 等同于 (value <=wanted)。因此作为结果,小于等于 wanted 的所有元素会出现在左分区中,而且所有严格大于 wanted 的元素会在右分区中。这个操作的效果是将所有 wanted 的实例移到左分区中,所以它们被一起作为左分区的最后一个元素。在第二次调用 partition() 后,values 包含的元素如下:
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
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
所以当序列像上边示例那样分区并且不是完全有序时,为什么 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 的元素。所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频