Оба набора :: find и std :: find не могут найти только несколько двойных элементов в наборе

Question

Я разрабатываю большую базу кода и хотел использовать set-s из STL для хранения двойных элементов. Я просто провел несколько тестов и нашел что-то очень странное.

Вот мой исходный код

#include <iostream> 
#include <set> 
#include <numeric> 
#include <algorithm> 

int main() 
{ 
    double iter = 0.001; 
    int count = 0; 
    std::set<double> S; 

    while(count < 10) 
    { 
     S.insert(iter); 
     std::cout << "Inserted element is " << iter << std::endl; 
     iter += 0.001; 
     count++; 
    } 

    for (std::set<double>::iterator i = S.begin(); i != S.end(); i++) 
    { 
     double element = *i; 
     std::cout << "The element in the set is " << element << std::endl; 
    } 

    std::cout << "The count of the element to be found is " << S.count(0.009) << std::endl; 

    if (S.find(0.008) != S.end()) 
     std::cout << "set::find found it!" << std::endl; 
    else 
     std::cout << "set::find didn't find it!" << std::endl; 

    if (std::find(S.begin(), S.end(), 0.009) != S.end()) 
     std::cout << "std::find found it!" << std::endl; 
    else 
     std::cout << "std::find didn't find it!" << std::endl; 

    return 0; 
} 

Теперь, странная часть, что оба set::find и std::find могут не найти все элементы до 0.008, но не может найти что-либо после этого.

Выход я для приведенного выше кода показан ниже:

Inserted element is 0.001 
Inserted element is 0.002 
Inserted element is 0.003 
Inserted element is 0.004 
Inserted element is 0.005 
Inserted element is 0.006 
Inserted element is 0.007 
Inserted element is 0.008 
Inserted element is 0.009 
Inserted element is 0.01 
The element in the set is 0.001 
The element in the set is 0.002 
The element in the set is 0.003 
The element in the set is 0.004 
The element in the set is 0.005 
The element in the set is 0.006 
The element in the set is 0.007 
The element in the set is 0.008 
The element in the set is 0.009 
The element in the set is 0.01 
The count of the element to be found is 0 
set::find found it! 
std::find didn't find it! 

Обратите внимание, что я просил set::find найти 0.008 в то время как я просил как countstd::find и сосчитать и найти 0.009 соответственно. Я просто хотел узнать, почему я вижу такую ​​аномалию.

Следует также отметить, что функции find абсолютно не имеют проблем с поиском целочисленных элементов. Мне было интересно, является ли это проблемой double. Даже если это так, я не уверен, почему он может найти несколько элементов, но не все.

Я не уверен, что вызывает эту ошибку, но если это используется, я работаю над Mac OS X 10.10.3 с gcc 4.9.2.

Answer 1

Да это double «проблема» - когда вы последовательно добавить 0.001 к iter, ошибки округления могут накапливаться таким образом, что полученное значение не соответствует тому, что вы могли бы ожидать (например, ваш зашиты 0.008).

Поскольку set сортируется, вы можете использовать, например. lower_bound, чтобы найти ближайший элемент, а затем проверить с помощью некоторого допуска для различий. Например, проверка того, что абсолютная разница между найденным и ожидаемым значениями меньше суммы эпсилона. Есть сотни вопросов по S.O. о том, как точно реализовать сравнение ... например. here.

Другим вопрос, специфичный для использования чисел с плавающей точкой в ​​set является то, что вы не можете получить insert s считаются дубликатами, когда вы ожидаете их тоже, или с другой стороны insert может отказаться вставить два значения, которые вы не ожидали чтобы быть дублирующими, поскольку ошибки округления во время их генерации оставили их одинаковыми. Также возможно, чтобы порядок двух очень близких значений был обратным по сравнению с тем, что вы математически ожидали бы при точном вычислении.