当前位置：文江博客话题详情

针对结束迭代器测试 lower_bound 的返回值

发布于 2024-12-25 12:54:51 字数 176 浏览 2 评论 0原文

在 Scott Meyers 的 effective STL（第 195 页）中，有这样一行：

“必须测试 lower_bound 的结果，看看它是否指向您要查找的值。与 find 不同，您不能只测试 lower_bound 的返回值针对结束迭代器。”

谁能解释为什么你不能这样做？似乎对我来说效果很好。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

好久不见√ 2025-01-01 12:54:51

它对你来说效果很好，因为你的元素已经存在。

lower_bound 返回一个迭代器，指向第一个不小于给定值的元素，upper_bound 返回一个迭代器，指向第一个大于的元素/em> 大于给定值。

给定数组 1, 2, 3, 3, 4, 6, 7，lower_bound(..., 5) 将返回一个指向 6 的迭代器。

因此，两个检查值是否存在的方法：

使用equal_range也获取upper_bound（分别计算lower_bound和upper_bound 可能不是最优的）。如果边界之间的 std::distance 大于 0，则该元素存在。
<前><代码>1, 2, 3, 3, 4, 6, 7
std::distance(std::lower_bound(v.begin(),v.end(),5), std::upper_bound(v.begin(),v.end(),5)) == 0 // 6 缺席
std::distance(std::lower_bound(v.begin(),v.end(),3), std::upper_bound(v.begin(),v.end(),3)) == 2 // 3 存在
将迭代器指向的元素与您的值进行比较（假设运算符 != 和 < 是一致的），但您必须确保它不会返回结束迭代器。
```
*(std::lower_bound(v.begin(), v.end(), 5)) != 5
```

此外，由于 lower_bound 是二分搜索算法，因此如果未找到元素，则返回 end 会不一致。实际上，该算法返回的迭代器可以用作后续插入操作的提示。

It works fine for you because your element is present.

lower_bound returns an iterator to the first element not less than the given value, and upper_bound returns an iterator to the first element greater than the given value.

Given the array 1, 2, 3, 3, 4, 6, 7, lower_bound(..., 5) will return an iterator pointing to 6.

Hence, two ways of checking whether the value is present:

Use equal_range to also get the upper_bound (computing separately lower_bound and upper_bound will probably be suboptimal). If the std::distance between the bounds is greater than 0 then the element is present.

1, 2, 3, 3, 4, 6, 7
std::distance(std::lower_bound(v.begin(),v.end(),5), std::upper_bound(v.begin(),v.end(),5)) == 0 // 6 is absent
std::distance(std::lower_bound(v.begin(),v.end(),3), std::upper_bound(v.begin(),v.end(),3)) == 2 // 3 is present

Compare the element pointed by the iterator with your value (provided operators != and < are coherent), but you have to make sure it does not return the end iterator.
```
*(std::lower_bound(v.begin(), v.end(), 5)) != 5
```

Additionally, since lower_bound is a binary search algorithms it would be inconsistent to return end if the element was not found. Actually, the iterators returned by this algorithm can be used as a hint for a subsequent insertion operation for example.

回复收藏 0 原文

~没有更多了~