# Thread: Help w/sort and operator overloading

1. ## 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
}
};```

2. 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. Originally Posted by dudeomanodude
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. Originally Posted by tabstop
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. 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. Originally Posted by brewbuck
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. Originally Posted by brewbuck
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. Originally Posted by cpjust
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. 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;
}```

10. 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?

11. Originally Posted by brewbuck
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. Originally Posted by dudeomanodude
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. 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.

14. Originally Posted by tabstop
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.

15. Originally Posted by CornedBee
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