Элегантный способ найти ближайшую ценность в векторе сверху

Мне нужна функция, которая принимает вектор (предполагается, что он отсортирован) и значение, и возвращает самое близкое число, которое [edit] ~~больше~~ меньше или равно этому числу, предпочтительно используя алгоритм из STL. Я придумал решение, используя std:: lower_bound(), но он кажется клочковым и уродливым:

struct ClosestCmp {
    bool operator()(const int & x, const int & y) { return x > y; }
};

// vec is assumed to be sorted
int closest(const std::vector<int> & vec, int value)
{
    std::vector<int>::const_reverse_iterator cri =
        std::lower_bound(vec.rbegin(), vec.rend(), value, ClosestCmp());
    if (cri != vec.rend()) {
        return *cri;
    }
    return -1;
}

// ...
vec.push_back(1);
vec.push_back(2);
vec.push_back(4);
vec.push_back(5);
std::cout << closest(vec, 2) << "\n"; // Should ouput "2"
std::cout << closest(vec, 3) << "\n"; // Should ouput "2"
std::cout << closest(vec, 4) << "\n"; // Should ouput "4"

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

Ответы

Ответ 1

Вы можете использовать только std::lower_bound и std::upper_bound с бинарными предикатами, которые соответствуют порядку контейнера. Таким образом, вы не можете сортировать по <, а затем использовать другой бинарный предикат (скажем <= или >). Таким образом, ваш "kludge" на самом деле является правильной вещью. Сортированный вектор в обратном порядке - это критерии упорядочения, которые вы хотите использовать, чтобы найти элемент, который меньше или равен значению. (В противном случае, если вы действительно искали значение, большее или равное, вы могли бы просто использовать std::lower_bound.)

Ответ 2

Для напоминания:

std::lower_bound: возвращает первое значение, которое не сравнивается меньше
std::upper_bound: возвращает первое значение, которое сравнивается строго больше

Из вашего описания std::lower_bound уже выглядит как идеальная подгонка, что не так:

int closest(std::vector<int> const& vec, int value) {
 auto const it = std::lower_bound(vec.begin(), vec.end(), value);
 if (it == vec.end()) { return -1; }

 return *it;
}

См. Ideone:

int main() {
 std::vector<int> vec;
 vec.push_back(2);
 vec.push_back(4);

 std::cout << closest(vec, 2) << "\n";
 std::cout << closest(vec, 3) << "\n";
 std::cout << closest(vec, 4) << "\n";
}

Вывод:

2
4
4

Ответ 3

Что-то вроде этого будет работать... Принимает наименьшее ближайшее значение:

Может быть сделано в виде шаблона или что-то вместо этого для тех, кто понимает программирование шаблонов. http://ideone.com/ff46ax

#include <iostream>
#include <vector>
#include <map>
#include <stdlib.h>

int main()
{
    int comparevalue = 3;
    typedef std::vector<int> intvec;
    intvec myvec;

    myvec.push_back(1);
    myvec.push_back(2);
    myvec.push_back(4);
    myvec.push_back(5);
    myvec.push_back(6);
    myvec.push_back(7);

    typedef std::map<int, int> intmap;
    intmap mymap;

    for (intvec::const_iterator itr = myvec.begin(); itr != myvec.end(); ++itr)
        mymap.insert(std::make_pair(abs(*itr-comparevalue), *itr));

    std::cout << "difference:" << mymap.begin()->first << "\n";
    std::cout << "value:" << mymap.begin()->second;
    return 0;
}

Ответ 4

Требуется С++ 11:

template<typename InputIterator, typename ValueType>
InputIterator closest(InputIterator first, InputIterator last, ValueType value)
{
    return std::min_element(first, last, [&](ValueType x, ValueType y)
    {   
        return std::abs(x - value) < std::abs(y - value);
    });
}

Ответ 5

Для наибольшего, которое меньше или равно, можно использовать эту функцию

int closest(std::vector<int> const& vec, int value) {
    auto const it = std::lower_bound(vec.begin(), vec.end(), value);
    if (it == vec.begin()) { return -1; }
    else return *(it - 1);
}