Jump to content

  • Log In with Google      Sign In   
  • Create Account

C++ arbitrarily sorting a struct


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
9 replies to this topic

#1 Dan Berliner   Members   -  Reputation: 113

Like
0Likes
Like

Posted 16 December 2012 - 08:23 PM

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?

Sponsor:

#2 wqking   Members   -  Reputation: 756

Like
0Likes
Like

Posted 16 December 2012 - 08:29 PM

if(a.dir > b.dir) {

    return false;

}

if(a.startx > b.startx) {

    return false;

}

if(a.starty > b.starty) {

    return false;

}

return true;


Not sure if it's want you want.
My code returns true only whan a's all fields are less than b's

http://www.cpgf.org/
cpgf library -- free C++ open source library for reflection, serialization, script binding, callbacks, and meta data for OpenGL Box2D, SFML and Irrlicht.
v1.5.5 was released. Now supports tween and timeline for ease animation.


#3 Dan Berliner   Members   -  Reputation: 113

Like
0Likes
Like

Posted 16 December 2012 - 09:02 PM

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, 16 December 2012 - 09:03 PM.


#4 SiCrane   Moderators   -  Reputation: 9668

Like
3Likes
Like

Posted 16 December 2012 - 09:47 PM

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;


#5 Dan Berliner   Members   -  Reputation: 113

Like
0Likes
Like

Posted 16 December 2012 - 09:54 PM


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;


Interesting, thanks for sharing.

Edited by Dan Berliner, 16 December 2012 - 09:55 PM.


#6 Álvaro   Crossbones+   -  Reputation: 13905

Like
0Likes
Like

Posted 16 December 2012 - 10:27 PM

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;

Edited by Álvaro, 16 December 2012 - 10:30 PM.


#7 BeerNutts   Crossbones+   -  Reputation: 2999

Like
1Likes
Like

Posted 18 December 2012 - 10:50 AM

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.
My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#8 Cornstalks   Crossbones+   -  Reputation: 6991

Like
0Likes
Like

Posted 18 December 2012 - 11:00 AM

If you're using C++11, there's std::tie and you can just do:
return std::tie(a.dir, a.startx, a.starty) < std::tie(b.dir, b.startx, b.starty);

[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#9 Álvaro   Crossbones+   -  Reputation: 13905

Like
0Likes
Like

Posted 18 December 2012 - 01: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;

Edited by Álvaro, 18 December 2012 - 01:31 PM.


#10 C0lumbo   Crossbones+   -  Reputation: 2496

Like
0Likes
Like

Posted 18 December 2012 - 01: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).




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS