CODEWITHSUNDEEP
c++
Rebirth
Rebirth

Reputation: 528

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

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 :)

Upvotes: 36

Views: 31374

Answers (8)

GPrathap
GPrathap

Reputation: 7800

I had to solve the same problem, however provided answers do not give me the correct answer. Here is a full example if someone wants

            template <typename T>
            class Key
            {
                public:
                    T x;
                    T y;
                    explicit Key(T x_, T y_): x(x_), y(y_){}
                    bool operator<( const Key<T> right) const{
                        if((x == right.x) && (y == right.y)){
                            return false;
                        }
                        return true;
                    }
                    T operator-( const Key<T> right) const{
                        return std::sqrt(std::pow(x-right.x, 2) + std::pow(y-right.y, 2));
                    }
            };

           int main(int argc, char **argv)
              {

                std::map<Key<double>, double> pixel_mapper;

                Key<double> k1(400,5);
                Key<double> k2(4,5);
                Key<double> k3(4,5);
                Key<double> k4(4667,5);
                Key<double> k5(1000,5);

                pixel_mapper.insert(std::pair<Key<double>, double>(k2, 5));
                pixel_mapper.insert(std::pair<Key<double>, double>(k3, 5));
                pixel_mapper.insert(std::pair<Key<double>, double>(k4, 5));
                pixel_mapper.insert(std::pair<Key<double>, double>(k1, 5));

                auto it = std::min_element( pixel_mapper.begin(), pixel_mapper.end(),
                      [&](const auto &p1, const auto &p2)
                      {
                        return std::abs(p1.first - k5) < std::abs(p2.first - k5);
                      });

                std::cout<< it->first.x << "," << it->first.y << std::endl;

                return 0;

                }

Here, we can use std:min_element to get the closest in case exact key is not present

Upvotes: 0

Tmotorhead
Tmotorhead

Reputation: 1

above is wrong. should be like this template 

typename std::map<T1, T2>::const_iterator nearest_key(const std::map<T1, T2>& map, T1 key)
{
    auto lower_bound = map.lower_bound(key);
    if (lower_bound == map.end()) return --lower_bound;
    auto upper_bound = lower_bound; upper_bound++;
    if (upper_bound == map.end()) return lower_bound;
    auto dist_to_lower = lower_bound->first - key;
    auto dist_to_upper = upper_bound->first - key;
    return (dist_to_upper < dist_to_lower) ? upper_bound : lower_bound;
}

Upvotes: 0

Bridge Dudley
Bridge Dudley

Reputation: 299

#include <map>

template <typename T1, typename T2>
std::map<T1, T2>::iterator nearest_key(const std::map<T1, T2>& map, T1 key) {
    auto lower_bound = map.lower_bound(key);
    auto upper_bound = lower_bound; upper_bound++;
    if (lower_bound == map.end()) return upper_bound;
    if (upper_bound == map.end()) return lower_bound;
    unsigned int dist_to_lower = std::abs((int)lower_bound->first - (int)key);
    unsigned int dist_to_upper = std::abs((int)upper_bound->first - (int)key);
    return (dist_to_upper < dist_to_lower) ? upper_bound : lower_bound;
}

Upvotes: 0

Andrej Debenjak
Andrej Debenjak

Reputation: 2122

Complete generic solution (original idea taken from Olaf Dietsche's answer):

#include <map>
#include <iostream>
#include <cstdint>

template <typename T1, typename T2>
T1 findClosestKey(const std::map<T1, T2> & data, T1 key)
{
    if (data.size() == 0) {
        throw std::out_of_range("Received empty map.");
    }

    auto lower = data.lower_bound(key);

    if (lower == data.end()) // If none found, return the last one.
        return std::prev(lower)->first;

    if (lower == data.begin())
        return lower->first;

    // Check which one is closest.
    auto previous = std::prev(lower);
    if ((key - previous->first) < (lower->first - key))
        return previous->first;

    return lower->first;
}

int main () {
double key = 3.3;

std::map<double, int> data = {{-10, 1000}, {0, 2000}, {10, 3000}};

std::cout << "Provided key: " << key << ", closest key: " << findClosestKey(data, key) << std::endl;
return 0;
}

Upvotes: 0

Olaf Dietsche
Olaf Dietsche

Reputation: 74018

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';
}

Upvotes: 43

jadhachem
jadhachem

Reputation: 1123

The functions std::lower_bound() and std::upper_bound() would be useful here.

lower_bound() gives the first element that is >= to the value you're looking for; upper_bound() gives the first element that is > than the value.

For instance, searching for the value 5 in the following list: {1,3,5,5,6}1 using lower_bound() returns the third element, while upper_bound() would return the fifth element. If the two functions return the same thing x, then the value you're looking for is not present in the list. The value just before it is x-1 and the value just after it is x.

1As pointed out by Tony D in a comment, the question asked for maps, which generally do not contain duplicate elements. I'm keeping this example though to illustrate the two functions.

Upvotes: 2

Tony Delroy
Tony Delroy

Reputation: 106066

"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.

Upvotes: 6

mths
mths

Reputation: 837

You could of course use lower_bound and upper_bound, which are logarithmic in runtime. And they should do what you want.

std::map<double,double>::iterator close_low;
//... your_map ...
close_low=your_map.lower_bound (current_length);

This should give you an iterator to the the first map element whose key is < current length. Do likewise with upper_bound and you have your time surrounded.

Upvotes: 3

Related Questions