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

Question

Мне нужна функция, которая берет вектор (предположительно отсортированный) и значение и возвращает ближайшее число, которое [править] больше меньше или равно этому числу, предпочтительно используяалгоритм из 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, но не смог найти лучшего решения, чем это.

Answer 1

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

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

Который используется как:

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

Answer 2

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

Answer 3

Требуется C ++ 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);
    });
}

Answer 4

Примерно так будет работать .... Принимает наименьшее ближайшее значение:

Может быть сделано в виде шаблона или чего-то подобного для тех, кто разбирается в программировании шаблонов.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;
}

Answer 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);
}