• Advertisement
Sign in to follow this  

C++ arbitrarily sorting a struct

This topic is 1857 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
[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

Share this post


Link to post
Share on other sites
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. Edited by Dan Berliner

Share this post


Link to post
Share on other sites
[quote name='wqking' timestamp='1355711372' post='5011470']
My code returns true only whan a's all fields are less than b's
[/quote]
This isn't a legal comparison for use with std::set. A valid comparison needs to be a [url=http://en.wikipedia.org/wiki/Strict_weak_ordering]strict weak ordering[/url]. 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:
[code]
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;
[/code]

Share this post


Link to post
Share on other sites
[quote name='SiCrane' timestamp='1355716029' post='5011503']
[quote name='wqking' timestamp='1355711372' post='5011470']
My code returns true only whan a's all fields are less than b's
[/quote]
This isn't a legal comparison for use with std::set. A valid comparison needs to be a [url="http://en.wikipedia.org/wiki/Strict_weak_ordering"]strict weak ordering[/url]. 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:
[code]
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;
[/code]
[/quote]

Interesting, thanks for sharing. Edited by Dan Berliner

Share this post


Link to post
Share on other sites
I do it like this (just a bit more compact):
[code]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;[/code]

EDIT: Or even this:
[code]return a.dir != b.dir ? a.dir < b.dir
: a.startx != b.startx ? a.startx < b.startx
: a.starty < b.starty;[/code] Edited by Álvaro

Share this post


Link to post
Share on other sites
[quote name='Álvaro' timestamp='1355718473' post='5011517']
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;

[/quote]

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

Share this post


Link to post
Share on other sites
If you're using C++11, there's [font=courier new,courier,monospace][url="http://en.cppreference.com/w/cpp/utility/tuple/tie"]std::tie[/url][/font] and you can just do:
[code]
return std::tie(a.dir, a.startx, a.starty) < std::tie(b.dir, b.startx, b.starty);
[/code]

Share this post


Link to post
Share on other sites
[quote name='BeerNutts' timestamp='1355849449' post='5012106']
What's the point? It's much more complicated to read with no processing time benefit.
[/quote]

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. [url="http://en.wikipedia.org/wiki/%3F:"]Wikipedia[/url] has this example of very readable use of concatenated ternary operators:

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

EDIT: Let's try:
[code]
return a.dir != b.dir ? a.dir < b.dir :
a.startx != b.startx ? a.startx < b.startx :
a.starty < b.starty;
[/code] Edited by Álvaro

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement