Блог

Главная - Вопросы по программированию - Получить элемент, ближайший к значению в std::вектор двойников

Получить элемент, ближайший к значению в std::вектор двойников

#c 11 #double #precision #stdvector

Вопрос:

Есть ли в C 11 элегантный способ получить элемент из a std::vector из double s, который ближе всего к определенному значению?

Код:

 #include <iostream>
#include <vector>

double GetClosest(const std::vector<double>amp; 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;
}

Поскольку это a std::vector из double s, я думаю, что точность вступает в игру? Или можно ли сделать логику таким образом, чтобы не нужно было беспокоиться о точности?

Комментарии:

1. Не знаю, будет ли это лучше, но, поскольку вы говорите, что вектор отсортирован, возможно std::stable_partition , это было бы полезно или даже просто std::find_if() . Любой из них должен привести вас iterator к тому , где value логически будет находиться внутри vector , тогда вы можете посмотреть на два значения, окружающие это iterator , и посмотреть, какое из них ближе к value этому .

2. Похоже, мне нужно реализовать двойное сравнение в переданном предикате std::find_if() ?

Ответ №1:

Вы можете использовать std::partition_point std::lower_bound или std::upper_bound в отсортированном диапазоне.

Пример:

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

double GetClosest(const std::vector<double>amp; 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;
}

Комментарии:

1. Мило, не знал о std::partition_point()

2. @RemyLebeau Спасибо — я тоже не был 🙂

Ответ №2:

Поскольку vector все отсортировано, вы могли бы попробовать что-то вроде этого:

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

double GetClosest(const std::vector<double>amp; 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;
}
Метки: ,