FRIHOST • FORUMS • FAQ • TOS • BLOGS • DIRECTORY
You are invited to Log in or Register a Frihost Account!

c++ object design help

   Frihost Forum Index -> Scripting -> Others
 


snowboardalliance
I'm starting to build classes for a c++ card game (poker probably) and I need some help.

I have a Card class, Hand class, and Deck class. The Deck holds a vector of 52 Card* while hands would hold vectors of some other number of Card*. I want it to work so that the Deck holds all the cards in these pointers, and then the hands can just take the pointer as cards are dealt out. However, I want it to work well when a round is over and the deck is reshuffled, like so the hands will automatically clear their vectors (something along those lines). Is this possible to do? Anyone have a good design for a card game that is better?

Just looking for some help to get me started here. If any of that was unclear let me know.

Partial headers of classes
Code:
class Card
{
      Suit suit;
      int value;
      std::string name;
      void setName();
   public:
      Card(Suit s, int v);
      Card(const Card &c);
      Card& operator=(const Card &c);
      Suit getSuit() const;
      int getValue() const;
      friend std::ostream& operator<<(std::ostream &out, const Card &c);
};

enum Suit
{
   diamond,
   heart,
   club,
   spade
};

// unfinished
class Deck
{
      std::vector<Card*> cards;
   public:
      Deck();
      void riffleShuffle(int repeat = 14);
      friend std::ostream& operator<<(std::ostream &out, const Deck &d);
      ~Deck();
};

//barely started
class Hand
{
   public:

};
AftershockVibe
There's nothing particularly wrong with what you've done. However, when you're doing OOP it's a good idea to minimise responsbility upon objects. If you're doing it the way you've outlined you need to ask yourself who has responsibility for a single card - the Deck or the Hand? Or (more complicated) does responsibility transfer when the card is dealt?

Looking what you have here I'd probably do the following:
- Hand takes a reference to a Deck as it's constructor and an Int (number of cards to be taken from the deck)
- Deck should have a deal() method which returns a pointer to a Card and removes it from the internal Card* vector.
- Hand's destructor should also destroy all cards held by it (it should have a vector like Deck but smaller).
- Why do you have a shuffle function in Deck? Vectors don't need to be accessed in order so just pick a card at random when you deal().
- Why do you need a name for cards? A function called getName() could easily convert from suit/number pairs to a string.
Indi
(Just a few small comments.)

AftershockVibe wrote:
- Hand takes a reference to a Deck as it's constructor and an Int (number of cards to be taken from the deck)

That would introduce an unnecessary coupling between Deck and Hand.

Why not just have Deck have a deal(n) function that returns a vector of Cards, and make Hand with a constructor that takes a vector of Cards? Both classes already use vectors, so it won't introduce that much in the way of new dependencies.

(Better yet, but only for the advanced class, have Deck's deal(n) function deal into an output iterator and Hand's constructor construct from an input iterator. That way you completely eliminate interface dependency on vector so that if you chose to change to a deque or something else internally, no biggie.)

AftershockVibe wrote:
- Deck should have a deal() method which returns a pointer to a Card and removes it from the internal Card* vector.

Why pointers? Why not just keep a vector of Cards internally, and made deal() pop one off and return it?

AftershockVibe wrote:
- Hand's destructor should also destroy all cards held by it (it should have a vector like Deck but smaller).

Unnecessary if you ditch the pointers.

AftershockVibe wrote:
- Why do you have a shuffle function in Deck? Vectors don't need to be accessed in order so just pick a card at random when you deal().

i would recommend against this for the sake of efficiency. Just call std::random_shuffle() in the shuffle function, and pop off the back in the deal function. Much faster than recalculating a random number each draw, pulling a card out from the middle, then readjusting the vector around the one you've just taken out.
AftershockVibe
I like these kind of discussions... in programming it's often not that your solution is wrong but it can be better. Smile

I agree with the removal of the coupling between Deck and Hand, a parameter of Cards makes so much more sense.

Quote:
Why pointers? Why not just keep a vector of Cards internally, and made deal() pop one off and return it?


He had defined a Card class already. Now, if he had a shuffle function it is much easier to simply shuffle the pointers to these structures than it is to shuffle the data itself around within a vector (or deque/etc). Unless C++ abstracts all this itself? Personally, I'd be tempted to simply represent cards as Integers and write a function which converted an integer to a Suit/Value pair based on it the value of the integer assuming evaluating hands etc happenned less often than not.

Quote:
Just call std::random_shuffle()

