Trouble creating a map with vector as key and custom class as value.

Question

Hey everybody,

I have created the abstract class below to evaluate a board position of simple games. The abstract class is overridden by each derived class so that only the evaluate function is defined in game.h

I am trying to make my program more efficient by using memoization, but I can't get my map to work correctly. The compiler throws an error for the line results[ board ] = best. This line is attempting to set the value that maps to the current board (vector of ints) to the best possible move from that position. Move is a class that I created that simply contains a score, a number to remove to make the next board, and the index (pile) to remove the number from.

The compiler error for ' results[ board ] = best ' says that there is no matching function call to move::move(). I don't understand this error because I am not trying to create a new move, just store the current best move. I have tried creating a temporary move and storing that as well, so I know that is not correct.

One last point - the code compiles and runs perfectly without that line of code, so I know that the algorithm and all subclasses work properly. Any help would be appreciated!

// VIRTUAL FUNCS
// All virtual functions must be overridden by subclasses

virtual ~game(){ }

// initialize
virtual void initialize( int numPlayers, std::vector<int> board ) = 0;


// gameHasEnded
virtual bool gameHasEnded( std::vector<int> board ) const = 0;

// display
virtual void display( std::vector<int> board ) const = 0;

// makeNewBoard
virtual std::vector<int> makeNewBoard( std::vector<int> currBoard, move m ) = 0;

// generateMoves
virtual std::vector< move >  generateMoves( std::vector<int> currBoard ) = 0;

// compare
virtual move compare( std::vector<int> board1, std::vector<int> board2 ) = 0;

// NON-VIRTUAL FUNCS

//
// Name:         evaluate
// Description:  Evaluates a given board position. Determines whether
//                 or not the current position is a winning position
//                 or a losing position. A winning position is
//                 designated by a 1, a losing by a -1.
// Modifies:     The board and the score.
// Returns:      The best possible move from this position.
//                
move evaluate(  std::vector<int> board, int multiplier = 1, int currScore = -100) {

  // Base case is defined by subclasses
  if( gameHasEnded( board ) ) {
    move toReturn(multiplier, 0);
    return toReturn;
  } // end-if

  // If game is not over
  else {

    std::map<std::vector<int>,move>::iterator iter = results.find( board );
    if( iter != results.end() ) {
      return iter->second;
    }
    else {

      move best(-2,0);  // Just a place holder. Is overridden later.
      int s = 0;  // Stores the score

      std::vector<move> nextMove;
      // generate all possible boards from this position - defined by subclass
      nextMove = generateMoves( board );

      // For each board position
      for( int i = 0; i < ( (int)nextMove.size() ); ++i ) {
        std::vector<int> newBoard;

        // Create a new possible board state
        newBoard =  makeNewBoard( board, nextMove[i] );

        move dif = compare( board, newBoard );  // Get the move that was made
        move m(0,0);  // place holder
        m = evaluate( newBoard, multiplier*-1, currScore );  // recurse through all positions
        s += m.getScore();
        // If this is the best score so far
        if( m.getScore() > currScore ) {  

          m.setNumTake( dif.getNumTake() );  // get the move
          m.setPile( dif.getPile() );
          best = m;  // store the move
          currScore = m.getScore();  // update the score

        }

      }
      best.setScore( s );

      ////////////////////////////// THIS IS THE LINE THAT THROWS A COMPILER ERROR

      results[ board ] = best;

      //////////////////////////////////

      return best;  // return best move
    }
  }
    return move(2,2);  // dummy return. should never happen
  }

private: // Data members

std::map<std::vector<int>,move> results;

};

Answer 1

The default constructor is needed if you use operator[].

If the map does not contain an element for the key board, operator[] of map constructs a new default object and inserts it to the map. Only then it does the assignment of best

Answer 2

Any class you use as a value in a map with the [] operator must be able to be created using the default constructor.

results[ board ] = best;

will do the following

1. Create a default move() with the key board
2. return a reference to that address
3. overwrite the default move by assigning best to it.

You are failing step 1.