Re: using vector to encapulate a tree - non const copy constructors
terry wrote:
One of the constraints on the first parameter of std::vector
(and in fact, on all type parameters of all templates in the
standard library, at present) is that it be a complete type at
the point of instantiation.
I think this is at the heart of the matter. From what has
been said, the standard does not say at the time of definition
or time of declaration.
It says "when instantiating a template component". Definition
or declaration. In fact, in your case, you need a definition;
the incomplete type resulting from a declaration cannot be used
as a base class.
I suggest that whether this type is complete at instantiation
is a more tricky question, and that this type of
declaration/definition provides a good example of the
distinction. (although I accept completely that I might get
it wrong as well.)
Are you sure that, for most implementations, at the time
instantiation using the default constructor for
vector<mytree>, mytree is not a complete type.
The constructor has nothing to do with it. To instantiate the
class std::vector<T>, T must be a complete type---std::vector
is a template component of the library, and the quoted text
applies. According to ?14.7.1: "Unless a class template
specialization has been explicitly instantiated (14.7.2) or
explicitly specialized (14.7.3), 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." To be used as
a base class, a class must be completely-defined.
I find it hard to believe any compiler would know how to
instantiate an incomplete type. Is there a simple example?
template< typename > class Toto ;
// ...
Toto< int >* pToto ;
Even if the complete definition of Toto were present, a
completely defined type is not needed here, so the compiler will
not instantiate it.
As I see it, the standard makes it clear that a type can be
incomplete at one point in a compilation unit and complete
later. Self referential declarations are certainly legal and
can define complete types after the event.
Certainly. And it is doubtlessly possible to implement
std::vector in a way that the complete type is not required to
instantiate the class template. The standard, however, doesn't
require this of the implementation; an implementation is also
free to implement the template in a way that requires the
complete definition.
By instantiating the template on an incomplete type, you have
violated your end of the contract, and the compiler/library are
no longer required to keep their end. (In practice, of course,
either the code will compile and work, or it won't compile. I
don't think you really have to fear all of the other potential
undefined behaviors.)
The result depends on the template design:
The result depends first and foremost on the contract which
constrains the template design.
template class <S> mytemplate
{
S* address;
}
class T : public: mytemplate<T>{};
//T is complete here.
but
template class <S> mytemplate2
{
S value;
}
class T2 : public: mytemplate<T2>{};
//Error T2 very incomplete!!
Right.
What the standard effectively says is that an implementation of
std::vector is free to use either of these.
I suspect that for most implimentations of the template
std::vector, the compiler would have mytree available as a
complete type at instantiation time just like T. In this case,
vector<mytree> would be well defined and accord to the
standard (of course one might want new constructors etc. but
that is another story).
As the examples for T and T2 above show, one should expect
that this would be implimentation dependent and one can
certainly construct implimentations of vector that made mytree
self referential and incomplet (typically because vector<T>
is declared with a T object in it like T2 above).
The standard makes some very careful distinctions.
Implementation dependant means that the implementation must
explictly make a choice, and document it. In this case, the
standard says undefined behavior---the implementation isn't
required to formally make any choice, nor document it. (An
implementation is, of course, free to define any undefined
behavior it wishes, any way it wants. Off hand, I don't know of
any implementation which does define this particular case, but
if the documentation of your implementation does guarantee it,
you can use it. In non-portable code.)
At the risk of being a bit controversial and overstepping my
expertise, I feel that there could be a case for recommending
that the standard requires that for all stl container
implimentations, the definition
class T: std::container< T >{};
// T complete here
is always true.
It is clear that in this case, the standard made a simple,
global statement, rather than evaluate each individual case, and
that more guarantees could be given. The next version of the
standard, for example, will explicitly allow the instantiation
of shared_ptr, and maybe some other classes, without a complete
definition being present.
I'm not sure, however, that anyone feels motivated to extend
this sort of guarantee to the containers. Conceptually, a
container contains objects of the instantiation type; an
std::vector<T> is conceptually pretty much the same thing as a
T[]. And a T[] does require a complete type. IMHO, there is no
real motivation for not requiring a complete type.
Note too that you won't get very far talking about inheritance.
It is generally acknowledged that you should not inherit from a
standard container. The same problem is present, however, if
you want to use it as a member:
struct T { std::vector<T > children ; } ;
is not a legal definition. But even here: conceptually, a class
cannot contain instances of itself, and conceptually,
std::vector contains instances of the instantiation type. If
you want simply to navigate, the normal C++ solution is to use
pointers.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]