Why C++ containers don't allow incomplete types?

20
votes

Why doesn't C++ allow containers of incomplete types to be instantiated?

It's certainly possible to write containers that don't have this restriction -- boost::container is completely capable of doing this. As far as I can see, it doesn't seem to give any performance or other type of gain, and yet the standard declares it to be undefined behavior.

It does prevent recursive data structures from being built, for example.

Why then does the C++ standard impose this arbitrary restriction? What would have been the downside of allowing incomplete types as template parameters wherever possible?

1
c++templatesstlincomplete-type
Because containers, unless they store pointers, needs the size of the object type it stores? – Viktor Sehr
Why do you think they don't? I can't find any such restriction in the C++11 standard. – Mike Seymour
@ViktorSehr: All standard containers except array do (directly) store pointers, not objects; so they shouldn't need the type to be complete until they need to allocate one or more objects. – Mike Seymour
@MikeSeymour: Because C++11 says, "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". – user541686
@n.m. It's impossible to swap the elements of an array without invalidating iterators. It you swapped by moving the elements, iterators would no longer refer to the same object. Also, swap is required to take constant time for most containers, which is impossible if it has to swap each element. – Mike Seymour

1 Answers

19
votes

Matt Austern, the chair of the C++ standardization committee's library working group, explained this decision of the committee in his Dr. Dobb's article by historical reasons:

We discovered, with more testing, that even the [simple] 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.

My understanding of this is that the committee did not want to invalidate existing implementations of the library by requiring them to support incomplete types retroactively.

In the same article he concedes that

In a future revision of C++, it might make sense to relax the restriction on instantiating standard library templates with incomplete types.

Given that the article dates back to 2002, and the prohibition remains in place in the current standard, I think that the decision of the boost designers not to wait for the future and build their own containers that allow incomplete types was fully justified.

Edit: See this answer for information on using incomplete types allowed by C++17 standard for some containers in the Standard C++ Library.