...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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: “17.6.4.8 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; sv.resize(100); //Let's build a tree based in //a recursive data type tree_node root; root.name = "root"; root.value = "root_value"; root.children_.resize(7); 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> //MyClassHolder.h //We don't need to include "MyClass.h" //to store vector<MyClass> class MyClass; class MyClassHolder { public: void AddNewObject(const MyClass &o); const MyClass & GetLastObject() const; private: ::boost::container::vector<MyClass> vector_; };
Then we can define MyClass
in its own header file.
//MyClass.h class MyClass { private: int value_; public: 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
//MyClassHolder.cpp #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!
//Main.cpp #include "MyClassHolder.h" #include "MyClass.h" #include <cassert> int main() { MyClass mc(7); MyClassHolder myclassholder; myclassholder.AddNewObject(mc); return myclassholder.GetLastObject() == mc ? 0 : 1; }