May I instantiate a templated object A<B> containing a deque of objects of type A<B>?

Question

I would like to understand if the following code is correct in general, or not:

#include <deque>

template<class T>
struct Node {
    std::deque<Node<T> > branches;
    T data;

    Node(const T& _data) : data(_data) {
    }

};

void dummy() {
    Node<float> test(5.0f);
}

This code was compiled with several toolchains without ever generating errors (See here for example). The problem is that now I get an instantiation error (maybe related to the fact that I am using llvm libc++, not sure about the version).

<...>llvm-libc++/include/deque:912:55: error: invalid application of 'sizeof' to incomplete type 'std::__1::__deque_base<Node<float>, std::__    1::allocator<Node<float> > >::value_type {aka Node<float>}'
     static const difference_type __block_size = sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16;

In case this code is correct, I am not interested to investigate the origin of the bug (compiler or std library implementation) or to have a workaround: again, I mainly would like to understand if the code above is formally correct.

Answer 1

The code is ill-formed. At this point:

template<class T>
struct Node {
    std::deque<Node<T> > branches; // <==

Node<T> is still an incomplete type. There are currently built-in exceptions for incomplete types for three of the containers:

• "An incomplete type T may be used when instantiating forward_list if the allocator satisfies the allocator completeness requirements 17.6.3.5.1. T shall be complete before any member of the resulting specialization of forward_list is referenced." [forwardlist.overview]/4
• "An incomplete type T may be used when instantiating list if the allocator satisfies the allocator completeness requirements 17.6.3.5.1. T shall be complete before any member of the resulting specialization of list is referenced." [list.overview]/3
• "An incomplete type T may be used when instantiating vector if the allocator satisfies the allocator completeness requirements 17.6.3.5.1. T shall be complete before any member of the resulting specialization of vector is referenced." [vector.overview]/3

There is no such wording for deque, which currently requires a complete type. Seems inconsistent to me to allow incomplete types for vector but not deque, but that's the way it is.

Answer 2

It's not a bug in your compiler nor the standard library. The program is ill formed. You may not instantiate std::deque with an incomplete value type.