c++ - Ad hoc polymorphism and heterogeneous containers with value semantics

Question

I have a number of unrelated types that all support the same operations through overloaded free functions (ad hoc polymorphism):

struct A {};

void use(int x) { std::cout << "int = " << x << std::endl; }
void use(const std::string& x) { std::cout << "string = " << x << std::endl; }
void use(const A&) { std::cout << "class A" << std::endl; }

As the title of the question implies, I want to store instances of those types in an heterogeneous container so that I can use() them no matter what concrete type they are. The container must have value semantics (ie. an assignment between two containers copies the data, it doesn't share it).

std::vector<???> items;
items.emplace_back(3);
items.emplace_back(std::string{ "hello" });
items.emplace_back(A{});

for (const auto& item: items)
    use(item);
// or better yet
use(items);

And of course this must be fully extensible. Think of a library API that takes a vector<???>, and client code that adds its own types to the already known ones.

---

The usual solution is to store (smart) pointers to an (abstract) interface (eg. vector<unique_ptr<IUsable>>) but this has a number of drawbacks -- from the top of my head:

• I have to migrate my current ad hoc polymorphic model to a class hierarchy where every single class inherits from the common interface. Oh snap! Now I have to write wrappers for int and string and what not... Not to mention the decreased reusability/composability due to the free member functions becoming intimately tied to the interface (virtual member functions).
• The container loses its value semantics: a simple assignment vec1 = vec2 is impossible if we use unique_ptr (forcing me to manually perform deep copies), or both containers end up with shared state if we use shared_ptr (which has its advantages and disadvantages -- but since I want value semantics on the container, again I am forced to manually perform deep copies).
• To be able to perform deep copies, the interface must support a virtual clone() function which has to be implemented in every single derived class. Can you seriously think of something more boring than that?

To sum it up: this adds a lot of unnecessary coupling and requires tons of (arguably useless) boilerplate code. This is definitely not satisfactory but so far this is the only practical solution I know of.

---

I have been searching for a viable alternative to subtype polymorphism (aka. interface inheritance) for ages. I play a lot with ad hoc polymorphism (aka. overloaded free functions) but I always hit the same hard wall: containers have to be homogeneous, so I always grudgingly go back to inheritance and smart pointers, with all the drawbacks already listed above (and probably more).

Ideally, I'd like to have a mere vector<IUsable> with proper value semantics, without changing anything to my current (absence of) type hierarchy, and keep ad hoc polymorphism instead of requiring subtype polymorphism.

Is this possible? If so, how?

Answer 1

Different alternatives

It is possible. There are several alternative approaches to your problem. Each one has different advantages and drawbacks (I will explain each one):

1. Create an interface and have a template class which implements this interface for different types. It should support cloning.
2. Use boost::variant and visitation.

Blending static and dynamic polymorphism

For the first alternative you need to create an interface like this:

class UsableInterface 
{
public:
    virtual ~UsableInterface() {}
    virtual void use() = 0;
    virtual std::unique_ptr<UsableInterface> clone() const = 0;
};

Obviously, you don't want to implement this interface by hand everytime you have a new type having the use() function. Therefore, let's have a template class which does that for you.

template <typename T> class UsableImpl : public UsableInterface
{
public:
    template <typename ...Ts> UsableImpl( Ts&&...ts ) 
        : t( std::forward<Ts>(ts)... ) {}
    virtual void use() override { use( t ); }
    virtual std::unique_ptr<UsableInterface> clone() const override
    {
        return std::make_unique<UsableImpl<T>>( t ); // This is C++14
        // This is the C++11 way to do it:
        // return std::unique_ptr<UsableImpl<T> >( new UsableImpl<T>(t) ); 
    }

private:
    T t;
};

Now you can actually already do everything you need with it. You can put these things in a vector:

std::vector<std::unique_ptr<UsableInterface>> usables;
// fill it

And you can copy that vector preserving the underlying types:

std::vector<std::unique_ptr<UsableInterface>> copies;
std::transform( begin(usables), end(usables), back_inserter(copies), 
    []( const std::unique_ptr<UsableInterface> & p )
    { return p->clone(); } );

You probably don't want to litter your code with stuff like this. What you want to write is

copies = usables;

Well, you can get that convenience by wrapping the std::unique_ptr into a class which supports copying.

class Usable
{
public:
    template <typename T> Usable( T t )
        : p( std::make_unique<UsableImpl<T>>( std::move(t) ) ) {}
    Usable( const Usable & other ) 
        : p( other.clone() ) {}
    Usable( Usable && other ) noexcept 
        : p( std::move(other.p) ) {}
    void swap( Usable & other ) noexcept 
        { p.swap(other.p); }
    Usable & operator=( Usable other ) 
        { swap(other); }
    void use()
        { p->use(); }
private:
    std::unique_ptr<UsableInterface> p;
};

Because of the nice templated contructor you can now write stuff like

Usable u1 = 5;
Usable u2 = std::string("Hello usable!");

And you can assign values with proper value semantics:

u1 = u2;

And you can put Usables in an std::vector

std::vector<Usable> usables;
usables.emplace_back( std::string("Hello!") );
usables.emplace_back( 42 );

and copy that vector

const auto copies = usables;

You can find this idea in Sean Parents talk Value Semantics and Concepts-based Polymorphism. He also gave a very brief version of this talk at Going Native 2013, but I think this is to fast to follow.

Moreover, you can take a more generic approach than writing your own Usable class and forwarding all the member functions (if you want to add other later). The idea is to replace the class Usable with a template class. This template class will not provide a member function use() but an operator T&() and operator const T&() const. This gives you the same functionality, but you don't need to write an extra value class every time you facilitate this pattern.

A safe, generic, stack-based discriminated union container

The template class boost::variant is exactly that and provides something like a C style union but safe and with proper value semantics. The way to use it is this:

using Usable = boost::variant<int,std::string,A>;
Usable usable;

You can assign from objects of any of these types to a Usable.

usable = 1;
usable = "Hello variant!";
usable = A();

If all template types have value semantics, then boost::variant also has value semantics and can be put into STL containers. You can write a use() function for such an object by a pattern that is called the visitor pattern. It calls the correct use() function for the contained object depending on the internal type.

class UseVisitor : public boost::static_visitor<void>
{
public:
    template <typename T>
    void operator()( T && t )
    {
        use( std::forward<T>(t) );
    }
}

void use( const Usable & u )
{
    boost::apply_visitor( UseVisitor(), u );
}

Now you can write

Usable u = "Hello";
use( u );

And, as I already mentioned, you can put these thingies into STL containers.

std::vector<Usable> usables;
usables.emplace_back( 5 );
usables.emplace_back( "Hello world!" );
const auto copies = usables;

The trade-offs

You can grow the functionality in two dimensions:

• Add new classes which satisfy the static interface.
• Add new functions which the classes must implement.

In the first approach I presented it is easier to add new classes. The second approach makes it easier to add new functionality.

In the first approach it it impossible (or at least hard) for client code to add new functions. In the second approach it is impossible (or at least hard) for client code to add new classes to the mix. A way out is the so-called acyclic visitor pattern which makes it possible for clients to extend a class hierarchy with new classes and new functionality. The drawback here is that you have to sacrifice a certain amount of static checking at compile-time. Here's a link which describes the visitor pattern including the acyclic visitor pattern along with some other alternatives. If you have questions about this stuff, I'm willing to answer.

Both approaches are super type-safe. There is not trade-off to be made there.

The run-time-costs of the first approach can be much higher, since there is a heap allocation involved for each element you create. The boost::variant approach is stack based and therefore is probably faster. If performance is a problem with the first approach consider to switch to the second.