Удаление повторяющихся элементов без округления, C++

Я пытаюсь удалить повторяющиеся элементы из вектора, используя следующий компаратор

            bool operator() ( const Point * p1, const Point * p2 ) const
            {
                    return ( p1->X() < p2->X() ) || ( ( p1->X() == p2->X() ) && ( p1->Y() < p2-Y() ) );
            }

и перегружен оператор ==

bool Point::operator == ( const Point &p ) const
{
    return ( x - p.x ) * ( x - p.x ) + ( y - p.y ) * ( y - p.y ) < DIFF;
}

схема удаления:

std::sort ( it_begin, it_end, Comp );
Points::iterator i_new_end = std::unique ( it_begin, it_end, Uniq);
items.erase ( i_new_end, this->items.end() );

Однако есть проблема с данными. Точки отсортированы по координате x

-0.0000000015   -6281103.8487118632   0.0000000000
-0.0000000011   -5993359.5353725236   0.0000000000
-0.0000000010   -5523510.0253371494   0.0000000000
-0.0000000009   -4885831.4582128422   0.0000000000
-0.0000000009   -4099699.3745807474   0.0000000000
-0.0000000008   -3189000.0000000000   0.0000000000
-0.0000000008   -2181404.4741311157   0.0000000000
-0.0000000008   -1107528.0771596823   0.0000000000 //unique
-0.0000000008   -0.0000000005   0.0000000000
-0.0000000007   1107528.0771596811   0.0000000000  //unique
-0.0000000007   2181404.4741311143   0.0000000000
-0.0000000007   3188999.9999999991   0.0000000000
-0.0000000006   4099699.3745807474   0.0000000000
-0.0000000006   4885831.4582128404   0.0000000000
-0.0000000005   5523510.0253371485   0.0000000000
-0.0000000004   5993359.5353725236   0.0000000000
0.0000000000   -6281103.8487118632   0.0000000000
0.0000000004   5993359.5353725236   0.0000000000
0.0000000005   5523510.0253371485   0.0000000000
0.0000000006   4099699.3745807474   0.0000000000
0.0000000006   4885831.4582128404   0.0000000000
0.0000000007   1107528.0771596811   0.0000000000
0.0000000007   2181404.4741311143   0.0000000000
0.0000000007   3188999.9999999991   0.0000000000
0.0000000008   -3189000.0000000000   0.0000000000
0.0000000008   -2181404.4741311157   0.0000000000
0.0000000008   -1107528.0771596823   0.0000000000
0.0000000008   -0.0000000005   0.0000000000
0.0000000009   -4885831.4582128422   0.0000000000
0.0000000009   -4099699.3745807474   0.0000000000
0.0000000010   -5523510.0253371494   0.0000000000
0.0000000011   -5993359.5353725236   0.0000000000
0.0000000015   -6281103.8487118632   0.0000000000
0.0089638987   -6377999.9999999991   0.0000000000

Оператор == не дает никакого эффекта, соседние точки не сортируются рядом друг с другом...

Есть ли возможность удалить такие повторяющиеся точки БЕЗ округления (например, компаратора diffrenet)? Я знаю, что координаты имеют много знаков после запятой...


c++ duplicates comparator
person Robo    schedule 16.03.2011    source источник
comment
Используете ли вы контейнеры STL? Если это так, вы должны определить оператор‹, а не оператор ==   -  person Dima    schedule 16.03.2011
comment
Как вы используете операторы?   -  person    schedule 16.03.2011

Ответы (4)


arrow_upward
0
arrow_downward

Оператор == не дает никакого эффекта, соседние точки не сортируются рядом друг с другом...

Если тип x и y — float или double, то равенство не может быть надежно установлено.

Попробуйте использовать numeric_limits<double>::epsilon() или numeric_limits<float>::epsilon() при сравнении!

Является ли DIFF в вашей реализации равным numeric_limits<T>::epsilon()? (где T — тип данных: float или double)

person Nawaz    schedule 16.03.2011
comment
И поэтому он делает сравнение с тем, что кажется константой, DIFF - person Erik; 16.03.2011
comment
@Arkadiy: Я думаю, он хотел удалить дубликаты с помощью std::unique(), а для этого нужен ==. - person Nawaz; 16.03.2011
comment
Вы правы - я не знал, что его оператор () используется как ‹. Извини. - person ; 16.03.2011

arrow_upward
1
arrow_downward

std::sort нужен оператор ‹, а не оператор ==

person Community    schedule 16.03.2011

arrow_upward
0
arrow_downward

std::sort использует operator<. std::unique использует operator==.

В STL существует различие между равенством, определяемым с помощью operator==, и эквивалентностью, определяемым с помощью operator<:

Два объекта эквивалентны, если ни один из них не предшествует другому в некотором интересующем порядке. Часто эквивалентные значения равны, но не всегда. Например, строки «STL» и «stl» эквивалентны при сортировке без учета регистра, но они определенно не равны. Для получения подробной информации о различии между эквивалентностью и равенством обратитесь к любому хорошему справочнику по STL. В разделе «Эффективный STL» этот вопрос рассматривается в пункте 19.

http://drdobbs.com/184401469#1

person Dima    schedule 16.03.2011

arrow_upward
0
arrow_downward

Думаю, вы столкнулись с неразрешимой проблемой. Стандартный алгоритм сортировки требует оператора упорядочивания, который определяет строгое упорядочивание. И нет возможности реализовать это с "нечеткими" отношениями. Лучше всего определить ваши отношения в том же духе, что и ваш ==, но без эпсилон:

inline double mag2( Point const& p )
{
    return p.X() * p.X() + p.Y() * p.Y();
}

bool operator()( Point const* lhs, Point const* rhs )
{
    return mag2( *lhs ) < mag2( *rhs );
}

(Добавление эпсилон в любом месте приведет к тому, что порядок отношений перестанет быть строгим и приведет к неопределенному поведению в алгоритме сортировки.)

person James Kanze    schedule 16.03.2011