查找向量中最近的点
给定一个具有多个值的排序向量,如下例所示:
std::vector<double> f;
f.pushback(10);
f.pushback(100);
f.pushback(1000);
f.pushback(10000);
我正在寻找最优雅的方法来检索任何 double d 与其直接相邻的两个值。 例如,给定值“45”,我希望返回“10”和“100”。
我正在查看 lower_bound 和 upper_bound,但它们没有达到我想要的效果。 你能帮我吗?
编辑:我决定发布我自己的答案,因为它在某种程度上是我在该线程中获得的所有有用答案的综合体。 我已经投票赞成了我认为最有帮助的那些答案。
谢谢大家,
戴夫
Given a sorted vector with a number of values, as in the following example:
std::vector<double> f;
f.pushback(10);
f.pushback(100);
f.pushback(1000);
f.pushback(10000);
I'm looking for the most elegant way to retrieve for any double d the two values that are immediately adjacent to it. For example, given the value "45", I'd like this to return "10" and "100".
I was looking at lower_bound and upper_bound, but they don't do what I want. Can you help?
EDIT: I've decided to post my own anser, as it is somewhat a composite of all the helpful answers that I got in this thread. I've voted up those answers which I thought were most helpful.
Thanks everyone,
Dave
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(10)
您可以使用 equal_range() 在一次调用中获取这两个值(如果存在)。 它返回一个 std::pair 迭代器,第一个是第一个位置,第二个是最后一个位置,您可以在其中插入传递的值而不违反顺序。 为了严格满足您的标准,您必须在验证迭代器不等于向量的 begin() 之后,首先递减迭代器。
You can grab both values (if they exist) in one call with equal_range(). It returns a std::pair of iterators, with first being the first location and second being the last location in which you could insert the value passed without violating ordering. To strictly meet your criteria, you'd have to decrement the iterator in first, after verifying that it wasn't equal to the vector's begin().
您可以使用 STL 的 lower_bound 在几行代码中获得您想要的结果。 lower_bound 在底层使用二分搜索,因此运行时间为 O(log n)。
You can use STL's lower_bound to get want you want in a few lines of code. lower_bound uses binary search under the hood, so your runtime is O(log n).
您可以简单地使用 二分搜索,它将在 O(log(n)) 中运行。
这是一个 Lua 片段(我没有时间用 C++ 来做,抱歉),它可以做你想要的事情,除了限制条件(你无论如何都没有定义):
它需要从命令行搜索值:
You could simply use a binary search, which will run in O(log(n)).
Here is a Lua snippet (I don't have time to do it in C++, sorry) which does what you want, except for limit conditions (that you did not define anyway) :
It takes the value to search from the command line :
我将发布我自己的答案,并对任何帮助我实现这一目标的人进行投票,因为这是我最终将使用的,并且你们都帮助我得出了这个结论。 欢迎评论。
I'm going to post my own anser, and vote anyone up that helped me to reach it, since this is what I'll use in the end, and you've all helped me reach this conclusion. Comments are welcome.
如果(在您的情况下)d 小于第一个元素或大于最后一个元素怎么办? 以及如何处理负值? 顺便说一句:保证你的“d”位于向量的第一个值和最后一个值之间,你可以这样做:
这是剩下的:
足够优雅吗? :/
What if (in your case) d is less than the first element or more than the last? And how to deal with negative values? By the way: guaranteeing that your "d" lives between the first and the last value of your vector you can do like that:
Here is the rest:
Elegant enough? :/
您可以在向量中搜索您的值(这会告诉您值在向量中的位置),然后返回该位置之前和之后的值。 因此,搜索 45 会告诉您它应该位于 index=1 处,然后您将返回 0 和 1 (根据您的搜索实现,您将获得较小值的索引或较大值的索引,但这很容易通过几个边界条件进行检查)。 这应该能够在 O(log n) 中运行,其中 n 是向量中的元素数量。
You could do a search in your vector for your value (which would tell you where your value would be if it were in the vector) and then return the value before and after that location. So searching for 45 would tell you it should be at index=1 and then you would return 0 and 1 (depending on your implementation of the search, you'll either get the index of the smaller value or the index of the larger value, but this is easy to check with a couple boundary conditions). This should be able to run in O(log n) where n is the number of elements in your vector.
我会写这样的东西,没有测试它是否可以编译,但你明白了:
I would write something like this, didn't test if this compiles, but you get the idea:
我写了这个小函数,它似乎适合您想要的更一般的情况。 我还没有完全测试它,但我确实编写了一些测试代码(包含在内)。
I wrote up this little function, which seems to fit the more general case you wanted. I haven't tested it totally, but I did write a little test code (included).
根据 tunnuz 发布的代码,这里对边界检查进行了一些改进:
使用示例:
Based on the code that tunnuz posted, here you have some improvements regarding bound checking:
Example of usage:
如果您有能力使用其他数据结构(不是向量),我建议使用 B 树。 如果你的数据不变,我相信你可以在常数时间内检索结果(最坏情况下是对数时间)。
If you have the ability to use some other data structure (not a vector), I'd suggest a B-tree. If you data is unchanging, I believe you can retrieve the result in constant time (logarithmic time at the worst).