Finding the closest or exact key in a std::map

Question

I need to create a lookup table which links a length to a time interval (both are of data type double). The keys increment linearly as they are inserted, so it will already be sorted (perhaps an unordered_map would be better?).

What I am looking for is a way to find a key that best matches the current length provided to get the time value, or even better find the two keys that surround the length (the given key is between them) so I can find the interpolated value between the two time values.

I also need the best performance possible as it will be called in real time.

EDIT: I would have rather the following was a comment to the first answer below, but the format is hard to read.

I tried to do the following, but it seems to return the same iterator (5.6):

std::map<double, double> map; map.insert(std::pair<double, double>(0.123, 0.1)); map.insert(std::pair<double, double>(2.5, 0.4)); map.insert(std::pair<double, double>(5.6, 0.8));  std::map<double, double>::iterator low, high; double pos = 3.0; low = map.lower_bound(pos); high = map.upper_bound(pos); 

How would I get 'low' to point to the last element that is < than the key used to search?

EDIT 2: Silly me, 'low--' will do it, providing it's not the first element.

Getting there :)

Answer 1

For this, you can use either std::map::lower_bound

Returns an iterator pointing to the first element that is not less than key.

or std::map::equal_range

Returns a range containing all elements with the given key in the container.

---

In your case, if you want the closest entry, you need to check both the returned entry and the one before and compare the differences. Something like this might work

std::map<double, double>::iterator low, prev; double pos = 3.0; low = map.lower_bound(pos); if (low == map.end()) {     // nothing found, maybe use rbegin() } else if (low == map.begin()) {     std::cout << "low=" << low->first << '\n'; } else {     prev = std::prev(low);     if ((pos - prev->first) < (low->first - pos))         std::cout << "prev=" << prev->first << '\n';     else         std::cout << "low=" << low->first << '\n'; } 

Answer 2

"best performance possible" - given you insert elements in increasing order, you can push_back/emplace_back them into a std::vector then use std::lower_bound - you'll get better cache utilisation because the data will be packed into contiguous address space.