STL "ближайший" метод?

Question

Я ищу сортировку STL, которая возвращает элемент «ближайший» к целевому значению, если точное значение отсутствует в контейнере.Это должно быть быстро, так что по сути я ищу слегка модифицированный бинарный поиск ... Я мог бы написать это, но похоже, что то, что уже должно существовать ...

Answer 1

Вы имеете в виду функции lower_bound / upper_bound? Они выполняют бинарный поиск и возвращают ближайший элемент над искомым значением.

Пояснение: глобальные версии lower / upper_bound работают только в том случае, если диапазон отсортирован, так как они используют некоторый вид двоичного поиска внутри. (Очевидно, методы lower / upper_bound в std :: map всегда работают). В своем вопросе вы сказали, что ищете какой-то бинарный поиск, поэтому я предполагаю, что диапазон отсортирован.

Кроме того, ни lower_bound, ни upper_bound не возвращает ближайшего члена. Если значение X, которое вы ищете, не входит в диапазон, они оба вернут первый элемент больше X. В противном случае lower_bound вернет первое значение, равное X, upper_bound вернет последнее значение, равное X.

Итак, чтобы найти ближайшее значение, вам нужно будет

• звоните lower_bound
• если он возвращает конец диапазона, все значения меньше X. Последний (то есть самый высокий) элемент является ближайшим
• это если возвращает начало диапазона, все значения больше X. Первый (т.е. самый низкий) элемент является ближайшим
• если он возвращает элемент в середине диапазона, проверьте этот элемент и элемент перед ним - тот, который ближе к X, тот, который вы ищете

Answer 2

Итак, вы ищете элемент, который имеет минимальное расстояние от некоторого значения k?

Используйте std::transform для преобразования каждого x в x-k. Используйте std::min_element с функцией сравнения, которая возвращает abs(l) < abs(r). Затем добавьте k обратно к результату.

РЕДАКТИРОВАТЬ: В качестве альтернативы, вы можете просто использовать std::min_element с функцией сравнения abs(l-k) < abs(r-k), и исключить std::transform.

EDIT2: Это хорошо для несортированных контейнеров. Для отсортированных контейнеров вам, вероятно, нужен ответ nikie.

Answer 3

Если контейнер уже отсортирован (как подразумевается), вы сможете использовать std::upper_bound и элемент непосредственно перед ним, чтобы определить ближайший:

// Untested.
template <class Iter, class T>
Iter closest_value(Iter begin, Iter end, T value)
{
    Iter result = std::upper_bound(begin, end, value);
    if(result != begin)
    {
        Iter lower_result = result;
        --lower_result;
        if(result == end || ((value - *lower_result) < (*result - value)))
        {
            result = lower_result;
        }
    }

    return result;
}

Если контейнер не отсортирован,используйте min_element с предикатом, как уже предлагалось.

Answer 4

Если ваши данные не отсортированы, используйте std :: min_element с функтором сравнения, который вычисляет ваше расстояние.