Introducing emplacer: allocate subtypes of an abstract base class directly in a container

The Problem

A few weeks ago I was working on a toy C++ project. I needed something similar to the HTML DOM, so I created a few classes.

class Node {
public:
/* ... */
        virtual std::string nodeName() = 0;  // At least one pure virtual method
};

class TextNode : public Node {
/* ... */
};

class ElementNode: public Node {
/* ... */
};

But then I did something dumb. I tried to make a vector of Nodes.
typedef std::vector<Node> NodeList;

And of course, when I went to use my NodeList, the compiler spewed a page of errors at me.  I was confused for a moment, but then it became obvious. You can't create an instance of an abstract base class. That's what the "abstract" part of "abstract base class" means. But creating a vector of them is asking the STL to do exactly that.

If you're not familiar with abstract base classes in C++, I suggest you read a tutorial on polymorphism in C++, such as this one. But suffice to say, you create pointers or references to them, and the pointers point to (and the references refer to) instances of concrete derived classes that inherit from the base class.  So you might have an ElementNode, and call a function that takes a Node&, and pass your ElementNode& to it instead, and it can call nodeName() on it, and the right function is called at runtime. (The compiler adds a pointer to a vtable somewhere in the object, and that vtable is consulted to see which function call.)

The Real Problem

So I told the compiler I wanted a std::vector<Node>. And the compiler told me no, that doesn't make sense. And it's right, of course.

So what did I really want? Well, I wanted a vector that can hold any subclass of Node. So how do I ask the compiler to do that?

(As a side note, the normal way to do this is to create a std::vector<Node*>, or perhaps a smart pointer version of that. I didn't want to do that because I didn't want separate memory allocations for each element of the vector.)

The most obvious way is with an union.

struct NodeAny {

        enum {TEXT, ELEMENT} nodeType;

        union {

                TextNode textNode;

                ElementNode elementNode;

        };

};

But there's a bunch of problems with that.

• You need a way to call the constructor of the whichever node type it currently is.
• The "nodeType" member is duplicating the purpose of the vtable. By that I mean, if you write some methods on this class, they're probably all going to switch on nodeType. But that's dumb, because that's what C++'s runtime subtype polymorphism does for you.
• There's also no way to make this generic, you can't write a variadic template union that takes a series of types to union together.

The Solution

So I complained to my friend Jeremy that C++ should be able to do this. This isn't Java, I shouldn't have to do a separate allocation for each object. (Side note: I've heard that Java's heap is actually faster than C's. Since it's garbage collected, it can basically just use a stack, and then compact things later.)

In the past, he had also wanted this functionality, and so my complaints spurred him to create emplacer. I then forked it and attempted to improve it, and added an example.

emplacer acts similar to a smart pointer to the base class. This means you have to use * or -> to access the pointed-to class.

Originally, to define one, you would do something like this:

typedef type_collection<ElementNode, TextNode> NodeSubclasses;

typedef emplacer<Node, NodeSubclasses> NodeAny;

But once we started really using it, we realized a problem with that. The compiler and debugger (and also valgrind) always expand out the name instead of using the typedef. Once we had 12 or so subclasses, whenever we made a compiler error, we started seeing some of the longest typenames we had ever seen. (And in C++, that is saying something.)

Eventually I realized that we could replace the second typedef with a new class, like this:

struct NodeAny : public emplacer<Node, NodeSubclasses> {

using emplacer::emplacer;

};

The using line is a C++11ism, and pulls in the constructors from the base class emplacer.

How It Works

emplacer has two private members, "char data[]" and "bool live".

The size and alignment of "data" are determine at compile time by the template arguments. This is done using type_collection has constexpr methods to calculate the max alignment and max size of any of the types it holds.

So each emplacer instance is big enough to hold the largest subclass. It uses placement new and manual destructor calls on "data".

"live" keeps track of whether or not the emplacer instance has been "emplace"ed. Or in other words if it has called placement new on "data". Most operations throw a std::logic_error if the object is not live.

emplacer implements operator*() and operator->(). They both do "return *reinterpret_cast<Type *>(data);", where Type is the abstract base class, and where they're defined to return by reference. The rest of the magic is done for us by C++'s subtype polymorphism.

How To Use It

First you'll need a class hierarchy with an abstract base class and some polymorphic subclasses. (I.e. the base class should have a bunch of pure virtual functions for the derived classes to implement.)

Then you'll want to create a typedef of the type_collection template, and subclass of emplacer. There's an example of that in the "The Solution" section, and also in the example .cc file in the gist.

You can then make an instance on the stack just like any other class.

ShapeAny my_shape;

If you're using my version, and if the first type in the type_collection is default constructible, and my_shape runs the default constructor of that first type. Otherwise, my_shape is not live, and trying to dereference it throws an exception.

In any case, you can run emplace on it to initialize or reinitialize it.

my_shape.emplace<Circle>(1);

If the object was live, it first calls the destructor by hand, and then calls the constructor, using placement new. Remember all of this is done on the stack memory (or heap, or global, or where ever it's allocated) that my_shape is already using, no additional allocations are done by emplacer. (But of course the class constructed can allocate memory in its constructor.)

My version also has copy and move constructors that accept the SubTypes, so you can do something like this:

ShapeAny my_shape(Circle(1));

(Speaking of copy constructors, emplacer implements a real copy constructor too, so you can copy instances of the emplacer.

This was kind of tricky to implement, since constructors cannot be virtual. At one point I was storing a pointer to the constructor of the last constructed type. But I didn't like taking up extra memory for that, so now I'm using type_collection and comparing typeids until I find the right class to construct. This uses less memory but is probably slower.)

You can call any method of the base class on it by using "->" instead of ".". You can pass it to any function that takes a base class reference by passing in *my_shape, or if it takes a pointer, &*my_shape.

As alluded to earlier, you can also use it in containers. Here's an example:

 std::vector<ShapeAny> shapes;

 shapes.emplace(shapes.end())->emplace<Rect>(3, 4);
 shapes.emplace(shapes.end())->emplace<Square>(3);

 //emplace returns reference to *this, so you can use it like this too
 shapes.push_back(ShapeAny().emplace<Rect>(5, 6));
 shapes.push_back(ShapeAny().emplace<Circle>(1));

 for (auto shape: shapes) {
  std::cout << shape->area() << std::endl;
 }

Conclusion

I think that emplacer is pretty useful. I searched, but I couldn't find anything else online like it. Boost has a couple of classes like Boost::Any and Boost::Variant, but both of them solve related but different problems.

While I suspect that emplacer is fast, I haven't done any benchmarking yet. The copy/move constructors and assignment operators might be slow since they search the class hierarchy, though I'm hoping the compiler can make them fast anyway.

One thing that I find interesting is that subtype polymorphism is more or less equivalent to a tagged union. But the former tends to be much easier to work with in C++. But there's a gap with what you can do with base classes, and emplacer fills that gap.

I hope you find it useful.

• Jeremy's original version of emplacer
• My own version with a few attempts at enhancement and an example