为什么 STL 算法 find() 不适用于地图?
有没有任何解释为什么 find() 算法不适用于地图而必须使用 map::find 代替?
Is there any explanation why find() algorithm doesn't work for maps and one have to use map::find instead?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(5)
map::value_type
进行比较(即std::pair
),而不是密钥类型。map::value_type
(which isstd::pair<const map::key_type, map::mapped_type>
), not the key type.正如其他地方所指出的,它确实有效,但类型是键/值对,因此您需要提供一个函子/函数来进行比较。 (您也可以使用自定义运算符 ==() 重载来完成此操作,尽管我从未尝试过这样的事情)
但是您可能确实想使用映射成员函数 find() ,因为它会给出 O(logN )查找,算法 std::find() 的复杂度为 O(N)。
另外:我认为你也可以使用 std::equal_range/lower_bound/upper_bound() 与地图,这些也是 O(LogN)。
As noted elsewhere, it does work, but the type is the key/value pair, so you need to supply a functor/function to do the comparison. (You could probably do it with a custom operator==() overload too, though I've never tried such a thing)
However you probably do want to use the map member function find() anyway since it will give the O(logN) lookup, the algorithm std::find() is O(N).
Additional: I think you could also use std::equal_range/lower_bound/upper_bound() with a map ok, these are also O(LogN).
你的意思是 equal_range 吗? 对于映射,您应该使用成员函数 lower_bound、upper_bound 和 equal_range。 std 等效项可以提供对数比较,但它们需要线性时间来遍历容器的元素。
Do you mean equal_range? With a map, you should use the member functions lower_bound, upper_bound and equal_range. The std equivalents may provide logarithm number of comparisons, but they require linear time to walk over the elements of a container.
您应该阅读 Scott Meyers 所著的《Effective STL》,以获取有关此类主题的更多信息。
“第 43 条:优先选择成员函数而不是同名算法”
了解成员函数存在的原因以及为什么应该使用它。
You should read "Effective STL" by Scott Meyers for more info on subjects like these.
"Item 43: Prefer member functions to algorithms with the same name"
For why the member function exists and why you should use it.
Scott Meyers 还建议使用 STL 算法,而不是编写自己的循环(2001 年版第 43 条)。 对于简单类型,您应该能够使用
Scott Meyers also recommends using STL algorithms as opposed to writing your own loops (Item 43 in 2001 edition). For a simple type you should be able to use just