Поиск ближайшего или точного ключа в std:: map

Мне нужно создать таблицу поиска, которая связывает длину с интервалом времени (оба имеют тип данных double). Клавиши линейно увеличиваются, когда они вставлены, поэтому он уже будет отсортирован (возможно, неупорядоченный_мап будет лучше?).

То, что я ищу, - это способ найти ключ, который наилучшим образом соответствует текущей длине, предоставленной для получения значения времени, или даже лучше найти две клавиши, которые окружают длину (данный ключ находится между ними), поэтому я могу найдите интерполированное значение между двумя значениями времени.

Мне также нужна лучшая производительность, так как она будет вызываться в режиме реального времени.

EDIT: я бы предпочел следующее: комментарий к первому ответу ниже, но формат трудно читать.

Я попытался сделать следующее, но, похоже, возвращает тот же итератор (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);

Как бы я получил "низкий", чтобы указать на последний элемент, который равен < чем ключ, используемый для поиска?

ИЗМЕНИТЬ 2: Глупый, "низкий", сделает это, не придавая ему не первого элемента.

Как добраться:)

Ответ 1

Для этого вы можете использовать std::map::lower_bound

Возвращает итератор, указывающий на первый элемент, который не меньше ключа.

или std::map::equal_range

Возвращает диапазон, содержащий все элементы с заданным ключом в контейнере.

В вашем случае, если вам нужна самая близкая запись, вам нужно проверить как возвращенную запись, так и предыдущую и сравнить различия. Что-то вроде этого может работать

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

Ответ 2

"максимально возможная производительность" - если вы вставляете элементы в возрастающем порядке, вы можете push_back/emplace_back их в std::vector затем использовать std::lower_bound - вы получите лучшее использование кэша, потому что данные будут упакованы в непрерывное адресное пространство,

Ответ 3

Конечно, вы можете использовать lower_bound и upper_bound, которые являются логарифмическими во время выполнения. И они должны делать то, что вы хотите.

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

Это должно дать вам итератор первому элементу карты, ключ которого < текущая длина. Аналогично используйте upper_bound, и у вас есть время, окруженное.

Ответ 4

Функции std::lower_bound() и std::upper_bound() было бы полезно здесь.

lower_bound() дает первому элементу >= значение, которое вы ищете; upper_bound() дает первый элемент >, чем значение.

Например, поиск значения 5 в следующем списке: {1,3,5,5,6} ¹ с помощью lower_bound() возвращает третий элемент, а upper_bound() возвращает пятый элемент. Если две функции возвращают одну и ту же вещь x, то значение, которое вы ищете, отсутствует в списке. Значение перед x-1 и значением сразу после x.

¹_{Как указано в комментарии Tony D, вопрос задан для карт, которые обычно не содержат дубликатов элементы.
Я придерживаюсь этого примера, хотя для иллюстрации двух функций.}

Ответ 5

Полное общее решение (оригинальная идея взята из ответа Олафа Дитче):

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

Ответ 6

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