


Containers of Incomplete Types

Recursive containers
Type Erasure

Incomplete types allow type erasure and recursive data types, and C and C++ programmers have been using it for years to build complex data structures, like tree structures where a node may have an arbitrary number of children.

What about standard containers? Containers of incomplete types have been under discussion for a long time, as explained in Matt Austern's great article (The Standard Librarian: Containers of Incomplete Types):

Unlike most of my columns, this one is about something you can't do with the C++ Standard library: put incomplete types in one of the standard containers. This column explains why you might want to do this, why the standardization committee banned it even though they knew it was useful, and what you might be able to do to get around the restriction.

In 1997, shortly before the C++ Standard was completed, the standardization committee received a query: Is it possible to create standard containers with incomplete types? It took a while for the committee to understand the question. What would such a thing even mean, and why on earth would you ever want to do it? The committee eventually worked it out and came up with an answer to the question. (Just so you don't have to skip ahead to the end, the answer is "no.") But the question is much more interesting than the answer: it points to a useful, and insufficiently discussed, programming technique. The standard library doesn't directly support that technique, but the two can be made to coexist.

In a future revision of C++, it might make sense to relax the restriction on instantiating standard library templates with incomplete types. Clearly, the general prohibition should stay in place - instantiating templates with incomplete types is a delicate business, and there are too many classes in the standard library where it would make no sense. But perhaps it should be relaxed on a case-by-case basis, and vector looks like a good candidate for such special-case treatment: it's the one standard container class where there are good reasons to instantiate it with an incomplete type and where Standard Library implementors want to make it work. As of today, in fact, implementors would have to go out of their way to prohibit it!

C++11 standard is also cautious about incomplete types and STL: Other functions (...) 2. the effects are undefined in the following cases: (...) In particular - if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for that component. Fortunately Boost.Container containers are designed to support type erasure and recursive types, so let's see some examples:

All containers offered by Boost.Container can be used to define recursive containers:

#include <boost/container/vector.hpp>
#include <boost/container/list.hpp>
#include <boost/container/map.hpp>
#include <boost/container/stable_vector.hpp>
#include <boost/container/string.hpp>

using namespace boost::container;

struct data
   int               i_;
   //A vector holding still undefined class 'data'
   vector<data>      v_;
   //A list holding still undefined 'data'
   list<data>        l_;
   //A map holding still undefined 'data'
   map<data, data>   m_;

   friend bool operator <(const data &l, const data &r)
   { return l.i_ < r.i_; }

struct tree_node
   string name;
   string value;

   //children nodes of this node
   list<tree_node>        children_;

int main()
   //a container holding a recursive data type
   stable_vector<data> sv;

   //Let's build a tree based in
   //a recursive data type
   tree_node root;  = "root";
   root.value = "root_value";
   return 0;

Containers of incomplete types are useful to break header file dependencies and improve compilation types. With Boost.Container, you can write a header file defining a class with containers of incomplete types as data members, if you carefully put all the implementation details that require knowing the size of the value_type in your implementation file:

In this header file we define a class (MyClassHolder) that holds a vector of an incomplete type (MyClass) that it's only forward declared.

#include <boost/container/vector.hpp>


//We don't need to include "MyClass.h"
//to store vector<MyClass>
class MyClass;

class MyClassHolder

   void AddNewObject(const MyClass &o);
   const MyClass & GetLastObject() const;

   ::boost::container::vector<MyClass> vector_;

Then we can define MyClass in its own header file.


class MyClass
   int value_;

   MyClass(int val = 0) : value_(val){}

   friend bool operator==(const MyClass &l, const MyClass &r)
   {  return l.value_ == r.value_;  }

And include it only in the implementation file of MyClassHolder


#include "MyClassHolder.h"

//In the implementation MyClass must be a complete
//type so we include the appropriate header
#include "MyClass.h"

void MyClassHolder::AddNewObject(const MyClass &o)
{  vector_.push_back(o);  }

const MyClass & MyClassHolder::GetLastObject() const
{  return vector_.back();  }

Finally, we can just compile, link, and run!


#include "MyClassHolder.h"
#include "MyClass.h"

#include <cassert>

int main()
   MyClass mc(7);
   MyClassHolder myclassholder;
   return myclassholder.GetLastObject() == mc ? 0 : 1;