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.
Incomplete Types
We're all used to incomplete types, in the familiar form of forward declarations [1]. If you declare a class T, you can use it in limited ways even before it is defined. (That is, before its definition is finished: a class is incomplete within its definition.) You can work with pointers and references of type T* and T&; you can write functions that have such pointers and references as part of their signature; you can even declare an extern object of type T. Some of what you can't do: you can't use pointer arithmetic, you can't define variables of type T, you can't write new T, you can't inherit from T, and you can't use sizeof.
This isn't a random list. All of these things follow from the fact that, as the Standard points out in a footnote, "The size and layout of an incompletely-defined object type is unknown." If a type is incomplete, you can't do anything that would require knowing its size or layout. How can you create an object of type T without knowing how large that object has to be? The declaration:
class T;
tells the compiler that T is a class or struct. (As opposed to, say, a built-in type or an alias for some other class.) That's enough for the compiler to know how to deal with pointers or references to T, but not enough to create a T object: how much memory would the compiler allocate for such an object, and how would it lay out the fields? Similarly, pointer arithmetic makes no sense because an expression like p += 1 requires the compiler to know the size of the object that p points to.
Why would you want to have a pointer to a type when all you've got is a forward declaration? The classic example is what Kernighan and Ritchie [2] call "self-referential structures": a class that contains a pointer to itself, like a list node or a tree node. For example:
struct int_list_node { int value; int_list_node* next; };
Within the class definition, int_list_node is itself an incomplete type: it isn't complete until the compiler has seen the full class definition. It would be illegal for next to be of type int_list_node (how could a class contain an instance of itself?), but a pointer or reference to int_list_node is fine.
Naturally, self-referential structures aren't the only place where incomplete types come in handy. They're necessary if your design involves classes that point to instances of each other, or even if it involves tightly coupled classes that are friends of each other:
class int_list; struct int_list_node; class int_list { friend class int_list_node; ... }; struct int_list_node { friend class int_list; ... };
This example illustrates an important aspect of incomplete types: a type that is incomplete at one point in a file can be completed later on. Here, int_list is an incomplete type after its forward declaration appears, but a complete type after its full class definition.
Finally, forward declarations can be used as a technique for data hiding, for decoupling an interface from its implementation [3]. You can provide a forward declaration of an "opaque type" my_class in a header file and then declare a functional interface that provides whatever operations are required. (You might choose to expose the full class definition elsewhere, or perhaps not at all.) Naturally, there are some limitations on what the functions in that header file might look like. You could write:
my_class& clone(const my_class&);
but you couldn't write:
int illegal_function(my_class);
or:
my_class illegal_function();
You can't pass or return incomplete types by value, for the same reason that you can't define variables of an incomplete type. And, of course, the restriction applies to member functions just as it applies to stand-alone functions. Just as you can't write illegal_function above, so you can't write:
struct illegal_class { my_class f(); };
Incomplete Types and Templates
A good starting point for understanding how incomplete types work for templates is the usual rule of thumb: when you see a class template X<T>, imagine that it's just a normal class, and that every time you see T in the class definition, it's replaced with some specific type. If you replace T with an incomplete type and you get a legal class, then you're on pretty solid ground in assuming that X<T> can be instantiated with an incomplete type. So, for example, you can write a templatized version of the list node class that we saw above:
template <class T> struct list_node { T value; list_node<T>* next; };
The incomplete type is list_node<T>, not T itself. Can you define an incomplete type as the argument to a template? Certainly! The C++ Standard [4] even says so explicitly. You can't instantiate list_node with an incomplete type (that would be illegal; we've got a member variable of type T), but that's because of the specifics of list_node, not because of any special restrictions on templates. There's nothing wrong with this:
template <class T> struct ptr_list_node { T* ptr_value; ptr_list_node<T>* next; }; class my_class; ptr_list_node<my_class> p;
It's legal to instantiate ptr_list_node with class my_class, even though all we have for my_class is a forward declaration; it's even legal to have a variable of type ptr_list_node<my_class>. In this respect, there's no real difference between a class template like list_node or ptr_list_node, and an ordinary class like int_list_node.
Combining forward declarations with templates does, however, introduce a few new wrinkles that you don't see with non-template classes.
Consider, for example, this class:
template <class T> struct X { T f() { T tmp; return tmp; } };
This looks a lot like the illegal_class example that we saw above. We have a member function, f, that returns T by value, and we've got a local variable of type T. Obviously these are things you can't do when T is an incomplete type, so you might think that writing X<my_class> is illegal if all we have of my_class is a forward declaration. In fact, however, there's nothing wrong with it. Why?
The point is technical, but simple: a function template isn't checked for errors unless it's instantiated (except for trivial syntactic errors), and a member function isn't instantiated unless it's used. It would be illegal to call X<my_class>().f() (you'd be using my_class in a way that's illegal for an incomplete type), but merely writing X<my_class> is fine; it doesn't trigger the instantiation of anything that would be a problem.
This isn't a very interesting example, of course: X<my_class> has nothing but one unusable member function. It does, however, serve as a reminder that we should pay attention to exactly where things are instantiated. When we're mixing templates and incomplete types, there are two important points in the program: the point at which the incomplete type is completed (that is, the point when we see a class definition instead of just a forward declaration), and the point of instantiation. Between those two points, interesting things can happen. You might, for example, instantiate X<my_class>, then define my_class, and only then instantiate X<my_class>::f.
template <class T> struct X { T f() { T tmp; return tmp; } }; class my_class; X<my_class> x; class my_class { ... };
Why would you ever want a delicate chain of definitions like this? There's one important reason: it lets you use X<my_class> in the definition of my_class itself. You can have a member variable of type X<my_class>, and you can even inherit from X<my_class>. This may seem circular, and it may seem almost as if my_class is inheriting from itself, but it's no more circular than a class like int_list_node that contains a pointer to itself. Each step in the chain is legal: X is written in such a way so that it can be instantiated with an incomplete type, and we're certainly free to define the complete type later.
We've now almost arrived at something realistic. In practice, of course, you probably wouldn't bother with the forward declaration: you would just define my_class right away and use X<my_class> within it. (Within a class definition, the compiler always acts as if it has seen a forward declaration of the class that's being defined.) Barton and Nackman [5] showed how to use this technique for base classes that govern structure and policy, as in:
class ComplexFloat : public FieldCategory<ComplexFloat> { ... };
The base class encapsulates that which is common to all types that model the mathematical definition of a field. The base and derived classes are mutually dependent: FieldCategory requires functions like operator*= from ComplexFloat, and, in turn, it provides functions like pow and repeat to ComplexFloat.
Standard Containers
We've come pretty far from the original question. We've talked about incomplete types and about templates, but we haven't yet mentioned the standard containers. The Standard doesn't define them in terms of the "curiously recurring template pattern," as this technique has come to be known [6]. So where do containers of incomplete types come in?
We've seen several kinds of near-circularity that are enabled by forward declarations, but there's another kind we haven't yet seen. A class like int_list_node contains a pointer to another int_list_node, but that's not very flexible. First, we may want to have a node that refers to N other nodes, not just one. (Lots of applications involve tree structures where a node may have an arbitrary number of children — consider XML, for example.) Second, pointer semantics might just not be very convenient [7]. Obviously, we can't define a class X that contains an array of X objects — and even if we could, arrays aren't variable sized. But might we be able to do something like this instead?
struct tree_node { int value; std::vector<tree_node> children; };
To all external appearances, it looks like a class where each object contains N other instances of the same object. That's by design: STL containers like vector closely resemble built-in arrays. A node's ith child is just n.children[i], and, because the children are tree_node objects rather than mere pointers, we can copy an entire subtree with the single line:
tree_node n2 = n1;
without needing to worry about memory protocols or explicit deep copies. It looks circular, but the appearance of circularity doesn't necessarily make it illegal; as we've seen, not everything that looks circular really is. All that's necessary is that it's possible to define a vector<T> where T is an incomplete type.
When the standardization committee first realized that this was an open question, the tree_node example was the first test I tried. I didn't know what to expect; I certainly knew that the person who implemented that particular version of std::vector (me) hadn't ever thought of such a possibility. To my amazement, it worked! Soon we started thinking of more possible applications — Greg Colvin, for example, had a use for a finite-state machine where each state object contained an std::map<int, state>:
struct state { int value; std::map<int, state> next; };
Alas, the state machine was our first sign that this wasn't so simple as we had hoped. The state machine failed to compile, and, after a moment's thought, we realized that we shouldn't have bothered to try — it should have been obvious that nothing like that could have worked. Then we discovered, with more testing, that even the tree_node example didn't work with every STL implementation. In the end, it all seemed too murky and too poorly understood; the standardization committee didn't think there was any choice except to say that STL containers aren't supposed to work with incomplete types. For good measure, we applied that prohibition to the rest of the standard library too. Would it make sense to have an std::complex<T>, or an std::basic_istream<Char>, where T or Char hasn't been defined yet? Almost certainly not.
The C++ Standard [8] says that you're not allowed to instantiate a standard library template with an incomplete type: "the effects are undefined ... if an incomplete type is used as a template argument when instantiating a template component." Some implementations do permit it in some circumstances, but that's just an accident. (Remember, "undefined behavior" covers absolutely anything — including things working as you might expect them to!)
In retrospect, now that the technology is better understood, that decision still seems basically right. Yes, in some cases it's possible to implement some of the standard containers so that they can be instantiated with incomplete types — but it's also clear that in other cases it would be difficult or impossible. It was mostly chance that the first test we tried, using std::vector, happened to be one of the easy cases.
It's easy to see that defining an std::map<K, V>, where K or V is an incomplete type, is quite hopeless. The value type of an std::map<K, V>, after all (that is, the kind of object that's stored in the container) is std::pair<const K, V>. In turn, pair<T1, T2> has a member variable of type T1 and another one of type T2. You can't have member variables of an incomplete type, and that's what this would mean: instantiating map<K, V> necessarily requires instantiating pair<const K, V>.
What about the other standard containers, like list or set? Here we get into implementation details; it's hard to come up with a firm proof that instantiating std::list<T> or std::set<T> is impossible. But it's easy to see why it won't work with current implementations of those containers, and why an implementation that allowed it to work would be anything but straightforward. These containers are usually implemented in terms of nodes; a set's node, for example, might look something like this:
template <class V> struct rb_tree_node { V value; rb_tree_node *parent, *left, *right; bool color; };
The problem, of course, is the value member variable: it means that we can't instantiate rb_tree_node with an incomplete type, which, in turn, means that (if set is implemented this way) we can't instantiate set with an incomplete type. Is it possible to implement set in a way that gets around this restriction? Probably. But, as far as I know, nobody has ever tried — and probably nobody will, because the obvious ways of getting around it would make set larger or slower or both.
With vector, it's the other way around. The C++ Standard doesn't say how vector<T> is supposed to be implemented, but in this case the obvious implementation is one that allows T to be an incomplete type. The straightforward way to write std::vector is something like this:
template <class T, class Allocator> class vector { ... private: Allocator a; T* buffer; typename Allocator::size_type buffer_size; typename Allocator::size_type buffer_capacity; };
Nothing in this requires T to be a complete type; a forward declaration is quite good enough. And none of the obvious variations (inheriting from Allocator, using three pointers instead of a pointer and two integers, and so on) affect this. Indeed, when I reran my tree_node test for this column, it passed on the first three compilers I tried [9].
Conclusion
Where does that leave us? A design like the recursive tree_node is very nice for some purposes, but, as we've seen, we can't have it: it's expressly forbidden by the C++ Standard. But this doesn't necessarily mean that the standard library is useless for this sort of design. The important idea is the seemingly circular design where a class X contains, as a member variable, a container whose value type is X: it's the next best thing to a class that contains itself. The C++ Standard says you aren't allowed to use any of the standard container classes, but the standard containers aren't the only options. The C++ Standard defines a container interface, not just a set of unrelated classes, and any container class conforming to that interface fits into the library framework just as well as the predefined classes like list and set.
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!
Notes
[1] Actually, there are two other kinds of incomplete types: arrays whose size is unknown, and void, which behaves like an incomplete type that can't ever be completed. See 3.9, paragraph 6, of the C++ Standard. However, the most important kind of incomplete type is a class that has been declared but not yet defined; it's the only kind that I'll discuss.
[2] B. W. Kernighan and D. M. Ritchie. The C Programming Language, First Edition (Prentice-Hall, 1978). I meant it when I said that this was "the classic example"!
[3] This is a well-known technique for managing dependencies in large programs. See, for example, J. Lakos's Large Scale C++ Design (Addison-Wesley, 1996). One classicexample of this technique is the familiar C stdio library.
[5] J. J. Barton and L. R. Nackman. Scientific and Engineering C++ (Addison-Wesley, 1994.)
[6] J. O. Coplien. "A Curiously Recurring Template Pattern," February 1995, <http://creport.com>.
[7] See my column "The Standard Librarian: Containers of Pointers," C/C++ Users Journal Experts Forum, <www.cuj.com/experts/1910/austern.htm>.
[8] 17.4.3.6, paragraph 2; this is the part of the Standard that discusses general requirements that the standard library places on user components.
[9] The three compilers I tried were g++ 2.95, Microsoft Visual C++ 7.0, and Borland C++ 5.5.1. Why did these results differ from the ones I got four years ago? I suspect it's because of changes in the compilers, not in the library implementations; some older compilers failed to obey the rule that an unused member function of a class template shouldn't be instantiated.
Matt Austern is the author of Generic Programming and the STL and the chair of the C++ standardization committee's library working group. He works at AT&T Labs — Research and can be contacted at [email protected].
