Is there any explanation why find() algorithm doesn't work for maps and one have to use map::find instead?
+16
A:
- It does work on maps, but you need to compare against a
map::value_type(which isstd::pair<const map::key_type, map::mapped_type>), not the key type. - Because map.find takes a key and returns a key/value pair iterator.
MSN
2009-07-22 21:25:14
Just to clarify, map's `value_type_ is `pair<key_type, mapped_type>`.
Pavel Minaev
2009-07-22 21:31:21
According to the standard section 23.3.1, for a std::map<Key, T, Compare, Allocator>, key_type is Key, but value_type is pair<const Key, T>. The reason is that once the value has been inserted the key of insertion must be immutable, or else the order invariant could be broken
David Rodríguez - dribeas
2009-07-22 22:26:32
+4
A:
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).
Andy J Buchanan
2009-07-22 22:07:13
A custom operator== is neither allowed nor necessary. Use find_if innstead.
MSalters
2009-07-23 10:39:56
+1
A:
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.
navigator
2009-07-22 22:35:15
Are you sure about the linear walk? I thought that you'd get a log walk just fine, if you have random access iterators.
Andy J Buchanan
2009-07-22 22:38:59
if you have random access iterators, yes, but if not, you'll have to do linear number of steps. std::map does not provide random access iterators.
navigator
2009-07-22 22:41:44
Yep, you quite right on that point, forgot map's iterators are only bidirectional.
Andy J Buchanan
2009-07-22 23:52:19
+1
A:
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.
iain
2009-07-23 10:03:14
A:
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
find(mmap.begin(), mmap.end(), "value")
ilya1725
2010-09-03 18:27:47