Премахване на дублирани елементи без закръгляване, 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

Операторът == не води до никакъв ефект, близките точки не се сортират една до друга...

Има ли някаква възможност за премахване на такива дублирани точки БЕЗ закръгляване (например дифренет компаратор)? Знам, че координатите имат много знаци след десетичната запетая...


c++ duplicates comparator
person Robo    schedule 16.03.2011    source източник
comment
Използвате ли STL контейнери? Ако е така, трябва да дефинирате operator‹, а не operator==   -  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. В Effective 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