Concept Based Polymorphism

Problem

We often wish to collect data into containers in order to manage large numbers of things. To put it less correctly but more clearly, we want collections of objects that represent a family. The reason this is wrong is because fundamental types aren't often thought of as objects, and really we aren't talking about families, rather things to be processed a certain way. Why this distinction matters, I hope, will become clear.

Base Class Solution

The almost reflexive solution is to derive everything from a common base class. Ideally this is an interface class that is pure virtual. There are a number of problems with this. Many experts, and I also agree, call this the most abused feature of C++.

Fundamental types, and STL types do not inherit from anything requiring they be wrapped. Often objects bridge responsibilities requiring either multiple interfaces, or overly broad interfaces (kitchen sink classes).
Classes often are shoehorned into an interface, the famous birds analogy. When ostriches and emus refuse to fly, are they no longer birds?

Inheritance is often not a good solution.

Internal Polymorphism

Classes could be internally polymorphic. They could rely on internal flags to determine what kind of thing they are today, and this one, amorphous blob class can, internally, be whatever it wants. This is too horrific to consider further.

Adaptor and Decorator Classes

We could wrap the class. How much do we wrap? Do we need every function adapted? Doesn't that start to bring back the same problem? Wrapping can also be tedious as it is difficult to automate. What if a class needs to behave as if it has functionality, but it doesn't. What if they have different memory sizes? We are getting close, but aren't quite there.

Solution

Wrapping data has some definite benefits. We don't need to modify the classes. They can be written in a way that best expresses their use without imposing design from outside. But how do we solve the wrapping problems. We can use Concepts, and non-member functions.

Concepts

Concepts are a generic programming term that describes operations on a type. It's like an interface class, but there is no inheritance and as of now, no compiler support, but that's OK. We can still use them. A Concept is really just a generic programmer telling programmers who use his stuff what functions and signatures are required. We've been using these all along. When we increment an iterator, there is no base class that defines that functionality. It's part of the documentation. Therefore, we can pass iterators into generic algorithms that expect that functionality.

Non-Member Functions Increase Encapsulation

I know. This is just wrong! Wrong, wrong, wrong, wrong, wrong, wrong, wrong!

Except it's not.

The reason we encapsulate things is to protect us against change. If I directly manipulate the data in a struct, that would not be well encapsulated. On the opposite extreme, it's hard to get better encapsulation than objects who's entire functionality resides in its constructor and destructor.

Encapsulation is measured by the number of functions that have to be changed if we change the implementation of our class. A class with n functions is more encapsulated than a class with n+1 functions. Non-member, non-friend functions do not increase n.

Here's an even bigger one. By using non-member functions, we effectively have polymorphism via function overloading. Rather than object->Draw(), and needing VTables, we can Draw(object) and leave it to compile time. This makes the problem much easier to solve.

Really, The Solution

Always start by writing the code you wish to write.

class MyClass
{
};

void Draw(const MyClass& mc, ostream& out, size_t position)
{
  out << "MyClass" << endl;
}

int main()
{
  Document document;
  document.reserve(5);

  document.emplace_back(0);
  document.emplace_back(string("Hello"));
  document.emplace_back(document);
  document.emplace_back(MyClass());

  reverse(begin(document), end(document));
  reverse(begin(document), end(document));

  Draw(document, cout, 0);
  return 0;
} 

We have a collection of things that have no relation whatsoever to one another, yet we are adding them to a common container. How does this work?

Here's the whole thing.

#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <memory>

template <typename T>
void Draw(const T& x, std::ostream& out, size_t position)

 out << std::string(position, ' ') << x << std::endl;
}

class DrawConcept
{
public:
 template <typename T>
 DrawConcept(const T& x) : m_object(new model<T>(x))
 {
  std::cout << "Ctor" << std::endl;
 }

 DrawConcept(const DrawConcept& x) : m_object(x.m_object->copy_())
 {
  std::cout << "Copy" << std::endl;
 }

 DrawConcept(DrawConcept&& x) : m_object(std::move(x.m_object)) {;}

 DrawConcept& operator=(DrawConcept x)
 {
  m_object = std::move(x.m_object); return *this;
 }

 friend void Draw(const DrawConcept& x, std::ostream& out, size_t position)
 {
  x.m_object->draw_(out, position);
 }

private:
 struct concept_t
 {
  virtual ~concept_t() {;}
  virtual concept_t* copy_() = 0;
  virtual void draw_(std::ostream& out, size_t position) const = 0;
 };

