代码超出范围。这个向量如何动态分配？

Question

我对C++相当陌生，并开始编写一个小型扑克游戏，以帮助我获得更多有关向量的经验。我在第二个函数中遇到了运行时错误，在阅读下面的文章后发现我误解了reserve（）类成员的行为，这真的不是什么新鲜事。我相信我可以用resize（）来补救这个问题，但是我希望能够通过一种方式来创建一些输入，以便我可以重新构建这个动态分配的函数。我在动态分配方面遇到的困难是，我试图让交易功能像真正的纸牌游戏一样向每个玩家分发纸牌（是的，我意识到这在统计上是多余的）。我可以很容易地用c中的指针数学来做到这一点，我想我可以通过静态分配这些向量来解决这个问题，但我更愿意尽可能地使用C++作为优雅和高效的。任何建议的动态做到这一点？也就是说，我怎样才能完全避免为deal()函数中使用的容器分配或预留空间？

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; 

} 

输出：

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 

回溯：

#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

我设法找到解决我自己的问题，并认为我应该分享。感谢迅速Aziuth的输入。它远没有完成，甚至没有功能，但是这样做会很好。我决定跟踪玩家是否折叠并因此不再有效，这是非常有用的，所以我在Hand类中添加了一个布尔成员“active”。这有另外的好处，允许我强制Deck :: deck向量初始化空结构，而不必手动调整它们的大小。

我也把它分成三类，让每一个小而简单。

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); 
}; 

Answer 2

载体不重新分配每当您添加或删除的元素。分配的大小可能与使用的大小不同 - 正如您已经注意到reserve()和resize()之间的差异。随着矢量大小的增加，分配变得更大，因此分配的“松弛”量是常数因子（IIANM）乘以矢量的长度。因此，对于n次插入，您只能进行O（log（n））重新分配调用。同样，当您删除元素时，只有当大小与保留大小的比率下降到某个点以下时才会释放空间 - 如果有的话。

编辑：继澄清 - 约不想要做任何调整大小或保留 - 一个可能的选项可以使用地图，而不是一个向量。 std::map和std::unordered_map有一个operator[]与“插入如果丢失，否则更新”语义。其实，我也将添加一些更多的变化，并提出了“交易”功能：

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; 
} 

这里的好处是，它不承担运动员是整数;事实上，也许你会用字符串代替。玩家可以是，例如std::vector或std::unordered_set。

此外，使用映射或集合是“浪费”，因为它们使用指针并执行许多分配;所以如果你在数百万玩家和卡片上工作，我会建议别的。但在你的例子中，效率并不是真正的问题。

_{PS - 正如@PeterBecker所提到的，C++标准只需要分摊的恒定时间插入，而不是我所描述的一切 - 这是对库实现通常具有的描述。}

Answer 3

什么是预防或调整向量的反感？当我知道矢量的大小时，我总是保留或调整它的大小。这一选择取决于我打算如何填补它。

特别是对于大型矢量，将大小保留为适当的值是一种更好的做法，比允许它随着其增长（它必须执行的操作）不断调整大小更好。

我看不出有什么理由不保留或调整甲板到52和手到5，因为这是他们将不得不长大，因为他们使用。

如果您要使用push_back填充矢量，请保留它们。如果您要使用分配，请调整其大小。

例如

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 

或：

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 

或：

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