Manière élégante pour trouver la valeur la plus proche dans un vecteur d'en haut

J'ai besoin d'une fonction qui prend un vecteur (supposé être triés), et une valeur, et retourne le nombre le plus proche c'est [edit] supérieur inférieur ou égal à ce nombre, de préférence à l'aide d'un algorithme à partir de la STL. J'ai trouvé une solution en utilisant std::lower_bound(), mais il semble encombrants et vilaine:

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"

Quelqu'un peut-il suggérer une façon plus élégante, peut-être l'aide d'un STL algorithme sans avoir besoin d'une fonction de comparaison ou un itérateur inverse? J'ai regardé dans la STL, mais je n'ai pas été en mesure de trouver une meilleure solution que ce.

source d'informationauteur josmith42

  1. 4

    Vous ne pouvez utiliser std::lower_bound et std::upper_bound avec des prédicats binaires qui correspondent à l'ordre du conteneur. Donc, vous ne pouvez pas trier par < et ensuite utiliser un autre prédicat binaire (dire <= ou >). Donc votre "quelque chose" est en fait la bonne chose à faire. Le vecteur trié dans le sens inverse est l'ordonnancement des critères que vous souhaitez utiliser pour trouver l'élément inférieur ou égal à la valeur. (Sinon, si vous étiez vraiment à la recherche pour la valeur supérieure ou égale à, vous pouvez simplement utiliser std::lower_bound.)

  2. 15

    Pour rappel:

    • std::lower_bound: retourne la première valeur qui ne se compare pas moins
    • std::upper_bound: retourne la première valeur qui compare strictement plus grand

    À partir de votre description, std::lower_bound ressemble déjà à un ajustement parfait, ce qui est erroné avec:

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

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

    De sortie:

    2
4
4
  3. 2

    Quelque chose de ce genre.... Prend la plus petite valeur la plus proche:

    Pro pourrait être un modèle ou quelque chose à la place de ceux qui comprennent le modèle de programmation. 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. 1

    Nécessite 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);
    });
}
  5. 0

    Pour le plus grand qui est inférieur ou égal on peut utiliser cette fonction

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