我正在研究http://www.cplusplus.com/reference/algorithm/upper_bound/的std::upper_bound我发现这可能会在非随机访问迭代器上以线性时间运行。我需要将其用于排序vector。现在我不知道什么是非随机访问迭代器以及它是否会在排序后的vector上以对数时间运行。谁能帮我解决这个问题。 最佳答案 §23.3.6.1[vector.overview]/p1:Avectorisasequencecontainerthatsupportsrandomaccessiterator
我有一个二维数组，我想在其中找到特定列的下界。我如何使用std::lower_bound做到这一点？ 最佳答案 简介这并不像人们想象的那么难，让我们首先浏览一下适用于范围的算法函数的摘要。每个这样的函数，比如std::lower_bound，接受一个begin和一个end迭代器来知道它们要搜索哪些元素.我们案例中的问题是，创建一个遍历列而不是行的迭代器似乎很重要。好消息；它不是。形成指向数组的指针我们可以在C++中创建指向几乎所有内容的指针，当然也包括数组。指针的好处在于，如果我们递增一个，我们将到达下一个元素，无论指针指的是什么类
通常，STL是为提高速度而构建的。然而，在map和set数据结构上只有upper_bound和lower_bound并且没有操作来检索具有小于输入键的最大键的条目k.为什么是这样？我知道我可以简单地做一个lower_bound并做一个--it检索它，但根据数据结构，立即搜索正确的条目可能比搜索另一个条目然后返回一步更有效。例如，std::map使用红黑树，即二叉搜索树。如果upper_bound返回的元素是大于根的最小元素，则--it必须回到根，查询O(logn)的额外成本。如果这是Java，我会接受设计决定。然而，STL是为实现最高速度而构建的，那么为什么要省略此操作？澄清:我不是在
我有以下完美运行的代码。目标:给定一个数n，找出n的下一个和上一个数。基于下面的例子:如果n=50，那么我将分别得到60和40。我可以通过使用upper_bound获得60。但是我如何获得50之前的数字我似乎找不到提供的算法来做到这一点。setmyset;set::iteratorit,itlow,itup;for(inti=1;i引用http://www.cplusplus.com/reference/stl/set/lower_bound/，它说upper_bound“返回指向容器中第一个元素的迭代器，它不比较小于x”但我确定还有其他东西指向比较小于x的东西.提前致谢!:)
我在内存中有一个16字节宽条目的数组。每个条目由两个64位整数字段组成。这些条目根据每个条目的第一个64位整数的数值进行排序。是否可以在不首先将数据加载到std::vector的情况下使用STL进行二进制搜索？我已经看到我可以在普通数组上使用STLlower_bound()方法，但我需要它来忽略每个条目的第二个64位字段。这可能吗？ 最佳答案 您不需要使用std::vector,但如果您首先将数据转换为正确的数据类型，这是最简单的:#includestructmystruct{std::int64_tfirst,second;};关
我知道我们需要包含一些比较功能才能实现这一点。但不能写这个。例如:vector的元素={(2,4),(4,2),(5,1),(5,3)}找到=5lower_bound()应该返回2代码->#definepppairboolcmp(constpp&l,constpp&r){returnl.firstv;sort(v.begin(),v.end(),cmp);intid=(int)(lower_bound(v.begin(),v.end(),??)-v.begin());} 最佳答案 对(justliketuples)无论如何按字典顺序
我知道你不应该使用std::find(some_map.begin(),some_map.end())或std::lower_bound，因为它会采用线性时间而不是some_map.lower_bound提供的对数时间。std::list也会发生类似的事情:有用于排序的std::list::sort函数，但您无法调用std::sort(some_list.begin(),some_list.end())，因为迭代器不是随机访问的。但是，例如，std::swap具有标准容器的重载，因此swap(some_map,other_map)的调用需要O(1)，而不是在)。为什么C++标准不为ma
我在这些页面上查看upper_bound和lower_bound算法在STL中的工作方式:lower_bound,upper_bound，并且在这些页面上以相同的方式记录:lower_bound,upper_bound查看链接中的代码，它们似乎对我做了完全相同的事情，只有以下几行不同(查看前2个链接中的代码):下限(第10行):if(*itupper_bound(第10行):if(!(val但是肯定颠倒被比较的元素然后将它们与false进行比较是双重否定，因此它们做的事情完全一样？是否真的存在我没有看到的差异，这是网站文档中的错误吗？如果是后者，正确的做法是什么？
boost::lower_bound(发现here)在Range2.0中的实现按值获取其参数。这是为什么？std::lower_bound通过constref获取其参数-参见here 最佳答案 虽然很难确定其中的原因，但有两点需要牢记:按值传递的一般原因是当您最终在函数中制作拷贝时。此外，按值传递可能会调用prvalues/xvalues上的移动构造函数和左值上的复制构造函数。在最新版本的boost库中，boost::lower_bound在其实现中使用了std::lower_bound。Boost1.59对链接中提到的boost:
我给了一个std::set>和一个整数x，我必须找到第一个元素大于或等于给定整数x的第一对的迭代器.我了解到如果s是set>和{x,y}是一对然后我可以使用s.lower_bound({x,y}).但是，就我而言，我只需要关心第一个元素x.所以，我的问题是如何使用lower_bound在set>当我只关心第一个元素时？ 最佳答案 核心问题是你的std::set实例已经排序，但默认为std::pairoperator.您不能直观地使用成员函数std::set::lower_bound，因为它使用了其类类型的比较函数。你不能使用std:
