Get item closest to a value in a std::vector of doubles

user_6626554 0
Viewed 61

Is there an elegant way in C++ 11 to get the item from a std::vector of doubles which is closest to a certain value?

Code:

#include <iostream>
#include <vector>

double GetClosest(const std::vector<double>& vec, double value) {
    // How to get the item closest to "value" from the items in vec. Vec is assumed to be sorted.
}

int main() {
    std::vector<double> my_doubles_vec;
    my_doubles_vec.push_back(101480.76915103197);
    my_doubles_vec.push_back(101480.85708367825);
    my_doubles_vec.push_back(101480.93293087184);
    my_doubles_vec.push_back(101481.0027936101);
    my_doubles_vec.push_back(101481.5625);
    my_doubles_vec.push_back(101481.5626);


    std::cout.precision(17);
    std::cout << GetClosest(my_doubles_vec, 101480.76915103201) << std::endl; // Should output "101480.76915103197"
    std::cout << GetClosest(my_doubles_vec, 101480.93293086279) << std::endl; // Should output "101480.93293087184"
    std::cout << GetClosest(my_doubles_vec, 101481.5625) << std::endl; // Should output "101481.5625"

    return 0;
}

Since its a std::vector of doubles, I think precision comes into play? Or can the logic be made in such a way that one doesn't need to bother about precision?

precision stdvector double c++11
2 Answers

You could use std::partition_point, std::lower_bound or std::upper_bound on the sorted range.

Example:

#include <algorithm>
#include <cmath>
#include <stdexcept>

double GetClosest(const std::vector<double>& vec, double value) {
    if(vec.empty()) throw std::runtime_error("no elements");

    // partition_point is the most generic of the three:
    auto it = std::partition_point(vec.begin(), vec.end(), [value](double v) {
        return v < value;
    });
    // or auto it = std::lower_bound(vec.begin(), vec.end(), value);
    // or auto it = std::upper_bound(vec.begin(), vec.end(), value);

    if(it == vec.end()) --it;      // value larger than the largest in the vector
    else if( it != vec.begin()) {  // value not less than first
        // check which one of the two around the partition point that is closest
        if(std::abs(*std::prev(it) - value) < std::abs(*it - value)) --it;
    }

    return *it;
}
user_75822470

Since the vector is sorted, you could try something like this:

#include <algorithm>
#include <cmath>
#include <stdexcept> 

double GetClosest(const std::vector<double>& vec, double value) {
    if (vec.empty()) throw std::invalid_argument("vector cant be empty");
    if (vec.size() == 1) return vec[0];
    auto iter = std::find_if(vec.begin(), vec.end(),
        [=](double d){ return d >= value; }
    );
    if (iter == vec.begin()) return vec.front();
    if (iter == vec.end()) return vec.back();
    if (std::abs(value - *(iter-1)) < std::abs(value - *iter)) --iter;
    return *iter;
}
user_658630
Related