Code out of range. How can this vector be allocated dynamically?

Question

I'm fairly new to c++ and started writing a small poker game to help me get some more experience with vectors. I'm getting a runtime error in the second function, which is really no surprise after reading the post below and discovering I was misunderstanding the behavior of the reserve() class member. I believe I could probably remedy this with resize() but I was hoping for some creative input on a way that I could re-construct this function to allocate dynamically. The difficulty I'm having with the dynamic allocation is that I am trying to make the deal function distribute cards to each player as in a real card game (yes I realize that this is somewhat statistically superfluous). I could do this with pointer math in c fairly easily, and I think I could fix this by statically allocating some of these vectors, but I would prefer to utilize c++ as elegant and efficient as possible. Any suggestions on a way to do this dynamically? That is, how can I completely avoid allocating or reserving space for the containers used in the deal() function?

Choice between vector::resize() and vector::reserve()

#include <cassert>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>

const int __handSize__ = 5;

class Hand {
public:
    std::vector<int> held;
    std::vector<int> played;
};

std::vector<int> shuffle() {
    std::vector<int> deck;
    for( int i = 0; i < 52; i++ ){
        deck.push_back( i );
    }
    std::random_shuffle(deck.begin(), deck.end());
    assert( 52 == deck.size() );
    return deck;
}

std::vector<Hand> deal( int nPlayers, std::vector<int> &deck ) {
    std::vector<Hand> playerHands;
    playerHands.reserve( nPlayers );
    for( int i = 0; i > __handSize__; i++ ) {
        for( int j = 0; j < nPlayers; j++ ) {
            playerHands.at(j).held.push_back( deck.back() );
        }
    }
    return playerHands;
}

int main() {
    srand(time( NULL ));
    std::vector<int> deck = shuffle();
    std::vector<Hand> hand = deal( 3, deck );
    std::cout << hand.at(1).held.at(1) <<std::endl;

}

output:

dmf86@tux3:~/src/poker$ ./poker
terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 1) >= this->size() (which is 0)
Aborted

Back trace:

#0  0x00007ffff74aa428 in __GI_raise (sig=sig@entry=6)
    at ../sysdeps/unix/sysv/linux/raise.c:54
#1  0x00007ffff74ac02a in __GI_abort () at abort.c:89
#2  0x00007ffff7ae484d in __gnu_cxx::__verbose_terminate_handler() ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#3  0x00007ffff7ae26b6 in ?? () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#4  0x00007ffff7ae2701 in std::terminate() ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#5  0x00007ffff7ae2919 in __cxa_throw ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#6  0x00007ffff7b0b3f7 in std::__throw_out_of_range_fmt(char const*, ...) ()
   from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#7  0x000000000040218c in std::vector<int, std::allocator<int> >::_M_range_check(unsigned long) const ()
#8  0x0000000000401785 in std::vector<int, std::allocator<int> >::at(unsigned long) ()
#9  0x0000000000401030 in main ()

Answer 1

What is the aversion to reserving or resizing vectors? When I know the size that a vector needs to be, I always reserve or resize it. That choice depends upon how I intend to fill it.

Especially for large vectors, reserving the size to the proper value is a better practice than allowing it to keep resizing as it grows (which it must do).

I see no reason to not reserve or resize the deck to 52, and the hands to 5, since that is what they will have to grow to as they are used.

If you are going to use push_back to fill the vectors, reserve them. If you are going to use assignment, resize it.

e.g.

vector<int> deck;  // create empty vector
deck.resize(52);   // resize to 52 elements
// now size = 52, and capacity = 52

for(int i = 0; i < 52; i++)
    deck[i] = i;   // assign the elements

or:

vector<int> deck(52);  // create vector with 52 elements
// size = 52 and capacity = 52

for(int i = 0; i < 52; i++)
    deck[i] = i;    // assign to the elements

or:

vector<int> deck;
deck.reserve(52);    // reserve space for 52 elements
// size = 0, capacity = 52

for(int i = 0; i < 52; i++)
    deck.push_back(i);  // push to create the elements
// now size = 52, capacity = 52

Answer 2

Vectors do not re-allocate whenever you add or remove an element. The allocated size can differ from the size used - as you have already noticed with the difference between reserve() and resize(). As the vector size increases, the allocations become larger, so that the amount of allocated "slack" is a constant factor (IIANM) times the length of the vector. Thus, for n insertions, you only make O(log(n)) re-allocation calls. Similarly, when you remove elements, space is de-allocated only when the ratio of size to reserved size drops below some point - if at all.

Edit: Following the clarification - about not wanting to have to do any resizing or reserving - a possible option could be using a map instead of a vector. std::map and std::unordered_map have an operator[] with an "insert if missing, update otherwise" semantic. In fact, I'll also add some more changes, and propose a "deal" function:

auto deal(const SomeKindOfContainer& players, std::vector<Card>& deck) {
    std::unordered_map<Player, Hand> playerHands;
    auto handSize = deck.size() / players.size();
    for(int i = 0; i < hand_size; i++) {
        for(const auto& player : Players) {
            playerHands[player].held.push_back( deck.pop_back() );
        }
    }
    return playerHands;
}

The nice thing here is that it doesn't assume the players are integers; and, in fact, maybe you're going to use strings instead. The players could be, say, a std::vector, or an std::unordered_set.

Also, using maps or sets is "wasteful", as these use pointers and perform many allocations; so if you were working on millions of players and cards, I would have suggested something else. but in your example efficiency is not really a concern.

_{PS - As @PeterBecker mentions, the C++ standard only requires amortized constant-time insertion, rather than everything I've described - which is a description of what library implementations typically have.}

Answer 3

I managed to find a solution to my own question and thought I should share. Thanks to swift Aziuth for their input. Its far from done, or even functional, but this will work well. I decided that it would be useful to keep track of whether a player had folded and therefore no longer active, so I added a boolean member "active" to the Hand class. This has the added benefit of allowing me to force the Deck::deck vector to initialize empty structures without having to manually resize them.

I also broke it up into three classes to keep each one small and simple.

class Hand {
public:
    std::vector<int> held;
    std::vector<int> played;
    bool active;
};

class Deck {
    const int _handSize_ = 5;
    std::vector<int> deck;
public:
    void shuffle();
    int getCard();
};

class Players {
    std::vector<Hand> playerNo;
    int activePlayers;
public:
    Players( int n );
    void addCard( int player, Deck &deck );
    bool isActive( int n );
};