C++中的std::lower_bound()和std::upper_bound()函数

2023-12-04 00:38
文章标签 c++ 函数 bound std lower upper

本文主要是介绍C++中的std::lower_bound()和std::upper_bound()函数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 前言
  • 函数定义
  • 实际例子
    • 自己设计
    • 具体分析
    • 最终版本
  • 总结

前言

问题是躲不掉的,该来的总会来,这不是代码中又遇到了 std::upper_bound() 函数,再来学习一遍好了,在我的印象中每次看到这 lower_boundupper_bound 两个函数都有些别扭,凡是见到他们必须查一遍,因为我记得它们两个函数的作用不对称,这一点记得很清楚,但是它们两个函数查找的细节却记不住,这次总结一下,强化记忆,下次回忆起来应该会快一点。

函数定义

今天看到这两个函数时挠挠头又打开了搜索引擎,看到文章里写到 std::lower_bound() 是返回大于等于 value 值的位置,而 std::upper_bound() 是返回第一个大于 value 值的位置,第一反应真是瞎写,怎么俩都是大于,肯定应该是一个大于一个小于啊,这样才“合理”嘛!

但是当看到多个文章中采用相同的说法时,刚刚还“坚定”的想法开始动摇,然后开始查C++标准文档,一遍遍读着那有些拗口的文字:

std::lower_bound returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

std::upper_bound returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found.

这些标准文档上的文字印证了刚刚查询到的结果,两个函数返回的结果都是迭代器,std::lower_bound() 是在区间内找到第一个大于等于 value 的值的位置并返回,如果没找到就返回 end() 位置。而 std::upper_bound() 是找到第一个大于 value 值的位置并返回,如果找不到同样返回 end() 位置。

两个函数都提到了大于操作,而没有涉及到小于操作,这就是我前面提到的不对称,也是我感觉不合理的地方,但是当尝试使用了几次这两个函数之后,我发现这两个函数的设计的恰到好处,这样的设计很方便我们来做一些具体的操作。

实际例子

首先说明这两个函数内部使用了二分查找,所以必须用在有序的区间上,满足有序的结构中有两个常见的面孔:std::mapstd::set,他们本身就是有序的,所以提供了 std::map::lower_bound()std::set::lower_bound() 这种类似的成员函数,但是原理都是一样的,我们可以弄明白一个,另外类似的函数就都清楚了。

自己设计

如果你看了这两个函数的具体含义也和我一样不太理解为什么这样设计,可以思考一下接下来这个需求,找出数组内所有值为2和3的元素,图例如下:

lower_bound()

对于一个有序数组,我们在实现 lower_bound() 函数和 upper_bound() 函数时可以让它返回指定的位置来确定取值区间,第①种情况就是标准函数库的实现方式,而第②种和第③种就是我第一印象中感觉应该对称的样子,这样看起来也没什么问题,下面具体来分析下后两种设计有哪些不好的地方。

具体分析

假如我们采用第②种实现方式,那么实现打印元素2和3的代码要写成下面这样:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main()
{std::vector<int> v{1,1,2,2,3,3,3,5,7,8};std::vector<int>::const_iterator itorLower = std::lower_bound(v.begin(), v.end(), 2);std::vector<int>::const_iterator itorUpper = std::upper_bound(v.begin(), v.end(), 3);while(true){std::cout << *itorLower << std::endl;if (itorLower == itorUpper)break;++itorLower;}return 0;
}

代码看起来还可以,打印完元素后判断到达了结尾直接跳出循环,但是如果要是数组中不包含元素2和3呢,那么也会打印出一个元素,还有可能导致程序崩溃。

如果我们采用第③种实现方式,那么实现打印元素2和3的代码要写成下面这样:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main()
{std::vector<int> v{1,1,2,2,3,3,3,5,7,8};std::vector<int>::const_iterator itorLower = std::lower_bound(v.begin(), v.end(), 2);std::vector<int>::const_iterator itorUpper = std::upper_bound(v.begin(), v.end(), 3);for(++itorLower; itorLower != itorUpper; ++itorLower){std::cout << *itorLower << std::endl;}return 0;
}

这代码看起来简洁了很多,但是在循环开始前需要先调用 ++itorLower,因为第一个元素并不是需要找到的元素,所以要先跳过它,这样看来确实多做了一步操作,一开始就让 itorLow 指向第一个2就好了呀。

最终版本

当你尝试几种实现方式就会发现,还是标准库提供的这种方式使用起来更加方便,虽然采取的不是对称的方式,但是统一了存在查找元素和不存在查找元素的的情况,写出的代码也比较简洁,没有多余的步骤,代码如下:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main()
{std::vector<int> v{1,1,2,2,3,3,3,5,7,8};auto itorUpper = std::upper_bound(v.begin(), v.end(), 3);for(auto itorLower = std::lower_bound(v.begin(), v.end(), 2); itorLower != itorUpper; ++itorLower){std::cout << *itorLower << std::endl;}return 0;
}

总结

  • 有些函数的实现方式和我们想象的并不一样,但是我们可以通过熟练使用来了解它为什么这样设计
  • 对称结构虽然是很美的,但是非对称的结构在编程中常常出现,同样有其美丽所在
  • 遇到类似的问题可以动笔画一画,列举出各种情况会有利于你做出正确的判断

==>> 反爬链接,请勿点击,原地爆炸,概不负责!<<==

有时会很焦虑,看到优秀的人比你还努力时总让人感到急迫,但是一味的忧患是无意义的,脚下迈出的每一步才是真真正正的前进,不要去忧虑可能根本就不会发生的事情,那样你会轻松许多

这篇关于C++中的std::lower_bound()和std::upper_bound()函数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/451460

相关文章

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

postgresql使用UUID函数的方法

《postgresql使用UUID函数的方法》本文给大家介绍postgresql使用UUID函数的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录PostgreSQL有两种生成uuid的方法。可以先通过sql查看是否已安装扩展函数,和可以安装的扩展函数

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更

PostgreSQL中rank()窗口函数实用指南与示例

《PostgreSQL中rank()窗口函数实用指南与示例》在数据分析和数据库管理中,经常需要对数据进行排名操作,PostgreSQL提供了强大的窗口函数rank(),可以方便地对结果集中的行进行排名... 目录一、rank()函数简介二、基础示例:部门内员工薪资排名示例数据排名查询三、高级应用示例1. 每

全面掌握 SQL 中的 DATEDIFF函数及用法最佳实践

《全面掌握SQL中的DATEDIFF函数及用法最佳实践》本文解析DATEDIFF在不同数据库中的差异,强调其边界计算原理,探讨应用场景及陷阱,推荐根据需求选择TIMESTAMPDIFF或inte... 目录1. 核心概念:DATEDIFF 究竟在计算什么?2. 主流数据库中的 DATEDIFF 实现2.1

MySQL中的LENGTH()函数用法详解与实例分析

《MySQL中的LENGTH()函数用法详解与实例分析》MySQLLENGTH()函数用于计算字符串的字节长度,区别于CHAR_LENGTH()的字符长度,适用于多字节字符集(如UTF-8)的数据验证... 目录1. LENGTH()函数的基本语法2. LENGTH()函数的返回值2.1 示例1:计算字符串

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被