Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++: what is the Curiously-Recurring-Template-Pattern? and can Curiously-Recurring-Template-Pattern replace virtual functions?

I don't have a precise description of the problem so I'm just asking if this is possible (and if it is, some other information would be great).

A programmer told me you can avoid runtime overhead caused by virtual functions/polymorphism. He said to avoid the runtime overhead you can use templates in pattern called Curiously_recurring_template_pattern which looks something like this:

class Derived : public Base<Derived>
{
  // ... implementation here
};

How does this Curiously-Recurring-Template-Pattern work?

How can one use Curiously-Recurring-Template-Pattern to substitute normal virtual functions/polymorphism?

Did I get it wrong?

like image 780
Marco A. Avatar asked Jun 07 '13 16:06

Marco A.


4 Answers

Very specifically, the CRTP can be used instead of a base class with virtual functions to implement the template method pattern without virtual function call overhead.

With virtual functions, the TMP looks like this:

class ProvidesMethod {
protected:
  void Method() {
    // do something
    Part1();
    // do something else
    Part2();
    // do something final
  }

private:
  virtual void Part1() = 0;
  virtual void Part2() = 0;
};

class ExposesMethod : private ProvidesMethod {
public:
  using ProvidesMethod::Method;

private:
  void Part1() {
    // first part implementation
  }
  void Part2() {
    // second part implementation
  }
};

With the CRTP, it looks like this:

template <typename Derived>
class ProvidesMethod {
protected:
  void Method() {
    // do something
    self().Part1();
    // do something else
    self().Part2();
    // do something final
  }

private:
  Derived& self() { return *static_cast<Derived*>(this); }
  const Derived& self() const { return *static_cast<const Derived*>(this); }
};

class ExposesMethod : private ProvidesMethod<ExposesMethod> {
public:
  using ProvidesMethod<ExposesMethod>::Method;

private:
  friend class ProvidesMethod<ExposesMethod>;
  void Part1() {
    // first part implementation
  }
  void Part2() {
    // second part implementation
  }
};
like image 193
Sebastian Redl Avatar answered Nov 03 '22 02:11

Sebastian Redl


this is called CRTP (for Curiously Recurring Template Pattern) so you can look it up.

Although I don't really see how it could replace classic polymorphism...

On the other hand, one can in some cases replace complex hierarchical structure of classes by template, (see policy-based design for more info), but it's not always possible...

like image 42
Julien Lopez Avatar answered Nov 03 '22 01:11

Julien Lopez


As Julien noted, this is CRTP. You should look it up. But the CRTP cannot replace virtual functions. If it does in a particular case for you, then you didn't actually need virtual functions in the first place. Look, templates provide compile-time polymorphism. Virtual functions provide run-time polymorphism. If you don't know what which override is going to be called at compile time, then a template based solution isn't going to work. If you always know what the real type of an object is going to be at runtime, then you don't need virtual functions.

like image 22
zindorsky Avatar answered Nov 03 '22 02:11

zindorsky


I'm not sure how you would use templates to provide something like virtual functions - it seems strange to me - certainly without a bunch of trickery that eventually amounts to implementing your own version of virtual functions instead of using the compiler provideed ones, I find it very hard to see how you can make a way that the code calling the function don't know what type the object is, and call the correct function for that object type. Which is what virtual functions do.

Further, from personal experience, the ACTUAL overhead from virtual functions is very small, and only in very extreme cases does it make a difference (the main case where the non-virtual function becomes inlined, and is so trivial that the overhead of calling a function is a substantial part of the total execution time (which also means the function needs to be called many times for it to make any significant difference). There is MORE overhead if you have to "work out what to do" (using if-statements or something like that) in some other way [other than implementing your own variation on "virtual function", but that's just reinventing the wheel, and unless your new wheel is better than the existing one, that's not a good idea].

like image 20
Mats Petersson Avatar answered Nov 03 '22 01:11

Mats Petersson