Silly me, rearranging vectors is (relatively) expensive. However, if you weren't removing the cards (and just selecting one at random) you'd be better off selecting one at random as needed because (even assuming the shuffle function is as efficient, which I don't think it will) there's no guarentee you want to use all of the Cards in the Deck.
Indi
AftershockVibe wrote:
Personally, I'd be tempted to simply represent cards as Integers and write a function which converted an integer to a Suit/Value pair based on it the value of the integer assuming evaluating hands etc happenned less often than not.

Sure, why not?

Technically speaking, you can even encode your suit/value pair as a single unsigned char:
Code:
class Card
{
  //...
 
  Value getValue() const
  {
    return (data_ % 13) + 1;
  }
 
  Suit getSuit() const
  {
    return toSuit(data_ / 13);
  }
 
  void setCard(Suit s, Value v)
  {
    data_ = (s * 13) + v;
  }
 
  // ...
 
private:
  unsigned char data_;
};

That's not the most efficient way to do it, for several reasons (you could improve it by using the lower 4 bits in the unsigned char for the value and the upper 4 for the suit, and using bit-masking and shifts rather than divides and mods - and using int will be faster than char on most architectures and never slower, and the extra size is hardly an issue with only 52 cards max), but it is surely possible.

Using an int and bit-masking (rather than an unsigned char and div/mod as i did) would be the way i'd go. Each card would be 1 int big, and operations would be freakin fast.

But that's an optimization issue that can be dealt with after the fact. Remember the rule: make it work... then make it fast.

AftershockVibe wrote:
Now, if he had a shuffle function it is much easier to simply shuffle the pointers to these structures than it is to shuffle the data itself around within a vector (or deque/etc). Unless C++ abstracts all this itself?

On almost all architectures, a pointer is an integer numeric value. On many architectures, it's even the same size as an int.

So... assuming you made your card class one int (as described above), the difference between shuffling an array of pointers vs. an array of ints is usually the difference between shuffling an array of 32-bit integer numeric values vs. an array of 32-bit integer numeric values. Translation: no difference at all.

Furthermore, on those architectures where ints and pointers are different sizes, according to the C++ standard, int is the "natural" size of the architecture, which means that it is always at least as as fast as any other type, and possibly faster. So in that case, the difference between shuffling an array of pointers vs. an array of ints is the difference between shuffling an array of integer numeric values vs. an array of fast integer numeric values. Translation: it is faster to shuffle an array of ints.

Putting it altogether: an array of ints will always be at least as fast as an array of pointers... and possibly faster. That's guaranteed by the standard, and that's without taking into account the extra overhead of indirection the pointers create.

Pointers are not always faster than direct values. Sometimes, they are slower. In C++, an int is guaranteed to be the fastest type, by definition.

-------------------------

But that's not even the biggest problem with using pointers in a situation like this.

Suppose i made an array of cards numbered 1 to 52 using an array of just the numbers, then i shuffled it up so that no two adjacent values were adjacent in the deck. No problem - no two cards drawn will ever be sequential. Piece of cake.

Now suppose i did the exact same thing with pointers to those values, rather than the values themselves. First, assume i shuffle it so that no two pointer values are sequential (the same thing as above, except using the addresses rather than the values). Now, consider this: would it be possible to draw two cards with sequential values? Answer: yes. Because you shuffled the pointers... but what relation did the pointers have to the values? You can't assume that the lowest card will have the lowest pointer (unless you deliberately set it up that way, of course, but if you're doing that, what's the benefit of pointers at all).

You could get around that problem by using compare(*a, *b) rather than compare(a, b) to shuffle... but then you're doing a double indirection each time you compare as you shuffle. In other words... it's slower. And for what gain? None at all.

Bottom line: if you want to shuffle a sequence of numbers, shuffle a sequence of numbers, not their pointers. Depending on how you shuffle, and how you determine their pointers, you could be in for some nasty surprises. And if you are shuffling numbers and not pointers, it is faster to shuffle a sequence of numbers rather than pointers to numbers.

(Note, all of this isn't a problem if you just do a random_shuffle, of course, cause random shuffle is random shuffle, regardless of whether you random shuffle pointers or numbers.)

AftershockVibe wrote:
Quote:
Just call std::random_shuffle()

Silly me, rearranging vectors is (relatively) expensive. However, if you weren't removing the cards (and just selecting one at random) you'd be better off selecting one at random as needed because (even assuming the shuffle function is as efficient, which I don't think it will) there's no guarentee you want to use all of the Cards in the Deck.

All true, but i considered two things when recommending against drawing a random card vs. shuffling then drawing from the top.

First, efficiency considerations:
It is true that shuffling up front may result in more random numbers being generated than generating on demand... but there are other factors to consider.

First, it is usually preferable to perform inefficient operations outside of the game itself, not during play. Levels are usually loaded first as a slow process with a loading screen, rather than amortizing the loading over the first few minutes, making the first few minutes of a level slow. In this context, you're talking about shuffling being really slow and drawing really fast, vs. shuffling being free (unnecessary) and drawing sorta slow. This is a matter of preference, but it seems to me that it is more natural and acceptable to flash a "shuffling..." message while doing the slow shuffle then dealing lightning fast, rather than shuffling being done in a blink but each deal causing a slight pause. Your mileage may vary.

Now, the delay due to random draws is not just the generation of the random numbers. Drawing from the middle of most containers is a very inefficient operation (std::list, or a linked list, is the exception, but that has its own inefficiencies). Consider a game where three cards are drawn. First, assume the deck is not shuffled and cards are drawn randomly. On the terminal i generated 3 random numbers between 0 and 51 - i got {48, 6, 2} (which is going to work out pretty bad ^_^; ). So, the first draw is the 49th card, which means that after we read the card's value, we take it out of the deck by moving the remaining values back then resetting the end pointer. That takes 3 move operations, and one subtraction to correct the end pointer. Not so bad. Now the 7th card takes 44 move operations and one subtraction. And the third card takes 46 move operations and one subtraction. Total work to draw three cards: 93 move operations and 3 subtractions. Now, assume the deck is already shuffled and we can just draw from the back. In this case, all we need to do is correct the end pointer. So each draw takes one subtraction. That's 3 subtractions total... vs. 93 moves and 3 subtractions if we draw randomly.

See, it's not just a question of the shuffling - you also have to readjust the deck after each draw. Drawing from the middle is slow. Drawing from the end is lightning fast... possibly free on some architectures (because the move instruction to copy the end value can be interleaved with the subtract instruction to correct the end pointer).

Next is aesthetic considerations:
When you are modelling a real world object in software, it makes sense to model it as closely to reality as possible. A stove class should work like an actual stove, in so far as it is possible (a stove's behaviour should be modelled as accurately as possible). This means less surprises for maintainers and users.

When you play cards... who draws from the middle? No one, unless they're doing a magic trick. People shuffle, then draw from the top. That is real-world behaviour, and it should be modelled as closely as possible.

And finally, future planning considerations:
Suppose you wanted to implement a put back function. Some card games allow you to discard cards back to the top of the deck, which can then be drawn by other players. How would you do that with a random draw system? With a shuffle then draw from the top system, it would be trivial. (And with a shuffle then draw from the top system, if you really wanted a random draw from the middle, it would be trivial to implement.)
snowboardalliance
wow, thanks for all that help.

Ok I don't have time right now to decide everything but I am definitely doing a shuffle. So I was just wondering, does it make sense to make the Card class keep track of all cards created on the heap by using like Card* create() and a private constructor? (so that the Card class can ensure all Cards are deleted at the end even if they get passed between the deck and hand a lot)

And which is better? Keeping the vector<Card*> in deck using iterators while keeping the data (no popping), or just using the pop_back() (if that's the function, I can't remember) and rebuilding the deck before every shuffle? It seemed to me initially that it would be better to keep the Cards lifetime through the whole game, but everyone seems to recommend popping Cards off. Wouldn't using pop cause the end of a round to be slower because the Deck would have to rebuild?

I have most other things figured out and I may post some code later once I get a working system. As for optimizing the Cards with ints and bitwise operations, I'll hold off for now.

Thanks again everyone.
Indi
snowboardalliance wrote:
wow, thanks for all that help.

Ok I don't have time right now to decide everything but I am definitely doing a shuffle. So I was just wondering, does it make sense to make the Card class keep track of all cards created on the heap by using like Card* create() and a private constructor? (so that the Card class can ensure all Cards are deleted at the end even if they get passed between the deck and hand a lot)

And which is better? Keeping the vector<Card*> in deck using iterators while keeping the data (no popping), or just using the pop_back() (if that's the function, I can't remember) and rebuilding the deck before every shuffle? It seemed to me initially that it would be better to keep the Cards lifetime through the whole game, but everyone seems to recommend popping Cards off. Wouldn't using pop cause the end of a round to be slower because the Deck would have to rebuild?

I have most other things figured out and I may post some code later once I get a working system. As for optimizing the Cards with ints and bitwise operations, I'll hold off for now.

Thanks again everyone.

Well, here are my opinions.

First, i don't see any reason for a card class to be in any way aware of other cards, or where it came from. Playing cards as *i* know them have exactly three pieces of information: the number (or face value), the suit, and the graphic on the back giving a hint what deck it belongs to (and even then, it's hardly an id mark, because with two decks with identical art, you'd have no way of distinguishing). i know of no card game in existence that uses the graphic on the back in any way - so it's generally superfluous information. Which means, in practice, a card has two pieces of information, number and suit - nothing more, nothing less.

Second, this create() function is just a bad idea, based on bad ideas. This is 2007, and almost 2008 at that. We really don't do things that way any more. Even assuming you had reason to create the cards on the heap (which, i can't see a reason for), there is no justification for passing around naked pointers. Remember this rule: "if there is a 'delete' in your code, you have done something wrong." If you really have to use the heap, use smart pointers. std::tr1::shared_ptr<card> beats card* ten thousand times over. Do that and your cards will be deleted no matter what happens up to a cataclysmic crash. No need for create() functions. No need to delete anything.

Now... would popping cards off of a card vector cause a delay at the start of each round as the deck is reconstructed? Maybe. In practice, no. But in theory, maybe. You see, once you construct the vector with 52 cards (or card*'s), that vector now has the memory for 52 cards. Popping a card off the back does not mean the vector has to be reallocated - all it would have to do is change the pointer to the back of the sequence (and, in practice, that's what they all do). Think of it like this: the inside of a vector probably looks like this:
Code:
card* allocated_memory_start_;
card* allocated_memory_end_;
card* data_end_;

When you add 52 cards, this happens:
Code:
allocated_memory_start_ = new card[52]; // Memory is allocated
allocated_memory_end_ = allocated_memory_start_ + 52; // End of memory is remembered
data_end_ = allocated_memory_end_; // vector is full (so all the allocated memory is used)

When you pop one card off the end, you think that means the vector has to be resized... but that's not the case. This could (and usually does) happen:
Code:
--data_end_; // End of data is moved one spot back

No reallocation is necessary.

So now at the end of a round, when it comes time to reconstruct the 52 card vector... it still has all the memory. All it has to do is reset "data_end_" so that the difference between the start of the allocated memory and the end of the data is 52. Simple and fast.

Now... that's how all current implementations that i know of work (excepting special purpose, very low memory STL implementations). But you're right... they could resize after each pop, or after 30 pops, or whenever, so that reconstructing at the end of the hand would require reallocating the entire vector. Your STL would suck rocks if it did that... but it is legal behaviour.

If you're really concerned about that, i'd say you shouldn't be. But if you still are....

First of all, std::vector is a sleek, sexy, multifunction power tool. It's nice. And it's very flexible. But... we don't need all of that power. We know how big a deck is, and it is always the same size. We don't need dynamic resizing.

Enter std::tr1::array. It is like a standard C array, but much more powerful and flexible, and safer. Instead of keeping your cards in a vector, keep them in an array:
Code:
std::tr1::array<card, 52> cards_;

(Incidentally, in your actual code, you would be wise to use typedefs. "typedef std::tr1::array<card, 52> cards;", then "cards cards_;". Why? Because if you want to change to vector or deque later, you can just change the typedef, and everything else will work.)

So, at the start of the game, fill the array with the 52 cards any way you like (depends on how you construct your cards, but you could do something like this:
Code:
cards::iterator p = cards_.begin();

for (int v = 1; v <= 13; ++v)
  *p = card(v, suit::hearts);
for (int v = 1; v <= 13; ++v)
  *p = card(v, suit::clubs);
for (int v = 1; v <= 13; ++v)
  *p = card(v, suit::spades);
for (int v = 1; v <= 13; ++v)
  *p = card(v, suit::diamonds);


To take a card from the deck, you need to keep track of where the top of the deck is. So you need another variable:
Code:
cards::iterator top_of_deck_;

Which you set at the beginning of the game to:
Code:
top_of_deck_ = cards_.begin();


To draw a card, it's simple. Get the card value, then change the top of the deck marker:
Code:
card drawn_card = *top_of_deck_;
++top_of_deck_;


At the end of a round, to put all the cards back:
Code:
top_of_deck_ = cards_.begin();

That's it.

And to shuffle, just remember you only want to shuffle what's in the deck:
Code:
std::random_shuffle(top_of_deck_, cards_.end());


How it works:
Well, you have your array of 52 cards (represented as numbers here):
Code:
1 2 3 4 5 ... 48 49 50 51 52

And you get (automatically, by begin() and end()) pointers to the start and end:
Code:
1 2 3 4 5 ... 48 49 50 51 52
↑                         ↑
begin()                   end()

And you have your pointer to the top of the deck:
Code:
1 2 3 4 5 ... 48 49 50 51 52
↑                         ↑
top                       |
|                         |
begin()                   end()

Now, when you draw a card, you don't change anything but the location of the top of the deck:
Code:
1 2 3 4 5 ... 48 49 50 51 52
↑ ↑                       ↑
| top                     |
|                         |
begin()                   end()

Draw another card:
Code:
1 2 3 4 5 ... 48 49 50 51 52
↑   ↑                     ↑
|   top                   |
|                         |
begin()                   end()

At all times, everything between top and end is what's still in the deck (which is why, when we shuffle, we use top and end(), not begin() and end()). And, at the end of the game, putting everything back, all you have to do is set top = begin():
Code:
1 2 3 4 5 ... 48 49 50 51 52
↑                         ↑
top                       |
|                         |
begin()                   end()


And that... is scorchingly fast. In fact, i dare say that it's as fast as you can possibly make it in C++ (or C). It's also simple, robust and extensible. That's the way i've done it in the past (although i had to use boost::array in the days before std::tr1::array), and that's still the way i'd do it.

(Incidentally, you may comment that it makes put back operations (returning a card to the deck) difficult. Not so. In fact, they're still very simple... and actually automatically include a layer of protection against cheating. But that's a more advanced issue.)
snowboardalliance
Ok thanks Indi, I won't use new and delete then.

The way you explained using iterators for the deck was kind of what I was thinking. I'll probably use that std::tr1::array that you suggested. I'm still new to c++ and got most of my information from "Thinking in C++ Vol. 1" which is probably a bit outdated.

My one last question then would be about this:

Quote:
Incidentally, you may comment that it makes put back operations (returning a card to the deck) difficult. Not so. In fact, they're still very simple... and actually automatically include a layer of protection against cheating.


What do you mean when you say they include a layer of protection? The only thing I'm wondering is how would I make sure no hand keeps any cards between rounds (resulting in duplicates). I mean I could just make sure I make the hands work well and I empty them, but I wanted some kind of "protection" as you mention and I was wondering if you could explain this a little (unless it's a lot more advanced as you said)

By the way, do you have any recommended reading on any of this? I mean just good c++ design in general? You seem to give good advice and since I am learning this in school for an independent study, I'd be interested in finding more information.

EDIT:
I'm using MingW with gcc version 3, is version 4 stable? Because I would need that to use TR1.

EDIT AGAIN:
Also, if I use a vector<Card> (or tr1::array) instead of Card* so I don't use new, does this mean I need copy a constructor and operator=? I tried changing my code to use Card instead of Card* in the vector and it seems like I would need to change that too.

Thanks.
Indi
snowboardalliance wrote:
Ok thanks Indi, I won't use new and delete then.

No no! Hang on! i didn't say don't use new. i said never use delete. (i know you meant that you won't use new and delete in this case, but i'm taking the opportunity to explain the more general rule.)

new is fine. There's nothing wrong with new. Sometimes it's even required.

But never, ever use delete. One software company i heard of had a semi-official in-house policy of using grep on all source files looking for deletes. If any were found, whoever put them there would be tracked down via CVS and punished. delete is the goto of the 1990s. It is evil.

snowboardalliance wrote:
The way you explained using iterators for the deck was kind of what I was thinking. I'll probably use that std::tr1::array that you suggested. I'm still new to c++ and got most of my information from "Thinking in C++ Vol. 1" which is probably a bit outdated.

i'm not familiar with book titles, but i do know authors. Who wrote it?

snowboardalliance wrote:
My one last question then would be about this:

Quote:
Incidentally, you may comment that it makes put back operations (returning a card to the deck) difficult. Not so. In fact, they're still very simple... and actually automatically include a layer of protection against cheating.


What do you mean when you say they include a layer of protection? The only thing I'm wondering is how would I make sure no hand keeps any cards between rounds (resulting in duplicates). I mean I could just make sure I make the hands work well and I empty them, but I wanted some kind of "protection" as you mention and I was wondering if you could explain this a little (unless it's a lot more advanced as you said)

Well... here's the thing. This won't provide that kind of security. It will, but it won't... this is more of a sanity check than a "wait a minute, the move you are trying to make is illegal" check. Basically, if this check fails... your program is crashing. But that's not a problem, and i'll explain why in a minute.

First, to answer your question.

Now, remember you have your deck of cards with a pointer to the top of the deck. Everything after that pointer (inclusive) is the contents of the deck... which means everything before that pointer has been dealt and is out in play. So suppose cards 1 through 8 were out in play, meaning card 9 is at the top of the deck (and would be dealt next). Your deck would look like:
Code:
1 2 3 4 5 6 7 8 9 10 11 ... 50 51 52
↑               ↑                 ↑
|               top               |
|                                 |
begin()                           end()

Suppose i wanted to return card 3 to the deck. Essentially what i want to do is replace card 8 with card 3, and move the pointer one step back.
Code:
1 2 4 5 6 7 8 3 9 10 11 ... 50 51 52
↑             ↑                   ↑
|             top                 |
|                                 |
begin()                           end()

That's possible... but there's no need to preserve the order that the cards have been dealt in, is there? (Or at least, it is not the deck's responsibility to keep track of the order that the cards have been dealt in. Once the card leaves the deck, it's gone. How would the deck know if it is the first or last card to have been dealt?) Which means that this is just as valid:
Code:
1 2 8 4 5 6 7 3 9 10 11 ... 50 51 52
↑             ↑                   ↑
|             top                 |
|                                 |
begin()                           end()

Which is a whole lot more efficient than shifting all the cards between 3 and 9 to the left.

So how can we accomplish this? Well here's a simple way:
  1. Find the 3 in the set of cards that has been dealt.
  2. Swap it with the 8.
  3. Move the pointer back.

Or, in code:
Code:
cards::iterator p = find(begin, top, 3); // Find the 3
swap(*p, *(top - 1)); // Swap with the 8
--top; // Move the pointer back


Now, a card can't be returned to the deck if it's already in the deck... it must be out in play. Therefore, when you return a card to the deck, it must be between the begin and top pointers. Which means, if you do a "find(begin, top, returned_card)", it should never equal top (which would mean the card is not in between begin and top). What that means in code is:
Code:
cards::iterator p = find(begin, top, 3);

if (p == top)
  throw unable_to_return_card_that_has_not_been_dealt_exception();

swap(*p, *(--top));

So an exception will be thrown if someone tries to return a card already in the deck.

Now, although this is a neat little free feature you get that does some basic checking, it's not really the best way to go about doing this. Why? Two reasons.

First, it's not the deck's responsibility to ensure fair play. Have you ever played a card game where the deck has jumped up and accused someone of cheating? Ok, granted, i have, but have you ever seen that happen when you were sober? The deck "knows" whether a given card is in the deck or not... and when someone tries to add a card that's already there, something is wrong with the universe, not the game or the honesty of the players. The only thing your poor deck can do is curl up and die. Which, by throwing an exception, it pretty much does.

Instead, you should have another class keeping track of the game, and watching for cheating - a game class, for example. The game class can monitor what is drawn and who has what in their hand, and when someone tries to do something illegal - and, being the game class, it would know the rules of the game - it can react accordingly. But the deck is just a pile of cards and a couple of handy interfaces for mixing them up and distributing them, nothing more, nothing less. Don't make the deck responsible for the sanctity of the game or game rules. But it is nice to know that you have one more safety net to catch you if something screws up.

Second, don't distribute responsibility. The deck class can certainly check to see that when a card is returned to the deck, it isn't already there, but it can't do anything about anything else. If someone tries to spoof a hand, how could the deck know? If you are going to put something in charge of maintaining the integrity of the game, put something in charge of maintaining the integrity of the game, not somethings. One job, one class. Clearly the deck isn't capable of doing the whole job, so you need another class that can. But once you have that class, use that class, not the deck, to keep the game sane.

snowboardalliance wrote:
By the way, do you have any recommended reading on any of this? I mean just good c++ design in general? You seem to give good advice and since I am learning this in school for an independent study, I'd be interested in finding more information.

i generally don't do books, but you can try Scott Meyers. He's got a series called Effective C++ which is kind of the bible of good design in the field.

snowboardalliance wrote:
EDIT:
I'm using MingW with gcc version 3, is version 4 stable? Because I would need that to use TR1.

Yes, and no. ^_^;

Yes, version 4 is fine and stable. It's at like 4.1 on my machine, and i don't really keep it updated.

No, you don't need to change your compiler to use tr1. Boost has tr1, and it can intelligently decide whether to use itself or your existing tr1. i use Boost.TR1 with four other compilers that don't have TR1 natively, and for most of them i have it set up so that you don't even notice it.

snowboardalliance wrote:
EDIT AGAIN:
Also, if I use a vector<Card> (or tr1::array) instead of Card* so I don't use new, does this mean I need copy a constructor and operator=? I tried changing my code to use Card instead of Card* in the vector and it seems like I would need to change that too.

Ah... ^_^; well....

Ok, first, yes, if you use vector or array, you don't need copy constructors, assignment operators or a destructor. The automatically generated ones are fine.

But. ^_^;

If you are going to use an iterator into the array to record where the top of the deck is... you need a copy constructor and assignment operator. Otherwise you will end up with a second deck where the top iterator points into the vector/array in the first deck. If you use a number to record the top position rather than an iterator, you won't have this problem... but there are no other benefits to that, and, frankly a lot more hassles.

However ^_^; (sometimes simple questions can lead to big answers).

Do you really want to allow copy construction and/or assignment? Why? What do you gain? Can you copy decks in real life? If you want a second deck, fine... but a copy of a deck? What does that mean?
AftershockVibe
Indi has gone into much better detail than I can but...
As an aside, while we're talking about equality and copy, you might want to think about whether in the game your card's value (not necessarily the "value" attribute) will ever be compared directly to each other. Would it be useful to specify the greater than operator?

For simple games, you can do:
Code:
Card1.value < Card2.value


But what about games like bridge where the clubs are the least valuable suit and spades the most valuable? Perhaps it would be useful to define this value calculation into the "<" operator for your Card class and take this into account. However, this makes your Card class less general. I'm not aware of any games where this would affect scoring but that doesn't mean there aren't any.

Also, will you ever need to sort your cards? You can't sort unless you have a less than operator. I can't think of any reason why you'd want to re-order a Deck, but Hands perhaps? For display purposes (lowest to highest) or perhaps for AI where they may want to drop their lowest card, or play their highest?

Note that you don't need a ">" operator for like sort(). Although for convenience you could define it to be the inverse of "<".

You have to think your logic through when doing these sort of things though.
Say, that I'm not playing bridge so I don't care about suit value so I do the following:

Code:
Card operator<(const Card& left, const Card& right)
{
  If (left.value < right.value){
    return True;
  }
  else {
    return False;
  }
}

Card operator>(const Card& left, const Card& right)
{
  If (left.value > right.value){
    return True;
  }
  else {
    return False;
  }
}

Card operator==(const Card& left, const Card& right)
{
  If (left.value == right.value){
    return True;
  }
  else {
    return False;
  }
}


Code is somewhat longwinded to make it clearer but hmm... is this really what we want?
Now we have a sutuation where "==" will tell you that the ace of spades is equal to the ace of hearts. Great for scoring... not great for checking for duplicate cards!
Similarly, if we had defined equality to include matching suits for both left and right then you end up with a rather confusing defintion of Card where the following will occur:

Card1 < Card2 -- False
Card1 > Card2 -- False
Card1 == Card2 -- False (Intuition says this should be True by implication).


I'd rambled for long enough and would like to ask Indi (apologies for highjacking the thread slightly) how he'd go about doing this? How would you go about sorting your Hand?
Indi
AftershockVibe wrote:
Indi has gone into much better detail than I can but...
As an aside, while we're talking about equality and copy, you might want to think about whether in the game your card's value (not necessarily the "value" attribute) will ever be compared directly to each other. Would it be useful to specify the greater than operator?

Useful? i can't answer that question, because first you have to ask if it would be meaningful. Is there any meaningful way to compare two cards?

Is the four of spades "greater" than the six of hearts? What is the proper way to order the three of diamonds, four of clubs and five of diamonds? The answer to both of those questions is... i dunno. It depends.

Now equality is well-defined for cards. Two cards are equal if their suit and value are the same. Forget what game you happen to be playing: if i asked you if the six of hearts was the same as the six of clubs, no one in their right mind would say yes. You may happen to be playing a game where they are considered equal in the context of the game... but that doesn't suddenly, magically make them actually equal. They're clearly two different cards.

An equality operator would be a trivial thing to add:
Code:
inline bool operator==(card const& a, card const& b)
{
  return a.value() == b.value() && a.suit() == b.suit();
}

And you're done. ^_^; Doesn't really benefit much from making it a class member, either, so why bother? Of course, making an equality operator mandates an inequality operator... which is also trivial, especially if you write it in terms of the equality operator.

AftershockVibe wrote:
For simple games, you can do:
Code:
Card1.value < Card2.value


But what about games like bridge where the clubs are the least valuable suit and spades the most valuable? Perhaps it would be useful to define this value calculation into the "<" operator for your Card class and take this into account. However, this makes your Card class less general. I'm not aware of any games where this would affect scoring but that doesn't mean there aren't any.

Also, will you ever need to sort your cards? You can't sort unless you have a less than operator. I can't think of any reason why you'd want to re-order a Deck, but Hands perhaps? For display purposes (lowest to highest) or perhaps for AI where they may want to drop their lowest card, or play their highest?

Note that you don't need a ">" operator for like sort(). Although for convenience you could define it to be the inverse of "<".

Well, technically it should be the logical inverse of ((<) || (==))... but you've missed a key feature of the STL. It's generic. Sure, it defaults to using operator< for sort... but it does not require it.

In the case of a card, < doesn't make sense. Therefore, it shouldn't be defined. It will only create unnecessary confusion.

However... that doesn't mean you can't use some kind of ordering logic for sorting:
Code:
// Compares two suits so that:
// clubs < diamonds < hearts < spades
bool suit_is_less(card::suit const&, card::suit const&);

bool compare_suit_then_value(card const& a, card const& b)
{
  if (a.suit() == b.suit())
    return a.value() < b.value();
  else
    return suit_is_less(a.suit(), b.suit());
}

bool compare_value_then_suit(card const& a, card const& b)
{
  if (a.value() == b.value())
    return suit_is_less(a.suit(), b.suit());
  else
    return a.value() < b.value();
}

// Now, given hand:
// ♠4 ♠2 ♡K ♡J ♡9 ♡5 ♡2 ♢Q ♢J ♢6 ♢2 ♣Q ♣9

sort(hand.begin(), hand.end(), ptr_fun(compare_suit_then_value));
// Gives you:
// ♣9 ♣Q ♢2 ♢6 ♢J ♢Q ♡2 ♡5 ♡9 ♡J ♡K ♠2 ♠4


sort(hand.begin(), hand.end(), ptr_fun(compare_value_then_suit));
// Gives you:
// ♢2 ♡2 ♠2 ♠4 ♡5 ♢6 ♣9 ♡9 ♢J ♡J ♣Q ♢Q ♡K

And of course, you can write any number of custom comparison functions to match the rules of any given game - be it bridge or go fish - or the tastes of the person holding the hand (so that they can choose to order by suit, by value, ace high, ace low, or whatever they like).

(Now, i wouldn't actually write either of those comparison functions above that way... but i would write a handful of convenience functions for doing comparisons and stick them in the same header as the card class. What i would probably do is write two comparison functions for value only - ace low and ace high - then a comparison function for suit only - using bridge ordering, i guess - then two comparison functions - suit-then-value and value-then-suit - that both take a suit comparison function and value comparison function. With just the five functions i have mentioned, i could probably compare anything. For bonus points, i might make a suit comparison template that takes the suits in order as parameters... but that's getting really advanced.)
snowboardalliance
Indi wrote:

new is fine. There's nothing wrong with new. Sometimes it's even required.

But never, ever use delete. One software company i heard of had a semi-official in-house policy of using grep on all source files looking for deletes. If any were found, whoever put them there would be tracked down via CVS and punished. delete is the goto of the 1990s. It is evil.


Ok I'm kind of confused, don't you need to use delete after you use new?

Indi wrote:

i'm not familiar with book titles, but i do know authors. Who wrote it?

Bruce Eckel


Indi wrote:

Instead, you should have another class keeping track of the game, and watching for cheating - a game class, for example. The game class can monitor what is drawn and who has what in their hand, and when someone tries to do something illegal - and, being the game class, it would know the rules of the game - it can react accordingly. But the deck is just a pile of cards and a couple of handy interfaces for mixing them up and distributing them, nothing more, nothing less. Don't make the deck responsible for the sanctity of the game or game rules. But it is nice to know that you have one more safety net to catch you if something screws up.

good point, I was starting to consider this.


Indi wrote:

i generally don't do books, but you can try Scott Meyers. He's got a series called Effective C++ which is kind of the bible of good design in the field.

I'll probably check that out next. Also, if you don't do books, where do you get all this info? I feel like everything I've been reading has been kind of outdated after reading your post.


Indi wrote:

No, you don't need to change your compiler to use tr1. Boost has tr1, and it can intelligently decide whether to use itself or your existing tr1. i use Boost.TR1 with four other compilers that don't have TR1 natively, and for most of them i have it set up so that you don't even notice it.

I'll just use that then



So basically could you just explain how I can use a vector (or tr1 array) of Card* (pointers) using new but not delete? That's the only thing I'm kind of confused about because I thought that would just create memory leaks. Or does vector use delete in its destructor?

Thanks so much for all your detailed help.
Indi
snowboardalliance wrote:
Indi wrote:

new is fine. There's nothing wrong with new. Sometimes it's even required.

But never, ever use delete. One software company i heard of had a semi-official in-house policy of using grep on all source files looking for deletes. If any were found, whoever put them there would be tracked down via CVS and punished. delete is the goto of the 1990s. It is evil.


Ok I'm kind of confused, don't you need to use delete after you use new?

Not if you change your paradigm.

The concept is RAII (Resource Acquisition Is Instantiation), which, basically, states that every resource should be managed by a class - acquired by the class's constructor and released by the class's destructor. Like a file for example - open it in the constructor, and close it in the destructor. (i'm giving you the basics of the principle - of course, in practise, it's often a good idea to allow some flexibility. For example, allow the file to be opened after construction and closed before destruction, and only closed in the destructor if it's still open.)

Memory is a resource. Therefore, an allocated chunk should be managed by an RAII class. The only one in the traditional STL is auto_ptr, but TR1 adds shared_ptr, and Boost has scoped_ptr. Loki's got a couple, too, if i recall, but i don't use it myself normally. Between those three, that's all the management you could possibly need of an allocated memory resource.

In code, that means:
Code:
//////// NEVER do this... EVER
object* p_foo = new object;

// ... some code...
// for example, p_foo->func();

delete p_foo;

//////// ALWAYS do this (with some kind of smart pointer)
std::tr1::shared_ptr<object> p_bar = new object;

// ... some code...
// for example, p_foo->func();

// Automatically deleted


i'll give a simple example of why. Take this three line function:
Code:
void foo()
{
  object* p_bar = new object;
  p_bar->baz();
  delete p_bar;
}
Now, riddle me this: does it leak memory?

You will never be able to give me a straight answer. The best you can do is "definitely maybe". ^_^;

What happens if baz() throws an exception? You get a leak. How can you be sure baz() will never throw? Unless it's declared no-throw, you can't. And very few functions are declared no-throw, for good reason.

Can you fix it? Sure, you can do something like this:
Code:
void foo()
{
  object* p_bar = new object;
 
  try
  {
    p_bar->baz();
    delete p_bar;
  }
  catch(...)
  {
    delete p_bar;
    throw;
  }
}

So much for simplicity. But it gets worse. What happens if you have to allocate two chunks of memory in a function... or more? You get a mess like this:

Code:
void foo()
{
  object* p_bar = new object;
 
  try
  {
    object* p_xyzzy = new object;
   
    try
    {
      p_bar->baz(p_xyzzy);
     
      delete p_xyzzy;
      delete p_bar;
    }
    catch (...)
    {
      delete p_xyzzy;
      throw;
    }
  }
  catch (...)
  {
    delete p_bar;
    throw;
  }
}

// OR:

void foo()
{
  object* p_bar = new object;
 
  object* p_xyzzy = new (nothrow) object;
  if (!p_xyzzy)
  {
    delete p_bar;
    throw bad_alloc();
  }
 
  try
  {
    p_bar->baz(p_xyzzy);
   
    delete p_xyzzy;
    delete p_bar;
  }
  catch (...)
  {
    delete p_xyzzy;
    delete p_bar;
    throw;
  }
}
AND THAT'S JUST WITH TWO POINTERS! ^_^; So much for the simple little three line function.

Let's try it again, this time with smart pointers (i chose boost::scoped_ptr, but pretty much any smart pointer would work in this case - auto_ptr would be a good choice if you don't want to use boost, shared_ptr would work but would be a little bit of overkill):
Code:
void foo()
{
  boost::scoped_ptr<object> p_bar = new object;
  p_bar->baz();
}
Does it leak memory?

The answer is no. Under no conceivable circumstance short of a complete and total program crash (at which point, releasing memory is hardly a concern) or code modification by an external agent (for example, a virus overwriting your program code or data in memory), this function will not leak memory. Even if baz() throws, you're fine. Even in a multi-threaded program, provided other threads don't overwrite this thread's stack data (which would probably lead to a program crash), it will work correctly.

Adding other pointers is no problem:
Code:
void foo()
{
  boost::scoped_ptr<object> p_bar = new object;
  boost::scoped_ptr<object> p_xyzzy = new object;
  p_bar->baz(p_xyzzy.get());
}
Again, it can't leak under any conceivable circumstance that doesn't involve a total program crash.

The situation gets a little stickier with arrays, unfortunately, because the standard expects you to use vector instead of a dynamically allocated array... but then doesn't require vector to have copy-on-write semantics (and you can't use any of the *_ptr smart pointers with chunks of memory that have been allocated by new[]). It's a real pain in the ass, frankly, and the working group is currently discussing copy-on-write semantics for C++2.0. But, Boost to the rescue, Boost has shared_array and scoped_array that cover all the possibilities right now.

snowboardalliance wrote:
Indi wrote:

i'm not familiar with book titles, but i do know authors. Who wrote it?

Bruce Eckel

Good guy. i don't know what he's doing nowadays, but he is one of the guys responsible for C++ being as well-designed and powerful as it is today.

Avoid Herb Sutter - he's a big shot and really popular, but aside from his guru of the week stuff (a lot of which was supplied by people like Eckel and Meyers), i've always found his writings to be a little... meh. Never wrong... just not great. For example, he was advocating the use of Hungarian warts for a looooong time after most people had already realized how silly they were and moved on. He's also one of those guys that writes C++-- (basically C with one or two C++ features, or Java rewritten as C++). Of course, i'm judging him based on stuff he did years ago. Maybe he's better now?

If you get through Meyers' stuff, also check out Andrei Alexandrescu. i believe he tends to be more advanced in what he covers... but he literally wrote the book on next-generation C++ programming techniques.

Also, i'm not exactly sure if Dave Abrahams has published any books, but his articles are always awesome. If he has a book, it would probably be awesome, too.

snowboardalliance wrote:
Indi wrote:

i generally don't do books, but you can try Scott Meyers. He's got a series called Effective C++ which is kind of the bible of good design in the field.

I'll probably check that out next. Also, if you don't do books, where do you get all this info? I feel like everything I've been reading has been kind of outdated after reading your post.

i'm not actually a programmer by trade, but i've done a lot of it as a hobby. i've also talked to a lot of the experts in the field, like Stroustrup, Abrahams, Beman Dawes and PJ Plauger, and i try to read technical whitepapers and articles (like, for example, the C++ issues list, and the list of proposed C++2.0 stuff). i just listen when the experts talk, and i ask them their opinions on different methods, and try to absorb the reasoning and logic given in whitepapers and stuff.

snowboardalliance wrote:
So basically could you just explain how I can use a vector (or tr1 array) of Card* (pointers) using new but not delete? That's the only thing I'm kind of confused about because I thought that would just create memory leaks. Or does vector use delete in its destructor?

Well, as i mentioned above, the basic concept is smart pointers. However, you do have a few extra tricks you can use.

The most basic answer is don't use vector<Card*> (or array<Card*>), use vector<shared_ptr<Card> >. That should be the first thing that springs to your mind - never use naked pointers, always use smart pointers.

But smart pointers can sometimes be overkill. If you're not really going to be sharing the pointers in your array, shared_ptr can be too much. It's (if i recall) double the size of a naked pointer, and copying and stuff can be (slightly) slower than a naked pointer. (C++2.0 will have unique_ptr, which will work nicely in this case, but in the meantime....)

As usual, Boost to the rescue. Boost has Boost.Pointer Container, which means that instead of vector<Card*>, you do ptr_vector<Card>. ptr_vector will intelligently delete all the pointers on destruction. It also has a couple of other handy-dandy features for dealing with containers of pointers, like intelligently handling cloning and stuff like that.

However, it's actually not all that common to use heap allocated objects, except for a few, rare, global objects, or large objects that only need to be constructed optionally - or when running out of memory is an issue. Most objects, including most global objects, can just as well be allocated on the stack. Take your card vector, for example. What gain is there by using a vector of pointers to the cards? The cards still have to be allocated somewhere. By using a vector of pointers, you end up with needing a card + a pointer for each card... before anything else is done in your program... and, of course, you have to keep track of the pointers. Why not cut out the middle man? Ditch the pointers, and now you only need a card object for each card, and you keep track of the cards directly. You can still pass around pointers to those cards to the rest of the program if you feel you must (or, even better, shared_ptrs with a null deleter).

Basically, it is the difference between:
Code:
template <typename T> void do_delete(T* p) { delete p; }

class deck
{
public:
  ~deck()
  {
    for_each(cards.begin(), cards.end(), ptr_fun(do_delete));
    // Or, if you use ptr_vector<card>, the above is not required
  }
 
  card* get_card(size_t n) const
  {
    return cards[n];
  }
 
  // ... other stuff...
 
private:
  vector<card*> cards;
};

And:
Code:
class deck
{
public:
  ~deck()
  {
    // Don't need anything here
  }
 
  card* get_card(size_t n) const
  {
    return &cards[n];
  }
 
  // ... other stuff...
 
private:
  vector<card> cards;
};

In practise, could be as little as one or two extra little "&" added to your code if you use ptr_vector. (If you don't use ptr_vector, things like sorting and finding can get a little verbose.) But instead of allocating cards and pointers to cards then keeping track of the pointers, you are allocating cards then keeping track of the cards.

snowboardalliance wrote:
Thanks so much for all your detailed help.

No problem.
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2007 Frihost, forums powered by phpBB.