 template <typename T>
 struct model : concept_t
 {
  model(const T& x) : m_data(x) {;}
  concept_t* copy_() { return new model(*this); }
  void draw_(std::ostream& out, size_t position) const
  {
   Draw(m_data, out, position);
  }
   T m_data;
 };
 std::unique_ptr<concept_t> m_object;
};

typedef std::vector<DrawConcept> Document;

void Draw(const Document& x, std::ostream& out, size_t position)
{
 out << std::string(position, ' ') << "<document>"<< std::endl;
 for(auto& e : x) Draw(e, out, position + 2);
 out << std::string(position, ' ') << "</document>"<< std::endl;
}

To see how it works, let's take it apart.

struct concept_t
  {
    virtual ~concept_t() {;}
    virtual concept_t* copy_() = 0;
    virtual void draw_(std::ostream& out, size_t position) const = 0;
  };

This is just a simple interface class. Note the copy_(). This is to ensure we get a copy of the actual derived class, not the base class. It's also written as clone().

The derived class is next.

template <typename T>

  struct model : concept_t

  {

    model(const T& x) : m_data(x) {;}

    concept_t* copy_() { return new model(*this); }

    void draw_(std::ostream& out, size_t position) const

    {

      Draw(m_data, out, position);

    }

     T m_data;

  };

This is the wrapper around the draw-able object. By deriving from concept_t we get an object that we can hold type agnostic. By templatizing the class, we can hold anything. Copy returns a derived class copy, but the real trick is the draw function. Here we take the virtual member draw and make it a non-member draw, allowing compile-time polymorphism.

There's just one more piece.

template <typename T>
 DrawConcept(const T& x) : m_object(new model<T>(x))
 {
    std::cout << "Ctor" << std::endl;
 } 

Even though the constructor is templatized, this is not a template class. That's important, because if it was it would be impossible to add to containers.

That's it.

The template function at the top is optional. It provides a common way to draw, but can be overloaded if an object has a different way to draw such as MyClass above.

The rest is just copy and assignment code common to most classes.

Conclusion

There are alternatives to typical inheritance. By using concept based polymorphism, you can leave your class interface alone to be the best representation of your abstraction and not a collection of externally forced design. Returning to those birds that refuse to fly, simply don't add them to a fly concept. If you do, rather than have a silent error running in your game, the compiler will squawk (pun intended) and the error gets fixed.

References

Sean Parent's excellent talk

Adobe Run Time Concepts

Swaptimizations - exploiting copy elision and RVO

Performance critical code for years has relied on passing everything by pointers to heap allocated objects. Often this is not the best, or even the fastest way to do this. Passing by value and returning by value use stack based entities which are much faster to allocate, de-allocate, and don't cause fragmentation of memory.

"C++ is my favorite garbage collected language because it generates so little garbage" - Bjarne Stroustrup

This is true if you write in such a way as to make this true. Smart pointers made it pretty easy to eliminate memory leaks, but it can be even better. Using RVO and copy elision we can pass by value pretty much all the time without the overhead of temporaries. Consider this code:

Texture MakeBigTexture
{
  Texture bigTexture();
  Do stuff
  return bigTexture;
}

void Init()
{
  Texture temp = MakeBigTexture();
}

This code seems wrong. What about the giant temporary? It doesn't exist. Compilers have long taken advantage of Return Value Optimization or RVO. The way it works is that the compiler knows the return is temporary. It also knows where it will ultimately end up. Why not put the temporary where it will ultimately end up? And that's what it does. 
Copy elision is the opposite. Here's an example

string FlipString(string str)
{
  reverse(str.begin(), str.end());
  return str;
}

string Source()
{
  return "Flip This String";
}

void main
{
  cout << FlipString(Source()) << endl;
}

The output of Source is a temporary so again the compiler moves the temporary to its final destination. In this case str.
Now the tricky part. You do not get RVO here. The reason is kind of simple. The compiler can put a temporary in one place or the other, but not both. So we will get a copy. But what if that copy is too expensive? Do we have to revert to pointers and references? No. We can do Swaptimization. Here's how it works.

string FlipString(string str)
{
  string result;
  result.swap(str);
  reverse(result.begin(), result.end());
  return result;
}

string Source()
{
  return "Flip This String";
}

void main
{
  cout << FlipString(Source()) << endl;
}

Result uses RVO and str uses copy elision. C++ 11 gives us rvalues and so we don't need to do this, but that is for another time.