Клавиши с плавающей запятой в std: map

Ответ 1

Вы можете реализовать собственную функцию сравнения.

#include <functional>

class own_double_less : public std::binary_function<double,double,bool>
{
public:
  own_double_less( double arg_ = 1e-7 ) : epsilon(arg_) {}
  bool operator()( const double &left, const double &right  ) const
  {
    // you can choose other way to make decision
    // (The original version is: return left < right;) 
    return (abs(left - right) > epsilon) && (left < right);
  }
  double epsilon;
};
// your map:
map<double,double,own_double_less> mymap;

Обновлено: см. Пункт 40 в Эффективном STL ! Обновлено на основе предложений.

Ответ 2

Итак, есть несколько проблем с использованием удвоений в качестве ключей в std::map.

Во-первых, проблема NaN, которая сравнивается меньше, чем сама по себе. Если есть вероятность вставить NaN, используйте это:

struct safe_double_less {
  bool operator()(double left, double right) const {
    bool leftNaN = std::isnan(left);
    bool rightNaN = std::isnan(right);
    if (leftNaN != rightNaN)
      return leftNaN<rightNaN;
    return left<right;
  }
};

но это может быть слишком параноидально. Не повторяйте, не повторяйте, включите порог epsilon в вашем операторе сравнения, который вы передадите на std::set или тому подобное: это нарушит требования к порядку контейнера и приведет к непредсказуемому поведению undefined.

(я поместил NaN как больше, чем все double s, включая +inf, в моем порядке, без уважительной причины. Меньше, чем все double также будут работать).

Итак, используйте либо по умолчанию operator<, либо выше safe_double_less, или что-то подобное.

Далее я бы посоветовал использовать std::multimap или std::multiset, потому что вы должны ожидать нескольких значений для каждого поиска. Вы могли бы также сделать управление контентом повседневной практикой, а не угловым случаем, увеличить охват вашего кода. (Я бы редко рекомендовал эти контейнеры). Кроме того, это блокирует operator[], который не рекомендуется использовать, когда вы используете клавиши с плавающей запятой.

Точка, в которой вы хотите использовать epsilon, - это когда вы запрашиваете контейнер. Вместо использования прямого интерфейса создайте вспомогательную функцию следующим образом:

// works on both `const` and non-`const` associative containers:
template<class Container>
auto my_equal_range( Container&& container, double target, double epsilon = 0.00001 )
-> decltype( container.equal_range(target) )
{
  auto lower = container.lower_bound( target-epsilon );
  auto upper = container.upper_bound( target+epsilon );
  return std::make_pair(lower, upper);
}

который работает как в версиях std::map, так и std::set (и multi).

(В более современной базе кода я ожидал бы, что объект range<?> станет лучше возвращаться из функции equal_range, но на данный момент я сделаю его совместимым с equal_range).

Это находит ряд вещей, ключи которых "достаточно близки" к тому, который вы запрашиваете, в то время как контейнер сохраняет свои заказывающие гарантии внутри себя и не выполняет поведение undefined.

Чтобы проверить наличие ключа, сделайте следующее:

template<typename Container>
bool key_exists( Container const& container, double target, double epsilon = 0.00001 ) {
  auto range = my_equal_range(container, target, epsilon);
  return range.first != range.second;
}

и если вы хотите удалить/заменить записи, вы должны иметь дело с возможностью того, что может быть более одного попадания в запись.

Более короткий ответ: "не используйте значения с плавающей запятой в качестве ключей для std::set и std::map", потому что это немного хлопот.

Если вы используете клавиши с плавающей запятой для std::set или std::map, почти наверняка никогда не делайте на них .find или [], так как это очень вероятно, будет источником ошибок. Вы можете использовать его для автоматически отсортированной коллекции вещей, если точный порядок не имеет значения (то есть, что один конкретный 1.0 впереди или позади или точно на том же месте, что и другой 1.0). Даже тогда я бы пошел с мультимассой/мультимножеством, так как полагаться на столкновения или отсутствие этого не на что я бы положился.

Рассуждение о точном значении значений плавающей запятой IEEE затруднено, и хрупкость кода, основанного на нем, является обычным явлением.

Ответ 3

Как Naszta говорит, вы можете реализовать свою собственную функцию сравнения. То, что он оставляет вне, является ключом к тому, чтобы заставить его работать - вы должны убедиться, что функция всегда возвращает false для любых значений, которые находятся в пределах вашего допуска для эквивалентности.

return (abs(left - right) > epsilon) && (left < right);

Изменить: как указано во многих комментариях к этому ответу и другим, существует вероятность того, что это получится плохо, если значения, которые вы его кормите, произвольно распределены, потому что вы не можете гарантировать, что !(a<b) и !(b<c) результат !(a<c). Это не будет проблемой в вопросе, как было задано, потому что числа, о которых идет речь, группируются вокруг 0,1 приращений; пока ваш эпсилон достаточно велик, чтобы учитывать все возможные ошибки округления, но меньше 0,05, он будет надежным. Чрезвычайно важно, чтобы ключи к карте никогда не были ближе, чем на расстоянии 2 * эпсилон.

Ответ 4

Здесь упрощенный пример того, как использование soft-compare (aka epsilon или почти равно) может привести к проблемам.

Пусть epsilon = 2 для простоты. Поместите 1 и 4 в ваш map. Теперь это может выглядеть так:

1
 \
  4

Итак, 1 - это корень дерева.

Теперь введите числа 2, 3, 4 в этом порядке. Каждый заменит корень, потому что он сравнивается с ним. Итак, у вас есть

4
 \
  4

который уже нарушен. (Предположим, что попытка ребалансировки дерева не производится.) Мы можем продолжать работу с 5, 6, 7:

7
 \
  4

и это еще более нарушено, потому что теперь, если мы спросим, ​​есть ли там 4, он скажет "нет", и если мы попросим итератор для значений меньше 7, он не будет включать 4.

Хотя я должен сказать, что я использовал map на основе этого ошибочного оператора нечеткого сравнения несколько раз в прошлом, и всякий раз, когда я выкапывал ошибку, это никогда не происходило из-за этого. Это связано с тем, что наборы данных в моих областях приложений никогда не представляют собой стресс-тестирование этой проблемы.

Ответ 5

Использование удвоений в качестве ключей не полезно. Как только вы делаете какую-либо арифметику на клавишах, вы не знаете, какие точные значения у них есть и, следовательно, не могут использовать их для индексации карты. Единственное разумное использование заключается в том, что ключи являются постоянными.