Can Standard Container Templates Be Instantiated With 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.

What are the rules for standard library containers and incomplete types?

std::deque<S> *p;   // seems to be UB like the previous case, 
                   // but is it ok if p is not used till S is defined?

That's actually the interesting bit here. Yes, instantiating that container with an incomplete type is not allowed, there is no provision for it. But the question becomes whether or not it's really instantiated. It doesn't have to be, according to the core language.

[temp.inst]

1 Unless a class template specialization has been explicitly
instantiated or explicitly specialized, the class template
specialization is implicitly instantiated when the specialization is
referenced in a context that requires a completely-defined object type
or when the completeness of the class type affects the semantics of
the program.

A pointer to a type doesn't require the type to be complete. So this declaration alone is not normally enough to cause an instantiation of a class template, and so it may be premature to determine the requirement of the container is violated here.

Unless of course we take "the completeness of the class type affects the semantics of the program" to include contract violations in the standard library. An implementation could instantiate here, I suppose. I'm not aware of any implementation that does however, so this may not be the desires interpretation.

So to err on to side of caution, I'd deem this UB too.

---

std::deque<S*> p;  // not really sure about this one

This is fine. Whether or not S is complete, S* is still a complete object type. I say this because it's not included at

[basic.types]

5 A class that has been declared but not defined, an enumeration
type in certain contexts ([dcl.enum]), or an array of unknown bound or
of incomplete element type, is an incompletely-defined object type.
Incompletely-defined object types and cv void are incomplete types
([basic.fundamental]). Objects shall not be defined to have an
incomplete type.

The constraints about the completeness of S only appear when attempting to use such a pointer in an expressions that does a dereference or pointer arithmetic. But the pointer type itself is still complete. So it's a valid template argument for a container type.

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

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

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:

1. clear is a member function of Window_mgr;
2. Window_mgr::clear() is a friend of Screen;
3. 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.

Instantiation of a list with an incomplete type in a typedef

If you want guaranteed support for incomplete types, your best bet is to create unique_ptr's to them:

typedef std::list<std::unique_ptr<NodeEntry>> NodeList;
typedef std::list<std::unique_ptr<EdgeEntry>> EdgeList;

In the past, many times std::list<incomplete_type> would just work. However with C++11 and noexcept specifications, it is becoming more likely that a complete type is needed, just so that the noexcept spec can be validated.

C++11 guarantees that unique_ptr<incomplete_type> and shared_ptr<incomplete_type> will work, although there are strict limits. For example wherever ~unique_ptr() is executed, the type has to be complete there. But you can usually outline such code to a source and #include the complete type at that point.

unique_ptr<incomplete_type> and shared_ptr<incomplete_type> are the only class templates in the C++11 std::lib that are guaranteed to work with incomplete types. Everything else is undefined behavior:

[res.on.functions]/p2/b5:

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.

If for some reason the std::list does not need to own the pointer to the incomplete type, then std::list<NodeEntry*> would work even better. You might also want to entertain using vector instead of list since the cost of moving pointers (or even unique_ptr's) around is relatively small.

---

Related Topics