Beginner's question regarding arrays

[Ulnarian]

I'm making a "war" style card game. For the sake of explanation, assume that there are only 10 available cards valued 1 through 10. At the start of the game, 5 of the cards will be randomly given to Player 1 and the other 5 will be given to Player 2.

So far, I have three int arrays. The first array represents the total available cards (i.e. int cards[10]...); the 2nd array is Player 1's cards and the 3rd array is Player 2's cards.

My question is about the "deal" of the cards. Specifically, how can I take an element from the 1st array and place it into either the 2nd or 3rd array in such a way that the same element cannot later be randomly picked again? For example, is player 1 is given card #5, how can I ensure that either player 1 or player 2 doesn't end up with a second #5 card?

Thanks.

[TheRogue]

There are going to be many ways to do this

I would suggest you change your cards from an int to a class that has a member variable indicating which player owns it.
You would then only need one array holding all cards, I would also suggest using a vector instead of an array.

If you are intent on using three arrays, I would still make the cards a class, then just move them from one "array" to another using copy and delete it from the first list.

Depending on what operations you will be performing, the first option requires no copying, allocating, deallocating, etc, and would be less likely to loose cards.

[monarch_dodra]

Yes, there are so many ways to do this it's not even funny (actually, it is).

Anyways, to give you the most concise yet helpful answer, I will guide you to random_suffle. This algorithm can take any range (in this case, your array), and shuffle the contents randomly.

Regardless of your solution, random_shuffle will probably end up as the core of your algorithm.

My recommendation: Shuffle your array1. Have player 1 draw the cards [0;5[, and player 2 draw the cards [5;10[. There, easy-peasy (is that the spelling?).

Of course, since it not clear if the players are "drawing by value" or "drawing by reference", or how they later use these cards in the future, it will be up to you to be the judge of the best solution.

Alternative: If you do not want to shuffle your first array of cards, you can create an intermediary array of indexes ({0,1,...,9}), and shuffle that. Then, player 1 can draw: array1[intermediarry[0]], array1[intermediarry[1]] etc.

[Lindley]

I would suggest you change your cards from an int to a class that has a member variable indicating which player owns it.

While I agree that making a Card class makes sense, I don't think the owner should be an attribute of the card. I think that should be determined by which container is currently storing the card.

[Ulnarian]

Thanks everyone. I ended up using Monarch's alternative answer as my vector knowledge is pretty much non-existent.

[D_Drmmr]

Thanks everyone. I ended up using Monarch's alternative answer as my vector knowledge is pretty much non-existent.

std::vector is so easy to learn that that's no excuse.

Have a look at one of these:
http://www.codeguru.com/cpp/cpp/cpp_...icle.php/c4071
http://www.codeguru.com/cpp/cpp/cpp_...icle.php/c4027

[itsmeandnobodyelse]

Thanks everyone. I ended up using Monarch's alternative answer as my vector knowledge is pretty much non-existent.

vector is easier than C arrays:

class Deck
{
     std::vector<int> deck;
public:
     Deck() 
     {
         // add cards 1 to 10 to deck 
         for (int i = 0; i < 10; ++i) 
              deck.push_back(i+1); 
     }    
     void deal(Hand & hand1, Hand & hand2)
     {
           // seed rand function with current time in seconds
           srand(time(NULL));
           for (i = 0; i < 10; ++i)
           {    // get random index from deck
                 int n = rand()%deck.size();
                 int c  = deck[n];
                 if ((i%2) == 0)
                      hand1.add(c);
                 else
                      hand2.add(c);
                 deck.erase(deck.begin()+n);
           }
     }
     // more functions
};

You would need class Hand which also has an internal vector and a function 'add'. Also a class Game with one Deck and two Hand objects.

[laserlight]

With only 10 cards in the deck, itsmeandnobodyelse's example is fine, but in general you would take monarch_dodra's suggestion of a random shuffle instead. Because the erase function runs in linear time, itsmeandnobodyelse's implementation of the deal function has quadratic time complexity. Compare this to the linear time complexity that you can get with random shuffle.

Also, it is not necessarily a good idea to seed the PRNG when deal is called. It would be better to allow the caller the option of seeding the PRNG, since this might be done just once in a run of the program (whereas the deal function might be called more than once), and the caller may want to seed with a known seed in order to redo a simulation.

[PredicateNormative]

vector is easier than C arrays:

class Deck
{
     std::vector<int> deck;
public:
     Deck() 
     {
         // add cards 1 to 10 to deck 
         for (int i = 0; i < 10; ++i) 
              deck.push_back(i+1); 
     }    
     void deal(Hand & hand1, Hand & hand2)
     {
           // seed rand function with current time in seconds
           srand(time(NULL));
           for (i = 0; i < 10; ++i)
           {    // get random index from deck
                 int n = rand()&#37;deck.size();
                 int c  = deck[n];
                 if ((i%2) == 0)
                      hand1.add(c);
                 else
                      hand2.add(c);
                 deck.erase(deck.begin()+n);
           }
     }
     // more functions
};

You would need class Hand which also has an internal vector and a function 'add'. Also a class Game with one Deck and two Hand objects.

Just for feedback, which you will hopefully find useful. I thought I'd point out that you have a few bugs.

1) You should move

 srand(time(NULL));

into the constructor of Deck, otherwise you will re-seed rand everytime deal is called (and thus will not necessarily provide very random consecutive deals).

2) Consecutive calls to deal will yeild undefined behaviour, because you are calling deck.erase(iter) in your deal function, but have no means of reconstituting the deck of 10 cards before the deal function is called again. Therefore further calls to deal will attempt to access elements in the vector that are now invalid.

That aside, I agree with the others, monarch_dodra has suggested a better solution. However, I understand that you were probably more trying to point out the use of vector rather than provide a correct and efficient solution.

[kempofighter]

vector does seem like a good choice here since you will typically take cards only from one end of the deck which would be the back of the vector container. I recommend using the reserve member function to set the capacity to the max number of cards. If you use push_back without reserve you'll probably end up allocating more memory than you need.

Also I agree with the suggestions to move the cards from one container to another. This is actually really simple. vector has a pop_back member function that is easy to use. If you random_shuffle the deck then you deal by copying the last element from the deck using vector::back into the new container and then pop_back from the vector. That's another alternative to consider and it would probably be easier to write the code for that. You an also start at the end with an iterator and move it backwards and copy until you are finished dealing. At that point you would erase everything after the final position of the iterator. Since the OP is a beginner I recommend keeping it simple at first. This shouldn't be a difficult program to write if you learn to use the sequence containers.

[itsmeandnobodyelse]

Just for feedback, which you will hopefully find useful. I thought I'd point out that you have a few bugs.

1) You should move

 srand(time(NULL));

into the constructor of Deck, otherwise you will re-seed rand everytime deal is called (and thus will not necessarily provide very random consecutive deals).

2) Consecutive calls to deal will yeild undefined behaviour, because you are calling deck.erase(iter) in your deal function, but have no means of reconstituting the deck of 10 cards before the deal function is called again. Therefore further calls to deal will attempt to access elements in the vector that are now invalid.

