std::bad alloc whit std::vector,Tic-Tac-Toe

Question

我正在尝试实现我自己的井字游戏并制作一棵树（数据结构），其中包含所有可能的动作（对于 Min-Max 算法）。

在函数 Add_Match() 的某一时刻，我收到了这个运行时错误：

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc`

main() 的有趣部分（int Tic-Tac-Toe.cpp）：

if(victory(board)){
    //the movement gave the victory to player 1, we save it

    final.set_score(1);
    match.push_back(final);

    //reset for rematch

    board.Reset();
    final.Reset();

    memory.Add_Match(match);

    match.clear();
    match.push_back(Choice());

    matchs++;
}

我的Boardclass:

class Board{
    private:
        int n_=3;
        std::vector<std::vector<int>> board_;

    public:
        Board(){
            board_= std::vector<std::vector<int>>(n_,std::vector<int>(n_));
            Reset();
        }

        void Reset(){
            for (size_t i = 0; i < n_; i++)
            for (size_t j = 0; j < n_; j++)
                board_[i][j]=0; 
        }

        void PrintBoard(){
            for (size_t i = 0; i < n_; i++){
                std::cout<<std::endl;
                for (size_t j = 0; j < n_; j++)
                std::cout<<board_[i][j]<<"  ";
            }    
            std::cout<<std::endl;
        }

        int win(){
            int winner=-1;
            for (size_t i = 0; i < n_; i++)
            for (size_t j = 0; j < n_; j++){
                int player=board_[i][j];

                //Right
                if(player!=0 && j+2 == 2 && board_[i][j+1] == player && board_[i][j+2] == player)
                    winner=player;

                //Left
                else if(player!=0 &&  j-2 == 0 && board_[i][j-1] == player && board_[i][j-2] == player)
                    winner=player;

                //Up
                else if(player!=0 &&  i-2 == 0 && board_[i-1][j] == player && board_[i-2][j] == player)
                    winner=player;

                //Down
                else if(player!=0 &&  i+2 == 2 && board_[i+1][j] == player && board_[i+2][j] == player)
                    winner=player;

                //Up-Right
                else if(player!=0 &&  i-2 == 0 && j+2 == 2 && board_[i-1][j+1] == player && board_[i-2][j+2] == player)
                    winner=player;

                //Up-Left
                else if(player!=0 &&  i-2 == 0 && j-2 == 0 && board_[i-1][j-1] == player && board_[i-2][j-2] == player)
                    winner=player;

                //Down-Left
                else if(player!=0 &&  i+2 == 2 && j-2 == 0 && board_[i+1][j-1] == player && board_[i+2][j-2] == player)
                    winner=player;

                //Down-Right
                else if(player!=0 &&  i+2 == 2 && j+2 == 2 && board_[i+1][j+1] == player && board_[i+2][j+2] == player)
                    winner=player;
            }

            if(winner==-1 && Size()==9)
                winner=0;

            return winner;
        }

        bool CheckPosition(int row,int col){
            if(board_[row][col]==0)
                return true;
            else   
                return false;
        }

        void Put(int player,int row,int col){
            board_[row][col]=player;
        }

        int Size(){
            int count=0;
            for (size_t i = 0; i < n_; i++)
            for (size_t j = 0; j < n_; j++)
                if(board_[i][j]!=0)
                    count++;

            return count;
        }

        int Get(int row,int col){
            return board_[row][col];
        }

        bool Equals(Board board){
            for (size_t i = 0; i < n_; i++)
            for (size_t j = 0; j < n_; j++)
            {
                if(board_[i][j]!=board.Get(i,j))
                    return false;
            }

            return true;
        }
};

我的Choiceclass:

class Choice{
    private:
        Board board_;
        int row_,col_,score_;
        std::vector<Choice> childs_;
    
    public:
        Choice(Board board,int row,int col,int score){
            board_=board;
            row_=row;
            col_=col;
            score_=score;
        }   

        Choice(){
            Reset();
        }

        void Reset(){
            board_.Reset();
            row_=-1;
            col_=-1;
            score_=-1;
        }

        void Add_Child(Choice new_child){
            childs_.push_back(new_child);
        }

        Choice* get_LastChild(){
            return &childs_.back();
        }

        void Delete_Childs(){
            childs_.clear();
        }

        Board get_Board(){return board_;}
        Board *get_Board_Adress(){return &board_;}
        int get_Row(){return row_;}
        int get_Col(){return col_;}
        std::vector<Choice> get_Childs(){return childs_;}
        int get_Score(){return score_;}
        void set_score(int score){score_=score;}
};

还有我的Tree_Min_Maxclass:

class Tree{
    private:
        Choice root_;
        Choice *ptr;

    public:
        Tree(){
            root_.Reset();
        }

        void Go_Root(){
            ptr=&root_;
        }

        bool find(Choice node){
            if(ptr->get_Board().Equals(node.get_Board()) && ptr->get_Row()==node.get_Row() && ptr->get_Col()==node.get_Col())
                return true;
            else
            {
                std::vector<Choice> childs = ptr->get_Childs();
                for (size_t i = 0; i < childs.size(); i++)
                {
                    ptr=&childs[i];
                    if(find(node))
                        return true;
                }
                return false;
            }
        }

        bool Has(Choice node_to_find){
            Go_Root();
            bool found=find(node_to_find);
            return found;
        }
    
        void Add_Match(std::vector<Choice> match){
            Choice *parent;
            for (size_t i = 0; i < match.size(); i++)
            {
                if(i==0)
                    parent=&root_;
                else
                {
                    if(!Has(match[i])){
                        parent->Add_Child(match[i]);
                        parent=parent->get_LastChild();
                    }
                    else
                        parent=ptr;
                }
            }
        }

        void clear(){
            Go_Root();
            root_.Delete_Childs();
        }
};

我已经调试了我的代码，但我无法正确找到错误。

我认为 bad_alloc 是由堆栈中的错误内存位置引起的，但我该如何解决这个问题？

Answer 1

这是一个明显的错误：

else
{ 
   std::vector<Choice> childs = ptr->get_Childs();
   for (size_t i = 0; i < childs.size(); i++)
   {
      ptr=&childs[i]; // <-- Bug
      //...

您正在存储局部变量的地址。当 childs 向量超出范围时，该指针不再有效。

错误实际上来自于：

std::vector<Choice> get_Childs(){return childs_;}

您正在 return 复制向量，而不是实际的 childs 向量。解决方法是 return 引用，而不是副本：

std::vector<Choice>& get_Childs(){return childs_;}

然后：

std::vector<Choice>& childs = ptr->get_Childs();

记下参考 return 值。

std::bad alloc whit std::vector,Tic-Tac-Toe

std::bad alloc whit std::vector,Tic-Tac-Toe

c++

stdvector

bad-alloc

tic-tac-toe

minmax