std::set с функцией личного сравнения имеет идентичные значения

Я хочу сохранить объект std::set из Point3D, моя функция сравнения определяется следующим образом (лексикографический порядок):

bool operator<(const Point3D &Pt1, const Point3D &Pt2)
{
    const double tol = 1e-5;

    if(fabs(Pt1.x() - Pt2.x()) > tol)
    {
        return Pt1.x() < Pt2.x();
    }    
    else if(fabs(Pt1.y() - Pt2.y()) > tol)
    {
        return Pt1.y() < Pt2.y();
    }
    else if(fabs(Pt1.z() - Pt2.z()) > tol)
    {
        return Pt1.z() < Pt2.z();
    }
    else
    {
        return false;
    }
}

В некоторых случаях set содержит одинаковую точку, я думаю, проблема связана с функцией сравнения, но я не нахожу именно проблему. Любая помощь будет оценена по достоинству!


c++ stdset
person nathanael    schedule 09.06.2014    source источник
comment
Ваш оператор сравнения должен реализовать строгий слабый порядок: stackoverflow.com /вопросы/979759/   -  person EdChum    schedule 09.06.2014
comment
Итак, вопрос: как реализовать строгое слабое упорядочение с double и толерантностью?   -  person nathanael    schedule 09.06.2014
comment
Ну, ваш код в настоящее время проверяет только каждую координату x, y, z по отдельности, вам нужно проверить, меньше ли все, чем эпсилон, а затем вернуть false   -  person EdChum    schedule 09.06.2014
comment
@EdChum, но если все три различия меньше эпсилон, оператор возвращает false как есть.   -  person undermind    schedule 09.06.2014
comment
Это как бы точки в пространстве. Рассматривали ли вы возможность использования евклидова расстояния для упорядочения? Толерантность будет проще реализовать.   -  person    schedule 09.06.2014

Ответы (1)


arrow_upward
7
arrow_downward

Ваша концепция толерантности неправильно устанавливает строгий слабый порядок, поскольку он не является транзитивным. Для примера представьте, что допуск равен 1. Теперь рассмотрим:

a = 1
b = 2
c = 3

здесь: !(a<b) и !(b<c), но a<c. Это явное нарушение требования транзитивности для строгого слабого упорядочения.

Если вы хотите реализовать сравнение, которое имеет допуск, но которое также является строгим слабым порядком, вы должны последовательно округлить каждое значение (например, 1.5 => 2, 0.75 => 1, 2.3 => 2 и т. д.), а затем сравнить округленные значения.

Делать это кажется очень бессмысленным, так как double уже делают это, но с максимально возможной точностью. Вы по-прежнему будете вести себя странно, когда обнаружите, что 1.4999999... != 1.5.

Вы должны просто написать свой компаратор следующим образом и отказаться от концепции допуска:

bool operator<(const Point3D &Pt1, const Point3D &Pt2)
{
    //This can be replaced with a member/free function if it is used elsewhere
    auto as_tie = [](Point3D const &Pt) {
        //assumes the member functions return references
        //to the internal `Point3D` values.
        return std::tie(Pt.x(), Pt.y(), Pt.z());
    };
    return as_tie(Pt1) < as_tie(Pt2);
}

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

person Mankarse    schedule 09.06.2014
comment
В моем случае мне нужно использовать допуск и круглое значение непосредственно перед сравнением: static_cast<int>(xDouble*std::pow(10,nbDecimal)+0.5) для каждой координаты. - person nathanael; 09.06.2014