Thread: Help w/sort and operator overloading

  1. #1
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391

    Help w/sort and operator overloading

    I'm able to sort any three given coordinates with respect to their reference angle by overlaoding the < operator like so:
    Code:
    // In coordinate class:
    
    bool operator<(const Coord& rhs){ return theta < rhs.theta; };
    
    // And now in main or elsewhere I can say:
    
    coordList.sort();
    which is good, except there are special cases where this won't work. One of those cases is if two coordinates have the same reference angle.

    My question is really what other operator can I overload to take care of this? Should I overload <=? ==?

    Also, I've had problems trying to add if-else statements in overloaded operators, any idea why that is?

    Like this:
    Code:
    operator <(const Coord& rhs){
    
        if(theta == something){
               // do this
        }
    
        else{ 
               // do something else
        }
    };
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    1. If the reference angles are equal, do you care what the sort order should be? If so, you just need to put more checks in your operator<.

    2. Theta is a float/double, right? Checking (theta==something) is a Bad Idea, since an infinite number of floating point values are not representable inside the computer, and errors can propagate if you even look at the numbers funny. If you want to check for "equality" of two floating-point numbers, you should check that their difference is less than some tolerance value. Something like this, maybe:
    Code:
    rel_diff = max(abs((a-b)/a), abs((a-b)/b));
    if (rel_diff < 1e-6) { // for a suitable value of 1e-6
        //stuff where "equal"
    } else {
        //stuff where not "equal"
    }

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by dudeomanodude View Post
    I'm able to sort any three given coordinates with respect to their reference angle by overlaoding the < operator like so:
    Code:
    // In coordinate class:
    
    bool operator<(const Coord& rhs){ return theta < rhs.theta; };
    
    // And now in main or elsewhere I can say:
    
    coordList.sort();
    which is good, except there are special cases where this won't work. One of those cases is if two coordinates have the same reference angle.
    If the angles are the same, you have to compare the coordinates. This has nothing to do with different operators. You just haven't finished implementing your operator<() properly.

    Also, I've had problems trying to add if-else statements in overloaded operators, any idea why that is?

    Like this:
    Code:
    operator <(const Coord& rhs){
    
        if(theta == something){
               // do this
        }
    
        else{ 
               // do something else
        }
    };
    For starters, there is no return type, and there is a spurious semicolon after the last brace. Nothing else looks wrong.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by tabstop View Post
    If you want to check for "equality" of two floating-point numbers, you should check that their difference is less than some tolerance value. Something like this, maybe:
    That's a major no-no in a sorting algorithm. This is one of the few cases where a check for exact equality is a proper thing to do.

    The problems with equality comparison of floats have to do with meaning. If two floats aren't equal (according to ==), does that really mean they aren't "equal" in a useful sense? It's an important question but one that doesn't really come up during sorting. You want a well-defined ordering of values, otherwise you can't sort consistently. You can't produce a well defined ordering by applying comparison tricks.

  5. #5
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    If you're sorting with std::sort(), instead of overloading operator<() you should just create a predicate function like this:
    Code:
    bool CoordLess( const Coord& lhs, const Coord& rhs )
    {
        return lhs.theta < rhs.theta;
    }
    Then pass it to sort()
    Code:
    std::vector<Coord> v;
    ...
    std::sort( v.begin(), v.end(), CoordLess );

  6. #6
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by brewbuck View Post
    That's a major no-no in a sorting algorithm. This is one of the few cases where a check for exact equality is a proper thing to do.

    The problems with equality comparison of floats have to do with meaning. If two floats aren't equal (according to ==), does that really mean they aren't "equal" in a useful sense? It's an important question but one that doesn't really come up during sorting. You want a well-defined ordering of values, otherwise you can't sort consistently. You can't produce a well defined ordering by applying comparison tricks.
    When comparing floating point numbers, shouldn't you test for equivalence rather than equality?
    Code:
    double d1, d2;
    ...
    if ( !(d1 < d2) && !(d2 < d1) )
    {
        // They're equivalent.
    }

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by brewbuck View Post
    That's a major no-no in a sorting algorithm. This is one of the few cases where a check for exact equality is a proper thing to do.

    The problems with equality comparison of floats have to do with meaning. If two floats aren't equal (according to ==), does that really mean they aren't "equal" in a useful sense? It's an important question but one that doesn't really come up during sorting. You want a well-defined ordering of values, otherwise you can't sort consistently. You can't produce a well defined ordering by applying comparison tricks.
    I guess I interpreted the question in context of "I have two coordinates with the 'same' reference angle, but my operator< isn't performing the secondary check and so my points get sorted backwards" rather than maybe a syntactic error. But your point that I may have introduced intransitivity is valid and that's a bad thing, so -- ignore everything I said.

  8. #8
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by cpjust View Post
    When comparing floating point numbers, shouldn't you test for equivalence rather than equality?
    You should test for equivalence in whatever sense you require. In this case, it is critically important that the comparison be consistent. The tolerance trick can blow up when sorting because it is not guaranteed by any standard that:

    b - a == -(a - b).

    At least for double precision. This is often the case when a and b have dramatically differing magnitudes.

    Therefore, the result of the sort can end up depending on the original ordering, which is probably bad.

    Code:
    double d1, d2;
    ...
    if ( !(d1 < d2) && !(d2 < d1) )
    {
        // They're equivalent.
    }
    I have never encountered an environment where that meant anything different than just "d1 == d2"

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    also, you can often centralize comparison by encapsulating it into a single function, eg:

    Code:
    int
    compare( Coord const & lhs, Coord const & rhs )
    {
    /*
    	if lhs is less than rhs return -1, else if rhs is less than lhs return 1, else return 0
    */	
    }
    
    inline
    bool
    operator < ( Coord const & lhs, Coord const & rhs )
    {
    	return compare( lhs, rhs ) < 0;
    }
    
    inline
    bool
    operator <= ( Coord const & lhs, Coord const & rhs )
    {
    	return compare( lhs, rhs ) <= 0;
    }
    
    inline
    bool
    operator == ( Coord const & lhs, Coord const & rhs )
    {
    	return compare( lhs, rhs ) == 0;
    }
    
    inline
    bool
    operator != ( Coord const & lhs, Coord const & rhs )
    {
    	return compare( lhs, rhs ) != 0;
    }
    
    inline
    bool
    operator > ( Coord const & lhs, Coord const & rhs )
    {
    	return compare( lhs, rhs ) > 0;
    }
    
    inline
    bool
    operator >= ( Coord const & lhs, Coord const & rhs )
    {
    	return compare( lhs, rhs ) >= 0;
    }
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  10. #10
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Wow! thanks for all the suggestions everyone.

    Sorry for the incomplete code on that last example of mine.

    The reason it's so imperative that everything be oriented in counter-clockwise fashion is because the fractal generation ultimately either goes outward from the triangle or inward, and there is a need to always be going in the same direction to keep track of that.

    Problems arise when reference angles are the same, like in the following coordinate pairs:
    Code:
    Coord1    Coord2
    (0, 0)       (100, 0)
    (5, 5)       (25, 25)
    (-100, 0)  (-10 0)
    //etc.
    It wouldn't matter if two coordinates had the same reference angle granted they were entered in by the user in the correct order, however this must be a fool-proof solution for me (or for my teacher I should say).

    So, if equal reference angles are found, another test must be applied to sort correctly. This is what I'd like to do:
    Code:
    bool operator<(const Coord& rhs){
    
        		if( theta == rhs.theta){
    
            		if( abs(x_coord) != abs(rhs.x_coord) ){
    
                		if( abs(x_coord) < abs(rhs.x_coord) ){
                     
                     		return theta < rhs.theta;
                		}
    
                		else{ return rhs.theta < theta; }
            		} 
    
            		// X-values are the same:
            		else{
    
                		if( y_coord < rhs.y_coord){
    
                    		return theta < rhs.theta;
                		}
    
                		else{ return rhs.theta < theta; }
            		}
        		}
    
        		else{ return theta < rhs.theta; }
    		}
    I don't need to worry about whether 2 coordinates are the same, that check is performed before sort() is called.

    But as you can see, it's a bit confusing to look at it this way.

    Any ideas?
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  11. #11
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by brewbuck View Post
    I have never encountered an environment where that meant anything different than just "d1 == d2"
    Scott Meyers seems to think there's a difference in chapter 19 of "Effective STL".
    He also claims that the standard associative containers compare using equivalence by doing:
    Code:
    if (!c.key_comp()(x, y) && !c.key_comp()(y, x) )

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by dudeomanodude View Post
    Wow! thanks for all the suggestions everyone.

    Sorry for the incomplete code on that last example of mine.

    The reason it's so imperative that everything be oriented in counter-clockwise fashion is because the fractal generation ultimately either goes outward from the triangle or inward, and there is a need to always be going in the same direction to keep track of that.

    Problems arise when reference angles are the same, like in the following coordinate pairs:
    Code:
    Coord1    Coord2
    (0, 0)       (100, 0)
    (5, 5)       (25, 25)
    (-100, 0)  (-10 0)
    //etc.
    But as you can see, it's a bit confusing to look at it this way.

    Any ideas?
    You don't want to do things backwards with all your if and else clauses -- you're always returning false, the way it is. Something like this:
    Code:
    if (theta != rhs.theta)
        return (theta < rhs.theta);
    if( abs(x_coord) != abs(rhs.x_coord) )
        return (x_coord < rhs.x_coord);
    /* only thing left to check is y. */
    return (y_coord < rhs.y_coord);
    Note that I don't need else's, since returns will end the function. Essentially you're defining a sort order (theta first, x second, y last); and the first condition that gives a difference, you return that comparison.

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I have never encountered an environment where that meant anything different than just "d1 == d2"
    There are environments where d1 == d2 is defined as "!(d1 relop d2) && !(d2 relop d1)".

    But the inverse isn't necessarily true. That is, if == is defined on its own, "!(d1 relop d2) && !(d2 relop d1)" does not imply "d1 == d2". Can happen if relop doesn't define a total ordering. For example, if relop defines an order not based on the full primary key, e.g. comparing persons by age.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    Use this: dudeomanodude's Avatar
    Join Date
    Jan 2008
    Location
    Hampton, VA
    Posts
    391
    Quote Originally Posted by tabstop View Post
    You don't want to do things backwards with all your if and else clauses -- you're always returning false, the way it is. Something like this:
    Code:
    if (theta != rhs.theta)
        return (theta < rhs.theta);
    if( abs(x_coord) != abs(rhs.x_coord) )
        return (x_coord < rhs.x_coord);
    /* only thing left to check is y. */
    return (y_coord < rhs.y_coord);
    Note that I don't need else's, since returns will end the function. Essentially you're defining a sort order (theta first, x second, y last); and the first condition that gives a difference, you return that comparison.
    Hey thanks. Yea, I wasn't sure about the way I had it, It certainly didn't make sense to return a theta that wasn't really less than the other. But what you have there certainly clears things up for me.
    Ubuntu Desktop
    GCC/G++
    Geany (for quick projects)
    Anjuta (for larger things)

  15. #15
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    There are environments where d1 == d2 is defined as "!(d1 relop d2) && !(d2 relop d1)".

    But the inverse isn't necessarily true. That is, if == is defined on its own, "!(d1 relop d2) && !(d2 relop d1)" does not imply "d1 == d2". Can happen if relop doesn't define a total ordering. For example, if relop defines an order not based on the full primary key, e.g. comparing persons by age.
    But I thought we were talkin' about doubles.

Popular pages Recent additions subscribe to a feed