How would you go about defining undefined functions in a template?

Question

I'm writing a C++ project and have a generic evaluate method in a class template.

My only question is how would I define the generateAllMoves and isPosFinal so that it is defined inside the classes that use this class template?

I've read that using pure virtual functions is a no no. I also do not want to make it static.

I foresee myself rewriting this as an abstract class, but then I would end up with a problem that requires generic types.

#ifndef ENGINE_H
#define ENGINE_H

#include <map>

using namespace std;

template< class M, class P >

class Engine {

public:

  Engine() { };  

  struct Move {
    P move;
    P pos;
    int score;
  };

  Move evaluate( P position ) {

    Move best;      

    if ( posIsFinal( position ) ) {
      Move newMove;
      newMove.pos = position;
      newMove.score = 1;
      return newMove;
    }

    else {

      map< M , P > allMoves = generateAllMoves( position );

      typename map< M , P > :: iterator it;

      for (it = allMoves.begin(); it != allMoves.end(); it++ ) {
        Move next = evaluate(it->second);

        if (next.score > best.score ) {
          best.pos = next.pos;
          best.move = next.move;
          best.score = next.score;
        }
      }
      return best;
    }
  }
};

#endif

Edit: To be more clear for everyone!

I have two different games right that defines its own generateAllMoves and isPosFinal methods. They use different algorithms and return different types.... For example, I will be soon implementing a chess game, but right now I'm implementing nim. Both interpret move and is this position final, differently.

2nd Edit:

Final code compiles!

#ifndef ENGINE_H
#define ENGINE_H

#include <map>

using namespace std;

template< typename Derived, class M, class P >

class Engine {

public:

  struct Move {
    P move;
    P pos;
    int score;
  };

  Move evaluate( P position ) {

    Move best;      

    if ( static_cast<Derived*>(this)->posIsFinal( position ) ) {
      Move newMove;
      newMove.pos = position;
      newMove.score = 1;
      return newMove;
    }

    else {

      map< M , P > allMoves = static_cast<Derived*>(this)->generateAllMoves( position );

      typename map< M , P > :: iterator it;

      for (it = allMoves.begin(); it != allMoves.end(); it++ ) {
        Move next = evaluate(it->second);

        if (next.score > best.score ) {
          best.pos = next.pos;
          best.move = next.move;
          best.score = next.score;
        }
      }
      return best;
    }
  }

  bool posIsFinal( P position ) {
    cerr << "Generic posIsFinal\n";
    exit(1);
  }

  map< M , P > generateAllMoves( P position ) {
    cerr << "Generic generateAllMoves\n";
    exit(1);
  }

private:


};

#endif

I've read that using pure virtual functions is a no no. <- Who said that and under what circumstances? — RedX, Oct 19 '11 at 06:56
@Als I think that Benoît's answer is more suitable for the problem presented here — Vinzenz, Oct 19 '11 at 06:57
no answer to your question but don't write using namespace std in a header file see: http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-a-bad-practice-in-c — codencandy, Oct 19 '11 at 06:57
@Vinzenz:I dont suggest answers unless I know the problem exists.Most new users try solving problems that don't really exist. — Alok Save, Oct 19 '11 at 07:34

score 2 · Accepted Answer · answered Oct 19 '11 at 06:54

2

A good way to do just this is to use the "Curiously Recursive Template Parameter" idiom.

See here for more information.

answered Oct 19 '11 at 06:54

Benoît

16,798
8
46
66

Thank you! After reading it many times and racking my brain, I finally get it. Thank you, thank you, thank you. I'm sure this will surprise my teacher... is this considered object oriented programming? – user1002563 Oct 19 '11 at 07:55
Well, that's unfortunate. But I'll ask my professor about it when I start the next part. Again, thank you! – user1002563 Oct 19 '11 at 08:07
Using CRTP is part of static polymorphism. Basically you can achieve to some degree the same results like you'd have with with a virtual method defined in the class without having the need for a vtable. Considering this, you actually can still call it Object Oriented, but most likely your professor would expect you to use virtual methods which are implemented by the derived class. CRTP offers you the same possibility without the runtime/dynamic polymorphism. – Vinzenz Oct 19 '11 at 13:55

score 1 · Answer 2 · answered Oct 19 '11 at 07:56

You could make a traits class with all necessary parameterization for the Engine:


template< class EngineTraits >
class Engine {

  typedef typename EngineTraits::P_type P;
  typedef typename EngineTraits::M_type M;

public:

  Engine() { };  

  struct Move {
    P move;
    P pos;
    int score;
  };

  Move evaluate( P position ) {

    Move best;      

    if ( EngineTraits::posIsFinal( position ) ) {
      Move newMove;
      newMove.pos = position;
      newMove.score = 1;
      return newMove;
    }

    else {
      typedef typename EngineTraits::moves_mapping_type MovesMapping;
      MovesMapping allMoves = EngineTraits::generateAllMoves( position );

      typename MovesMapping::iterator it;

      for (it = allMoves.begin(); it != allMoves.end(); it++ ) {
        Move next = evaluate(it->second);

        if (next.score > best.score ) {
          best.pos = next.pos;
          best.move = next.move;
          best.score = next.score;
        }
      }
      return best;
    }
  }
};

Now you can customize your engine by defining appropriate traits class:


struct my_engine_traits
{
  typedef some-type P_type;
  typedef some-type M_type;
  typedef std::map<M_type, P_type> moves_mapping_type;

  static bool posIsFinal(P_type const &position)
  {
    // ...
  }

  static moves_mapping_type generateAllMoves(P_type const &position)
  {
    // ...
  }
};

Or you can make your engine client class to be engine traits as well:


class my_engine_client
{
  typedef some-type P_type;
  typedef some-type M_type;
  typedef std::map<M_type, P_type> moves_mapping_type;

  static bool posIsFinal(P_type const &position)
  {
    // ...
  }

  static moves_mapping_type generateAllMoves(P_type const &position)
  {
    // ...
  }

  typedef Engine<my_engine_client> Engine;
  Engine m_engine;  
};

And surely you can vary what is passed directly as Engine template parameters and what to move to a single traits class, e.g.:


template< class M, class P, class PositionProcessor >
class Engine {
// ...
};

score 0 · Answer 3 · answered Oct 19 '11 at 07:19

0

Not particularly a friend of friend functions but how about something like this:

template< class M, class P >
class Engine {
public:
  friend void generateAllMoves(P position);
  void evaluate( P position )
  {
    ...
    generateAllMoves(position);
    ...
  }
};

// here your specific function

void generateAllMoves(int position )
{ 
  ;
}

int main(int argc, char* argv[])
{
// then instantiate it
  Engine<int,int> X;

  ..

answered Oct 19 '11 at 07:19

AndersK

35,813
6
60
86

This doesn't seem to have any static methods in it... so I will assume this is object oriented programming? I''ll save this when I redesign in the future. Thanks Anders! – user1002563 Oct 19 '11 at 08:14

How would you go about defining undefined functions in a template?

3 Answers3