草庐IT

C++ lower_bound/upper_bound用法解析

reasa 2023-04-15 原文

1. 作用
           lower_bound和upper_bound都是C++的STL库中的函数，作用差不多，lower_bound所返回的是第一个大于或等于目标元素的元素地址，而upper_bound则是返回第一个大于目标元素的元素地址。

            从定义就可以看出两者的差别只差在是否取等的的地方  那何必要设置两个函数呢（bushi

2.使用条件
            用lower_bound/upper_bound进行二分查找时必须保证查找区间为升序序列！

            什么是升序序列？你小学老师没教过你吗（bushi  举个例子你就明白了：

 

　　　　　　　　从第一个元素开始，后面的每一个元素都会大于等于前面一个元素 

　　　显然造成这种限制的原因就是出现在制作STL库的人身上 Orz，因为他所写的比较器是‘<’。 

3.用法
            lower_bound和upper_bound的用法与sort类似： 

1 lower_bound(起始位置first,结束位置last,目标元素val);
2 upper_bound(起始位置first,结束位置last,目标元素val);
3  //lower_bound/upperbound的返回值是一个地址值，若要得到目标元素的下标，直接减去数组首地址的值即可

　　    根据C++STL的尿性，同理可得，在lower_bound和upper_bound中我们同样可以添加cmp来进行自定义比较： 

1 lower_bound(a,a+n,2,cmp);
2 upper_bound(a,a+n,2,cmp);

 

　　　  当然你在使用lower_bound/upper_bound时要注意其二分查找的区间：

                    以上面的例子为例，他们的区间都是 [a,a+n) 

            不要问我[)是什么，这不是小学二年级教的吗（doge，‘[’ 就是大于等于的意思，‘)’ 就是小于的意思，请举一反三。

            有人可能会说了，lower_bound和upper_bound只能查找升序序列岂不是很废？那你一定是没有好好学sort ，显然，我们可以通过自定义比较函数来实现降序序列的查找: 

1 bool cmp(const int& a,const int& b){
2     return a>b;
3 }
4 lower_bound(a,a+n,val,cmp);
5 upper_bound(a,a+n,val,cmp);

　　　  或者你可以更简单一些： 

lower_bound(a,a+n,val,greater<int>());
upper_bound(a,a+n,val,greater<int>());

　　　  最后，如果函数并没有找到目标元素，则会返回last的地址，且last的地址是越界的。

4.思考 

　　　  https://www.luogu.com.cn/problem/P2249

C++boundnbspspancolorC++

