Menu
Is there an equivalent version of std::find(first, last) but for a std::map? I.e., is there a version of std::map's find method that searches for an element in a map, but restricting the search only to a specified [first, last) range? Ideally, the solution should be logarithmic in the size of [first, last).
From what I've seen, std::map::find itself doesn't support this functionality (it always searches the whole map).
300
map find() function in C++ STL If the key is not present in the map container, it returns an iterator or a constant iterator which refers to map. end(). Time Complexity for Searching element : The time complexity for searching elements in std::map is O(log n).
To check for the existence of a particular key in the map, the standard solution is to use the public member function find() of the ordered or the unordered map container, which returns an iterator to the key-value pair if the specified key is found, or iterator to the end of the container if the specified key is not ...
Note: unordered_map container performs faster than map when they have to access an individual element by their key.
You can use std::lower_bound, std::upper_bound or std::equal_range for that as std::map iterators and data in the map satisfy the requirement for those functions, though you should be aware that it will be less efficient than std::map::find() due to linear iterator increments.
From std::lower_bound documentation
The number of comparisons performed is logarithmic in the distance between first and last (At most log 2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.
emphasis is mine.
65
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
