c++ - una - Manera elegante de encontrar el valor más cercano en un vector desde arriba

imprimir un arreglo en c

Question

Necesito una función que tome un vector (se supone que está ordenado) y un valor, y devuelve el número más cercano que es [edit] mayor que menor o igual que ese número, preferiblemente usando un algoritmo de la STL. He encontrado una solución usando std :: lower_bound (), pero parece desagradable y feo:

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"

¿Alguien puede sugerir una forma más elegante, tal vez usando un algoritmo STL sin necesidad de una función de comparación o un iterador inverso? He buscado en el STL, pero no he podido encontrar una solución mejor que esta.

Answer 1

Algo como esto funcionaría ... Toma el valor más cercano más cercano:

Podría hacerse fácilmente como una plantilla o algo para aquellos que entienden la programación de plantillas. 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 2

Para el mayor que sea menor o igual se puede usar esta función.

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

Answer 3

Para recordar:

• std::lower_bound : devuelve el primer valor que no se compara menos
• std::upper_bound : devuelve el primer valor que se compara estrictamente mayor

Desde su descripción, std::lower_bound ya parece el ajuste perfecto, lo que está mal con:

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

Que se utiliza como:

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

Salida:

2
4
4

Answer 4

Requiere 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 5

Solo puede usar std::lower_bound y std::upper_bound con predicados binarios que coinciden con el orden del contenedor. Por lo tanto, no puede ordenar por < y luego usar un predicado binario diferente (diga <= o > ). Así que su "kludge" es en realidad lo correcto a hacer. El vector ordenado a la inversa es el criterio de ordenación que desea utilizar para encontrar el elemento menor o igual al valor. (De lo contrario, si realmente estuviera buscando el valor mayor o igual que, simplemente podría usar std::lower_bound ).