有关C++ lower_bound/upper_bound用法解析的更多相关文章

  1. Ruby 解析字符串 - 2

    我有一个字符串input="maybe(thisis|thatwas)some((nice|ugly)(day|night)|(strange(weather|time)))"Ruby中解析该字符串的最佳方法是什么？我的意思是脚本应该能够像这样构建句子:maybethisissomeuglynightmaybethatwassomenicenightmaybethiswassomestrangetime等等，你明白了......我应该一个字符一个字符地读取字符串并构建一个带有堆栈的状态机来存储括号值以供以后计算，还是有更好的方法？也许为此目的准备了一个开箱即用的库？

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby - 用逗号、双引号和编码解析 csv - 2

    我正在使用ruby​​1.9解析以下带有MacRoman字符的csv文件#encoding:ISO-8859-1#csv_parse.csvName,main-dialogue"Marceu","Giveittohimóhe,hiswife."我做了以下解析。require'csv'input_string=File.read("../csv_parse.rb").force_encoding("ISO-8859-1").encode("UTF-8")#=>"Name,main-dialogue\r\n\"Marceu\",\"Giveittohim\x97he,hiswife.\"\

  4. ruby-on-rails - 我更新了 ruby​​ gems，现在到处都收到解析树错误和弃用警告! - 2

    简而言之错误:NOTE:Gem::SourceIndex#add_specisdeprecated,useSpecification.add_spec.Itwillberemovedonorafter2011-11-01.Gem::SourceIndex#add_speccalledfrom/opt/local/lib/ruby/site_ruby/1.8/rubygems/source_index.rb:91./opt/local/lib/ruby/gems/1.8/gems/rails-2.3.8/lib/rails/gem_dependency.rb:275:in`==':und

  5. ruby - 用 YAML.load 解析 json 安全吗？ - 2

    我正在使用ruby2.1.0我有一个json文件。例如:test.json{"item":[{"apple":1},{"banana":2}]}用YAML.load加载这个文件安全吗？YAML.load(File.read('test.json'))我正在尝试加载一个json或yaml格式的文件。 最佳答案 YAML可以加载JSONYAML.load('{"something":"test","other":4}')=>{"something"=>"test","other"=>4}JSON将无法加载YAML。JSON.load("

  6. ruby - 如何使用 Nokogiri 解析纯 HTML 表格？ - 2

    我想用Nokogiri解析HTML页面。页面的一部分有一个表，它没有使用任何特定的ID。是否可以提取如下内容:Today,3,455,34Today,1,1300,3664Today,10,100000,3444,Yesterday,3454,5656,3Yesterday,3545,1000,10Yesterday,3411,36223,15来自这个HTML:TodayYesterdayQntySizeLengthLengthSizeQnty345534345456563113003664354510001010100000344434113622315

  7. python - 帮我找到合适的 ruby​​/python 解析器生成器 - 2

    我使用的第一个解析器生成器是Parse::RecDescent，它的指南/教程很棒，但它最有用的功能是它的调试工具，特别是tracing功能(通过将$RD_TRACE设置为1来激活)。我正在寻找可以帮助您调试其规则的解析器生成器。问题是，它必须用python或ruby​​编写，并且具有详细模式/跟踪模式或非常有用的调试技术。有人知道这样的解析器生成器吗？编辑:当我说调试时，我并不是指调试python或ruby​​。我指的是调试解析器生成器，查看它在每一步都在做什么，查看它正在读取的每个字符，它试图匹配的规则。希望你明白这一点。赏金编辑:要赢得赏金，请展示一个解析器生成器框架，并说明它的

  8. ruby - 如何用 Nokogiri 解析连续的标签？ - 2

    我有这样的HTML代码:Label1Value1Label2Value2...我的代码不起作用。doc.css("first").eachdo|item|label=item.css("dt")value=item.css("dd")end显示所有首先标记，然后标记标签，我需要“标签:值” 最佳答案 首先，您的HTML应该有和中的元素:Label1Value1Label2Value2...但这不会改变您解析它的方式。你想找到s并遍历它们，然后在每个你可以使用next_element得到;像这样:doc=Nokogiri::HTML(

  9. ruby - 有人可以解释一下在 Ruby 中注入(inject)的真实、通俗易懂的用法吗？ - 2

    我正在学习Ruby，遇到了inject。我正处于理解它的风口浪尖，但当我是那种需要真实世界的例子来学习一些东西的人时。我遇到的最常见的例子是人们使用inject来添加一个(1..10)范围的总和，我不太关心这个。这是一个任意的例子。在实际程序中我会用它做什么？我正在学习，所以我可以继续使用Rails，但我不必有一个以Web为中心的示例。我只需要一些我可以全神贯注的目标。谢谢大家。 最佳答案 inject有时可以通过它的“其他”名称reduce更好地理解。它是一个对Enumerable进行操作(迭代一次)并返回单个值的函数。它有许多有

  10. ruby-on-rails - 如何在 Rails 3 中禁用 XML 解析 - 2

    我想禁用HTTP参数的自动XML解析。但我发现命令仅适用于Rails2.x，它们都不适用于3.0:config.action_controller.param_parsers.deleteMime::XML(application.rb)ActionController::Base.param_parsers.deleteMime::XMLRails3.0中的等价物是什么？ 最佳答案 根据CVE-2013-0156的最新安全公告你可以将它用于Rails3.0。3.1和3.2ActionDispatch::ParamsParser::

随机推荐