Why C++ Containers Don't Allow Incomplete Types

Can standard container templates be instantiated with incomplete types?

Personally, I feel the wording instantiating in 17.6.4.8/2 is a little
ambiguous, but according to
this article,
the standard's intent seems not to allow recursive data type using
standard containers.

On a related note, VC2005 issues an error for
class C { std::deque< C > x; };, while it compiles
class C { std::vector< C > x; };...

However, in my understanding, this restriction is just for expanding the
freedom of the implementation of standard containers.
So as Kerrek SB mentioned, there can be containers which allow
recursive data structure, and
Boost.Container
seems to provide this facility.

Can I manage incomplete class objects using STL containers?

Incomplete types are currently not supported by standard containers; cf. Can standard container templates be instantiated with incomplete types? - that said, implementations can choose to support incomplete types as an extension, but that makes your code non-portable.

The paper n4371 Minimal incomplete type support for standard containers, revision 2 has been incorporated into the most recent draft (n4527) of the C++ Standard, so barring the unexpected it is very likely that incomplete types will be supported for vector, list and forward_list in C++17.

There is one way to satisfy the requirements in "C++ Primer" without depending on implementation extension or C++17:

clear is a member function of Window_mgr;
Window_mgr::clear() is a friend of Screen;
Window_mgr is contains a vector of Screens:

You could make Screen a nested class of Window_mgr:

class Window_mgr{
public:
    typedef std::size_t screenindex;
    void clear(screenindex);

    class Screen{
        friend void Window_mgr::clear(screenindex);
    public:
        // ...
    };

// ...
private:
    vector<Screen> screens;
};

Even here I've had to adjust the definition of type screenindex to break the dependency cycle.

Is iterator to a container with incomplete data type legal?

Unless explicitly stated in the standard that incomplete types are legal, they are not legal. The specific section is 17.6.4.8 [res.on.functions] paragraph 2:

In particular, the effects are undefined in the following cases:
[...]
if an incomplete type (3.9) is used as a template argument when instantiating a template component, unless specifically allowed for that component.

I don't think any of containers is required to support incomplete types. Some of the smart pointers do allow incomplete types. Off-hand I can't think of anything else which would allow incomplete types. A quick search for "incomplete" yields the following components allowing incomplete types as template arguments:

std::declval<T>()
std::unique_ptr<T>
std::default_delete<T>
std::shared_ptr<T>
std::weak_ptr<T>
std::enable_shared_from_this<T>

In the code example, std::map<int, A>::iterator instantiates a template with an incomplete type. As a result the code results in undefined behavior.

Why do C++ templates let me circumvent incomplete types (forward declarations)?

The first requires a definition of container since you are doing a copy operation. If you define the constructor of iter after container's definition you'd be okay. So:

struct container;
struct iter {
  container &c;
  int *p;
  iter(container &c);
};

struct container {
  int x;
  int &value() { return x; }
  iter begin() { return iter(*this); }
};

iter::iter(container &c) : c(c), p(&c.value()) {}

int main() {
  container c;
  c.begin();
  return 0;
}

The second example works because there is no class until you actually instantiate one in your main function. By that time all types are defined. Try moving any of the iter or container templates definition after main and you'll hit an error.

The third example is a specialization for int or so it appears. This should compile because the template parameter for iter is not used. You've got the specialization syntax a bit off. However, there is no proper constructor so you'll only get garbage for x. Moreover, iterators are modeled well by pointers. Passing this's value will not be of much help. Iterators are typically required for a sequence and not an individual object. Though, there is nothing that can stop you from building one.

And you don't need a ; after a function body.

Trick to allow incomplete types in templates?

It's undefined behavior. The standard requires a type to be
complete if it is used as the argument of a template, at the
point where the template is instantiated. And
my_incomplete_vector::Element is not complete when you use it
inside Element. No problems will occur until you actually
instantiate your template, of course, but g++ fails to compile
your code with the usual debugging options
(-D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC).

How do I fix my STL style container to hold incomplete or abstract types?

Since the type is incomplete the compiler has no way of determinng it's size. Since the size is needed to store the objects by value the compiler whines about it. If you must deal with incomplete types you will need to use a container of pointers. For instance in Test you can use std::vector<std::unique_ptr<IncompleteType>> or std::vector<IncompleteType*>.

There is another issue in your code. tree and vector fail with AbstractClass because you are trying to store it by value. Since it has pure virtual functions it cannot be instantiated when the Node is created.

Does the using declaration allow for incomplete types in all cases?

Since you've not included language-lawyer, I'm attempting a non-lawyer answer.

Why should that be UB?

With a using delcaration, you're just providing a synonym for std::variant<whatever>. That doesn't require an instantiation of the object, nor of the class std::variant, pretty much like a function declaration with a parameter of that class doesn't require it:

void f(val); // just fine

The problem would occur as soon as you give to that function a definition (if val is still incomplete because box is still incomplete):

void f(val) {}

But it's enough just to change val to val& for allowing a definition,

void f(val&) {}

because the compiler doesn't need to know anything else of val than its name.

Furthermore, and here I'm really inventing, "incomplete type" means that some definition is lacking at the point it's needed, so I expect you should discover such an issue at compile/link time, and not by being hit by UB. As in, how can the compiler and linker even finish their job succesfully if a definition to do something wasn't found?

Why does std::vector work with incomplete types in class definitions?

Standard says (draft N3690; this is post C++11, pre C++14):

[res.on.functions]

1 In certain cases (replacement functions, handler functions,
operations on types used to instantiate standard library template
components), the C++standard library depends on components supplied by
a C++program. If these components do not meet their requirements,
the Standard places no requirements on the implementation.

2 In particular, the effects are undefined in the following cases:

— if an incomplete type (3.9) is used as a template argument when
instantiating a template component, unless specifically allowed for
that component.

Given that standard places no requirements, and effects are undefined (as far as I can tell, this is same as undefined behaviour), there is no expectation for the instantiation to "not work" any more than there is expectation for it to (appear to) "work".

Since C++17, the requirement was relaxed and std::vector does not require the value type to be complete, if used with appropriate allocator (the default allocator is appropriate). (This freedom does not extend to using all member functions; they have additional requirements).

Standard quote (current draft):

[vector.overview]

An incomplete type T may be used when instantiating vector if the allocator meets the allocator completeness requirements.
T shall be complete before any member of the resulting specialization of vector is referenced.

[allocator.requirements.completeness]

If X is an allocator class for type T, X additionally meets the allocator completeness requirements if, whether or not T is a complete type:

X is a complete type, and

all the member types of allocator_traits other than value_type are complete types.

[default.allocator]

All specializations of the default allocator meet the allocator completeness requirements ([allocator.requirements.completeness]).