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?
C++ arbitrarily sorting a struct
[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
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
Author
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.
The exact order it sorts in is unimportant, it just needs some way to do so.
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;
Author
[quote name='wqking' timestamp='1355711372' post='5011470']
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;
[/quote]
Interesting, thanks for sharing.
I do it like this (just a bit more compact):
EDIT: Or even this:
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;
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.
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);
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;
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
