20

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?

Leon
  • 31,443
  • 4
  • 72
  • 97
user541686
  • 205,094
  • 128
  • 528
  • 886
  • 9
    Because containers, unless they store pointers, needs the size of the object type it stores? – Viktor Sehr Sep 07 '13 at 10:10
  • 1
    Why do you think they don't? I can't find any such restriction in the C++11 standard. – Mike Seymour Sep 07 '13 at 10:17
  • 2
    @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 Sep 07 '13 at 10:18
  • 5
    @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 Sep 07 '13 at 10:20
  • @Mehrdad: Fair enough, I didn't find that clause. – Mike Seymour Sep 07 '13 at 10:21
  • 1
    "All standard containers except array do (directly) store pointers" — \[citation needed\]. – n. m. could be an AI Sep 07 '13 at 10:24
  • @n.m.: Containers cannot store the objects directly inside them because, as far as I know, `swap` must not invalidate their iterators. This is only possible if they store the objects elsewhere and point to them instead, which does not require knowing the objects' sizes. – user541686 Sep 07 '13 at 10:26
  • @Mehrdad: "This is only possible if they store the objects elsewhere" — this makes no sense. Since when is it impossible to swap two elements of an array? – n. m. could be an AI Sep 07 '13 at 10:32
  • @n.m. They use the provided allocator to create objects, and that gives them pointers. If you insist on a citation, "23.2.1/7 Unless otherwise specified, all containers defined in this clause obtain memory using an allocator". – Mike Seymour Sep 07 '13 at 10:33
  • 2
    @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 Sep 07 '13 at 10:35
  • @n.m.: If you had two vectors that stored their data inside themselves and they had different sizes, swapping them would destroy (and create) some objects. That means their iterators must be invalidated, which is prohibited by `swap`. – user541686 Sep 07 '13 at 10:36
  • @Mehrdad: I'm sorry I'm obviously have no idea what I'm talking about, or why. Please pay no attention to what I've written. – n. m. could be an AI Sep 07 '13 at 10:39
  • @MikeSeymour: there is a difference between swapping two vectors and swapping two elements of the same vector. I'd appreciate if everyone would make it crystal clear what kind of swap is meant from the get go. – n. m. could be an AI Sep 07 '13 at 10:45
  • @n.m. I'm talking about the `swap` function, applied to vectors. Swapping two vectors doesn't move the elements; any references or iterators to them remain valid after the swap. – Mike Seymour Sep 07 '13 at 10:47
  • 1
    @n.m.: We're talking about `swap` on vectors, and we're telling you it *must not* swap their elements because that would invalidate iterators. This implies the items *cannot* have been directly stored in the `vector` (the vector must be storing pointers instead), so the vector doesn't need to know their sizes upon instantiation of its type. – user541686 Sep 07 '13 at 10:49
  • OK so I have misunderstood your claims. – n. m. could be an AI Sep 07 '13 at 10:49
  • Related to [class-or-struct-self-reference-by-template](https://stackoverflow.com/questions/32487575/class-or-struct-self-reference-by-template). – Jarod42 Sep 12 '19 at 16:27

1 Answers1

20

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • 1
    The Dr. Dobbs article is pretty obsolete. Boost has implemented it now, and it's obviously possible. Your last sentence makes some sense but the Dr. Dobbs article doesn't... – user541686 Sep 07 '13 at 10:31
  • 2
    @Mehrdad Standard committees (as most committees) are very slow at making decisions. Sometimes, it's a good thing; sometimes (as I think is the case with the standard library of C++) it's too restrictive. The age of this article is a good proof: this restriction should have been lifted for a long time now, at least on the `std::vector`. – Sergey Kalinichenko Sep 07 '13 at 10:37
  • 1
    I honestly don't think they were "slow"... and the idea that they wouldn't want to require libraries to support this retroactively is weird. It's a new C++ standard after all -- there are tons of much more complicated changes to add; what's the benefit of not adding this? – user541686 Sep 07 '13 at 10:52
  • 1
    @Mehrdad I think that the only "benefit" here is letting some existing implementations to remain unchanged. In particular, I don't think there's any logical reason to keep the ban in place for `std::vector`, because internally it's pretty much a pair of pointers. – Sergey Kalinichenko Sep 07 '13 at 11:38
  • If I use incomplete type `struct R;` between this forward declaration and further definition `struct R { int payload; V v; };` as `using V = std::shared_ptr< std::vector< R > >;`, is it still undefined behaviour? If so, should I always use raw pointers for similar purposes (to defining recursive `struct`s)? – Tomilov Anatoliy Jan 13 '15 at 08:11
  • @Orient According to [this answer](http://stackoverflow.com/q/5606750/335858) `std::shared_ptr` to an incomplete type should be OK. – Sergey Kalinichenko Jan 13 '15 at 14:43
  • Hi @dasblinkenlight, I know you have forgotten you answered this almost 7years ago :-) , but things *have changed a bit* now, and your answer is still a top result in a Google search; Can you please update your answer? For reference you can see https://stackoverflow.com/a/41913654/1621391 – WhiZTiM May 03 '20 at 19:38
  • @WhiZTiM Thanks for the comment. I added a link to your answer in a note. – Sergey Kalinichenko May 04 '20 at 02:09