How Can an Incomplete Type Be Used as a Template Parameter to Vector Here

How can an incomplete type be used as a template parameter to vector here?

I think in practice this may work but from what I can tell this looks like undefined behavior. From the draft C++11 standard 17.6.4.8 [res.on.functions]:

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.

Although instantiating a template component does not seem like a well-defined term.

I came to this via LWG defect 611 which added:

unless specifically allowed for the component.

to the end of the bullet above so it now reads:

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

as an exception for shared_ptr since the above quote conflicted with this quote from 20.6.6.2 [util.smartptr.shared]:

The template parameter T of shared_ptr may be an incomplete type.

Also see N4371: Minimal incomplete type support for standard containers, revision 2.

Incomplete type as tag type for templates

Yes, you can use an incomplete type as a template type argument - provided that you never use that type argument in a context that requires a complete type. This is handy for when you want a template argument to distinguish two different class templates - but don't actually need it for anything else.

Since B never tries to do anything with T that requires it to be complete, all three instantiations of it (C1, C2, and C3) are perfectly valid.

Reference or pointer to std::vector of incomplete type

The declaration is correct, so long as you don't call f2.

The compiler doesn't need to know the internal of Result class if you don't call f2. There's no storage allocation in the declaration.

If some compilation unit call f2, you need to supply the complete type for Result class, or you need another reference parameter to call f2:

void another_f(SomeAlgoInterface& i, std::vector<Result>& results)
{
    i.f2(results);  
}

Incomplete type is not allowed in a class, but is allowed in a class template

The real answer might be ¯\_(ツ)_/¯, but it's probably currently okay because templates are magical, but it may be more explicitly not okay pending some other core issue resolutions.

First, the main problem of course is [class.mem]/14:

Non-static data members shall not have incomplete types.

This is why your non-template example is ill-formed. However, according to [temp.point]/4:

For a class template specialization, a class member template specialization, or a specialization for a class member of a class template, if the specialization is implicitly instantiated because it is referenced from within another template specialization, if the context from which the specialization is referenced depends on a template parameter, and if the specialization is not instantiated previous to the instantiation of the enclosing template, the point of instantiation is immediately before the point of instantiation of the enclosing template. Otherwise, the point of instantiation for such a specialization immediately precedes the namespace scope declaration or definition that refers to the specialization.

Which suggests that foo_impl<void>::bar is instantiated before foo_impl<void>, and hence it's complete at the point where the non-static data member of type bar is instantiated. So maybe it's okay.

However, core language issues 1626 and 2335 deal with not-exactly-the-same-but-still-quite-similar issues regarding completeness and templates, and both point to desiring to make the template case more consistent with the non-template case.

What does all of this mean when viewed as a whole? I'm not sure.

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).

Is instantiating a class template with an incomplete type ill-formed, if the type is defined afterwards?

Assuming we only have one translation unit, [temp.point] rules out your quote as a possible source of ill-formedness

A specialization for a class template has at most one point of instantiation within a translation unit.

Instead, the problem with the first snippet is [temp.expl.spec]

If a template, a member template or a member of a class template is explicitly specialized then that specialization shall be declared before the first use of that specialization that would cause an implicit instantiation to take place, in every translation unit in which such a use occurs; no diagnostic is required.

The second snippet is well-formed, there is no requirement that template parameters need to have complete type.

The third snippet is ill-formed, new T requires that T be a complete type. A slight catch here is that the definition of the constructor is implicitly instantiated at Foo<A> foo;. If however, the snippet is changed to

struct A;

template <typename T>
struct Foo {
    Foo() {
        new T;
    }
};

using FooA = Foo<A>;

struct A {};

Then the definition of the constructor isn't instantiated and will therefore be well-formed. [temp.inst]

The implicit instantiation of a class template specialization causes
the implicit instantiation of the declarations, but not of the definitions, of the non-deleted class member functions, member classes, scoped member enumerations, static data members, member templates, and friends; and [...]

The fourth snippet is ill-formed because members need to have complete type. [class.mem]

The type of a non-static data member shall not be an incomplete type [...]

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]).

How Can an Incomplete Type Be Used as a Template Parameter to Vector Here