🔒 Locked

C++ arbitrarily sorting a struct

Started by DanBerliner Dec 17, 2012 at 2:23 AM 8 replies 2.1k views

Original Post

Dec 17, 2012 at 2:23 AM

I'm currently making a scrabble like game, the AI is the topic of this week. Basically the computer goes though and finds every possible place it can make a move. I handle this data with the below struct
[source lang="cpp"]struct Move{
int startx,starty, score, dir;
std::string word;
};
[/source]

While the string and score are there for later reasons, any object with the same starting points and direction must be the same word. My algorithm for finding possible moves takes on duplicates so I'm using std::set to store it. To do this, however, I need a way to compare one Move from another. Dir ranges from 0-1, startx and starty both range from 0 to 15 (in theory they can be expanded, unlikely ever more than 100 though). Here is what I am currently using

[source lang="cpp"]bool operator<(const Move &a, const Move &b){
return (a.dir + a.startx*10 + a.starty*1000) < (b.dir + b.startx*10 + b.starty*1000);
}[/source]

As long as the starting X position is under 100 I don't see any way to produce false-duplicates.

Is there a better way to do this?

wqking

Dec 17, 2012 at 2:29 AM

[source]if(a.dir > b.dir) {
return false;
}
if(a.startx > b.startx) {
return false;
}
if(a.starty > b.starty) {
return false;
}
return true;
[/source]
Not sure if it's want you want.
My code returns true only whan a's all fields are less than b's

DanBerliner

Dec 17, 2012 at 3:02 AM

That's roughly the same idea, I like your approach better. Thanks.

The exact order it sorts in is unimportant, it just needs some way to do so.

SiCrane

Dec 17, 2012 at 3:47 AM

My code returns true only whan a's all fields are less than b's

This isn't a legal comparison for use with std::set. A valid comparison needs to be a strict weak ordering. One of the properties of a strict weak ordering is that if you have three objects A, B and C if A and B are equivalent and B and C are equivalent then A and C must also be equivalent. However, with this kind of comparison this property doesn't hold. One way to do this is to use a lexicographical comparison. Ex:


 if (a.dir < b.dir) return true;
 if (a.dir > b.dir) return false;
 if (a.startx < b.startx) return true;
 if (a.startx > b.startx) return false;
 return a.starty < b.starty;

DanBerliner

Dec 17, 2012 at 3:54 AM

[quote name='wqking' timestamp='1355711372' post='5011470']
My code returns true only whan a's all fields are less than b's


 if (a.dir < b.dir) return true;
 if (a.dir > b.dir) return false;
 if (a.startx < b.startx) return true;
 if (a.startx > b.startx) return false;
 return a.starty < b.starty;

[/quote]

Interesting, thanks for sharing.

alvaro

Dec 17, 2012 at 4:27 AM

I do it like this (just a bit more compact):

if (a.dir != b.dir) return a.dir < b.dir;
 if (a.startx != b.startx) return a.startx < b.startx;
 return a.starty < b.starty;

EDIT: Or even this:

return a.dir != b.dir ? a.dir < b.dir
 : a.startx != b.startx ? a.startx < b.startx
 : a.starty < b.starty;

BeerNutts

Dec 18, 2012 at 4:50 PM

EDIT: Or even this:
?
1
2
3
return a.dir != b.dir ? a.dir < b.dir
: a.startx != b.startx ? a.startx < b.startx
: a.starty < b.starty;

What's the point? It's much more complicated to read with no processing time benefit.

Cornstalks

Dec 18, 2012 at 5:00 PM

If you're using C++11, there's [font=courier new,courier,monospace]std::tie[/font] and you can just do:


 return std::tie(a.dir, a.startx, a.starty) < std::tie(b.dir, b.startx, b.starty);

alvaro

Dec 18, 2012 at 7:27 PM

What's the point? It's much more complicated to read with no processing time benefit.

Of course there is no processing time benefit, but I would argue that it is [slightly] less complicated.

if' is used to change program flow conditionally, but here we are only using if' to return one value or another. Using a single `return' and the ternary operator expresses this better. The structure of (condition1 ? value1 : condition2 ? value2 : value_else) is identical to a chain of if-else statements, and it's equally readable if you get used to it.

I concede that people are often more familiar with if-else than with chains of ternary operators, so perhaps in practice the other solution is better. But perhaps we can educate code readers a bit too...

Perhaps better formatting would make my code more clear. Wikipedia has this example of very readable use of concatenated ternary operators:

vehicle = arg == 'B' ? bus :
 arg == 'A' ? airplane :
 arg == 'T' ? train :
 arg == 'C' ? car :
 arg == 'H' ? horse :
 feet;

EDIT: Let's try:


 return a.dir != b.dir ? a.dir < b.dir :
 a.startx != b.startx ? a.startx < b.startx :
 a.starty < b.starty;

C0lumbo

Dec 18, 2012 at 7:34 PM

At the risk of this thread derailing into code style wars, I wouldn't like to debug any code with such excessive and chained use of the ternary operator - it's also a precedence minefield. (Or the suggestions where the 'return' ends up on the same line as the 'if' for that matter).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.