That aside, I agree with the others, monarch_dodra has suggested a better solution. However, I understand that you were probably more trying to point out the use of vector rather than provide a correct and efficient solution.

Guys, it was only quick and dirty sample code to show advantage of std::vector. I didn't want to show the most efficient and fully way shuffling and dealing needs to be done.

The seed of the srand could be done once but in a game program which asks for user input (probably) it makes not so much a difference. I added it in Deck:eal just to keep the sample code simple. I didn't assume consecutive calls to deal either (what makes little sense logically) and had no error handling but of course both should be considered for serious code.

You easily could make the deal safer by

     for (int i = 0; i < (int)deck.size(); ++i)
        ...

but of course the deal should be called only once for a new deck.

Shuffling before dealing of course is a valid alternative and has the advantage that it maps to a real life game better than the random dealing.

Here is a simple way of randomly adding cards into the deck in the constructor. After that the deal would put all even indices to hand1 and all odd indices to hand2.

class Deck
{
      ...
      Deck::Deck()
      {
           srand(time(NULL));
           shuffle();
       }

       void shuffle()
       {
           // fill a vector with 10 integers of value 1
           std::vector<int> deckinit(10, 1);
           // make deck empty
           deck.clear();
           // calculate randomly a position in deckinit,
           // assign next non-zero entry to deck and 
           // mark the moved entry position by a zero entry
           for (i = 0; i < 10; ++i)
           {    // get random index from deck
                 int n = rand()%10;
                 int c;
                 // if we find a zero in the deckinit, the card is already moved
                 while (deckinit[n]) == 0)
                       // step to next n in cycle
                       n = (++n)%10;  
                 deck.push_back(n+1);
                 deckinit[n] = 0;
           }
      }
      ....

Again, the code is more to show up the advantages of std::vector over C arrays than to give an efficient shuffle algorithm.

[monarch_dodra]

Guys, it was only quick and dirty sample code to show advantage of std::vector.

Don't take comments on your code personally. A quote is a citation, not a direct reply to the original author.

Even if PredicateNormative's words look like they are directed at you (which they were), they are especially meant to be seen by the OP, who, while learning about vector, is also learning about (s)rand. Most of us here, you included, know all this, but our posts are seen by hundreds of people of copy it by the letter, and it is important for us to cover each other's backs.

Take it as a "further more about itsmeandnobodyelse's code, you can..." rather than a direct attack/correction at you.

PS: Could you turn on private messaging to your account? I wanted to give you a personal welcome message to these boards.