2

I'm having a map<double, unique_ptr<Item>>. I would like to search this map, to find the item where a computed value is closest to the search value. The computed value can be generated by Item::compute which is a length computation, that I would like avoid doing for all elements. It can be assumed that this map is already ordered according to the results of the compute function.

So I thought that I could make a binary search, but the problem is, that I cannot really jump to the nth element in the map, since it is a map and not a vector. More specifically, I would need to get the middle item between two arbitrary items in the map. Is that possible? Is there a way an efficiant way to perform binary search within a map?

basilikum
  • 10,378
  • 5
  • 45
  • 58
  • 1
    If the data structure doesn't support random access to any element, then we cannot perform binary search on it. – Rohith R Oct 15 '16 at 13:34

1 Answers1

4

Use either the lower_bound() or the upper_bound() std::map methods. See the std::map documentation for both of these methods, that find an existing key nearest to the search key, if one does not exist. You don't need to code the binary search yourself, these methods do it for you.

Although using double as a map key is problematic, of course, I guess that using lower_bound() or upper_bound() might produce reasonable results, in this use case.

Community
  • 1
  • 1
Sam Varshavchik
  • 114,536
  • 5
  • 94
  • 148
  • Thanks! But as far as I understand, the lower_bound() and upper_bound() functions compare entries based on their key but I need to compare them based on their value. Is there a way to do that? – basilikum Oct 15 '16 at 14:39
  • No. That was unclear. The whole purpose of the map is look up values by their keys. If you want to search for values, swap the map, make it a`map, double, ptr_comparator>`, define and implement `ptr_comparator` as strict weak ordering for `unique_ptr`, and then use `lower_bound()` and `upper_bound()` with that map. – Sam Varshavchik Oct 15 '16 at 15:26