recursive type template

[n.torrey.pines]

I have the following tree definition:

template<typename T>
struct tree {
T first;
vector<tree<T> > second; // branches
};

which compiles successfully. What I'd like to do though is to use
another template like 'pair', because I might have a bunch of useful
methods already defined in 'pair':

template<typename T>
struct tree : public pair<T, tree<T> > {};

This doesn't compile. I tried some forward declarations with no
success. Is there any way to do it?

 

[Kai-Uwe Bux]

I have the following tree definition:

template<typename T>
struct tree {
T first;
vector<tree<T> > second; // branches
};

which compiles successfully.

Maybe, but the program has undefined behavior: standard templates may only
be instantiated with complete types. It may not show in the implementation
of std::vector in your library, but it might fail in others. The reason
that it is not guaranteed to fail is that the straight forward
implementation of std::vector only uses T* internally. Thus, you have to
put in an extra check to detect incomplete types. Some implementations of
std::vector do that.

What I'd like to do though is to use
another template like 'pair', because I might have a bunch of useful
methods already defined in 'pair':

template<typename T>
struct tree : public pair<T, tree<T> > {};

This doesn't compile. I tried some forward declarations with no
success. Is there any way to do it?

Not really. You could do:

#include <utility>

template < typename T >
struct tree : public std:air< T, tree<T>* > {};

int main () {

tree<int> a;

}


Best

Kai-Uwe Bux

 

[David W]

I have the following tree definition:

template<typename T>
struct tree {
T first;
vector<tree<T> > second; // branches
};

which compiles successfully. What I'd like to do though is to use
another template like 'pair', because I might have a bunch of useful
methods already defined in 'pair':

template<typename T>
struct tree : public pair<T, tree<T> > {};

This doesn't compile. I tried some forward declarations with no
success. Is there any way to do it?

If your 'pair' is really std:air, and that pair has an instance of each type passed to it as a
member (I assume it does), then you've effectively got struct tree having itself as a member, which
is impossible (since that member has another instance of itself as a member, ad infinitum), and in
its base class to boot, which is even more impossible (???). This problem isn't anything to do with
templates.

Uh, are you sure that 'tree' is a kind of 'pair'?

DW

 

[amparikh]

I have the following tree definition:

template<typename T>
struct tree {
T first;
vector<tree<T> > second; // branches
};

which compiles successfully. What I'd like to do though is to use
another template like 'pair', because I might have a bunch of useful
methods already defined in 'pair':

template<typename T>
struct tree : public pair<T, tree<T> > {};

tree<T> template class is not completely defined at the point at which
is being referred as the base class.

Not sure what you are trying to do, but try using CRTP.
Have some of the functionality you need in the base and then pass the
Derived as the templare parameter to the Base, to use it in the
std:air that you define in the Base.

 

[shuisheng]

I have the following tree definition:

template<typename T>
struct tree {
T first;
vector<tree<T> > second; // branches
};

which compiles successfully.

This is because the vector contains the data pointers rather than the
data itself. So you can construct a instance of the tree class in the
memory since you know its size.

What I'd like to do though is to use
another template like 'pair', because I might have a bunch of useful
methods already defined in 'pair':

template<typename T>
struct tree : public pair<T, tree<T> > {};

This doesn't compile. I tried some forward declarations with no
success. Is there any way to do it?

But here the compiler don't know the size of the class because the tree
in pair<T, tree<T> > is not define well when it is used to construct
the derived tree. So the compiler give an error.

Try this:

template<typename T>
struct tree : public pair<T, tree<T>* > {};

Bests,

Shuisheng

 

[Gernot Frisch]

I have the following tree definition:

template<typename T>
struct tree {
T first;
vector<tree<T> > second; // branches
};

maybe this way:

template<typename T> struct tree
{
T first;
std::vector<tree<T> > subtrees;
};


int main()
{
tree<pair<int, std::string> > mytree;

}

 

[Kai-Uwe Bux]

maybe this way:

template<typename T> struct tree
{
T first;
std::vector<tree<T> > subtrees;
};

That is UB according to [17.4.3.6/2] item 5:

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.

int main()
{
tree<pair<int, std::string> > mytree;

}

Best

Kai-Uwe Bux

 

[Gernot Frisch]

That is UB according to [17.4.3.6/2] item 5:

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.

and if I substitute "typename" by "class"?

 

[shuisheng]

I have the following tree definition:

template<typename T>
struct tree {
T first;
vector<tree<T> > second; // branches
};

which compiles successfully. What I'd like to do though is to use
another template like 'pair', because I might have a bunch of useful
methods already defined in 'pair':

template<typename T>
struct tree : public pair<T, tree<T> > {};

This doesn't compile. I tried some forward declarations with no
success. Is there any way to do it?

template<typename T>
struct tree : public pair<T, tree<T>* > {};

make the second part of pair to be a pointer.t

 

[Kai-Uwe Bux]

That is UB according to [17.4.3.6/2] item 5:

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.

and if I substitute "typename" by "class"?

The word "typename" does not occur anywhere in what you quoted. So, what
exactly do you mean?


Best

Kai-Uwe Bux

 

[n.torrey.pines]

If your 'pair' is really std:air, and that pair has an instance of each type passed to it as a
member (I assume it does), then you've effectively got struct tree having itself as a member, which
is impossible (since that member has another instance of itself as a member, ad infinitum), and in
its base class to boot, which is even more impossible (???). This problem isn't anything to do with
templates.

Uh, are you sure that 'tree' is a kind of 'pair'?

A tree of T is a pair of T and a vector of trees of T. I doesn't have
self as a member - it has a vector of selves as a member.

My pair is like std:air for the purposes of this discussion, but it
has some useful to me (and the tree) methods defined for it that I
would like to reuse.

 

[n.torrey.pines]

It's weird, but both versions compile now (maybe the sysadmin updated
g++, but more likely, I did something different last time)

#include <vector>
#include <utility>

template<typename T>
struct tree : public std:air<T, std::vector< tree<T> > > {};

int main() {
tree<int> t1; t1.first = 0;
tree<int> t2(t1); t1.second.push_back(t2);
}


This compiles with g++ -pedantic -ansi. Those who say that the behavior
is undefined, as far as the standard is concerned, can you point me to
a specific point in the standard that says it?

 

[Kai-Uwe Bux]

It's weird, but both versions compile now (maybe the sysadmin updated
g++, but more likely, I did something different last time)

#include <vector>
#include <utility>

template<typename T>
struct tree : public std:air<T, std::vector< tree<T> > > {};

int main() {
tree<int> t1; t1.first = 0;
tree<int> t2(t1); t1.second.push_back(t2);
}


This compiles with g++ -pedantic -ansi. Those who say that the behavior
is undefined, as far as the standard is concerned, can you point me to
a specific point in the standard that says it?

Sure:

[17.4.3.6/1 and 2]

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.

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.


Best

Kai-Uwe Bux

ps.: please don't top post. It's frowned upon in this group.

 

[Gernot Frisch]

The word "typename" does not occur anywhere in what you quoted. So,
what
exactly do you mean?

My post was:
template<typename T> struct tree
....

But, you're perfectly right:

template <class T> tree
{
std::vector<T> subtrees;
};

does not compile. Sorry for my stupidity. I apologize.

 

[werasm]

Sure:

[17.4.3.6/1 and 2]

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.

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.

Interesting. This contradicts 14.3.2 's note which says that a template
type argument can be and incomplete type - hence CRTP.

The problem, amongst others is that if Derived derives from Base, its
size is determined by Base. OTOH, if Base depends on derived to such an
extent that its size is determined by derived, then a catch 22 exists.
So it boils down to how std::vector is implemented, which means UB,
yes. A little example:

template <class T>
struct Base
{
int size(){ return sizeof(T); }
//T t_; (1)
};
template <class T>
class Derived : public Base<Derived<T> >
{
};

int main()
{
Derived<int> d;
d.size();
}

....compiles but when I uncomment (1), this does not compile because T
is an incomplete type, and therefore not instantiabable. The code he
submitted compiles under Comeau, but is dependent on whether that STL
vector implementation requires complete types or not.

Regards,

Werner

 

[Kai-Uwe Bux]

Sure:

[17.4.3.6/1 and 2]

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.

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.

Interesting. This contradicts 14.3.2 's note which says that a template
type argument can be and incomplete type - hence CRTP.

There is no contradiction: 17.4.3.6 specifies requirements for the use of
components from the standard library. It does not talk about templates in
general.

The problem, amongst others is that if Derived derives from Base, its
size is determined by Base. OTOH, if Base depends on derived to such an
extent that its size is determined by derived, then a catch 22 exists.
So it boils down to how std::vector is implemented, which means UB,
yes. A little example:

template <class T>
struct Base
{
int size(){ return sizeof(T); }
//T t_; (1)
};
template <class T>
class Derived : public Base<Derived<T> >
{
};

int main()
{
Derived<int> d;
d.size();
}

...compiles but when I uncomment (1), this does not compile because T
is an incomplete type, and therefore not instantiabable. The code he
submitted compiles under Comeau, but is dependent on whether that STL
vector implementation requires complete types or not.

Right. And 17.4.3.6 gives license to the implementations of the standard
library (e.g., implementations of std::vector) to use code that requires
template parameters to be complete types.

E.g., the obvious implementation for std:air<First,Second> will require
that First and Second are complete types:

template < typename First, typename Second >
struct pair {
First first;
Second second;
...
};

whereas the obvious implementation of std::vector will not. This explains
the observations of the OP.


Best

Kai-Uwe Bux

 

[werasm]

There is no contradiction: 17.4.3.6 specifies requirements for the use of
components from the standard library. It does not talk about templates in
general.

Ok, I'll put it this way:

The requirement that the standard library imposes on template arguments
differ from (or oppose) the requirements that are imposed on template
arguments by the standard itself (I call this contradictory - I could
for instance read the standard partially, and believe that my code is
valid). Admittedly, the fact that this is the case is not wrong, but
stems from the fact that the standard don't want to restrict its
implementors (I guess).

No big deal, though - I'm not criticizing the standard. I'm just saying
this could cause ambiguity, and is to an extent (when looking
subjectively, as we so often do), contradictory.

,

Werner

 

[n.torrey.pines]

Sure:

[17.4.3.6/1 and 2]

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.

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.

Interesting. This contradicts 14.3.2 's note which says that a template
type argument can be and incomplete type - hence CRTP.

The problem, amongst others is that if Derived derives from Base, its
size is determined by Base. OTOH, if Base depends on derived to such an
extent that its size is determined by derived, then a catch 22 exists.
So it boils down to how std::vector is implemented, which means UB,
yes. A little example:

template <class T>
struct Base
{
int size(){ return sizeof(T); }
//T t_; (1)
};
template <class T>
class Derived : public Base<Derived<T> >
{
};

int main()
{
Derived<int> d;
d.size();
}

...compiles but when I uncomment (1), this does not compile because T
is an incomplete type, and therefore not instantiabable. The code he
submitted compiles under Comeau, but is dependent on whether that STL
vector implementation requires complete types or not.

Regards,

Werner

So if you treat STL as an external library, for example if you are using
STLport, you can write it off as an external library dependence, as
opposed to a non-standard use of the language?

For the record, I tested the following in GCC 3.4 (-pedantic -ansi),
Intel 9.1 (-strict-ansi) and MSVC++ (some 0.5 y.o. version). None of
them complained:

template<typename T>
struct tree : public std:air<T, std::vector< tree<T> > > {};

 

[Kai-Uwe Bux]

Sure:

[17.4.3.6/1 and 2]

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.

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.

Interesting. This contradicts 14.3.2 's note which says that a template
type argument can be and incomplete type - hence CRTP.

The problem, amongst others is that if Derived derives from Base, its
size is determined by Base. OTOH, if Base depends on derived to such an
extent that its size is determined by derived, then a catch 22 exists.
So it boils down to how std::vector is implemented, which means UB,
yes. A little example:

template <class T>
struct Base
{
int size(){ return sizeof(T); }
//T t_; (1)
};
template <class T>
class Derived : public Base<Derived<T> >
{
};

int main()
{
Derived<int> d;
d.size();
}

...compiles but when I uncomment (1), this does not compile because T
is an incomplete type, and therefore not instantiabable. The code he
submitted compiles under Comeau, but is dependent on whether that STL
vector implementation requires complete types or not.

Regards,

Werner

So if you treat STL as an external library, for example if you are using
STLport, you can write it off as an external library dependence, as
opposed to a non-standard use of the language?

I am not sure I understand what you mean. However, this is like many other
issues where the standard says that you get undefined behavior: if you know
what the undefined behavior is that your implementation gets you, then you
are of course perfectly free to make use of that.

For the record, I tested the following in GCC 3.4 (-pedantic -ansi),
Intel 9.1 (-strict-ansi) and MSVC++ (some 0.5 y.o. version). None of
them complained:

template<typename T>
struct tree : public std:air<T, std::vector< tree<T> > > {};

In principle, a totally whacky implementation could compile the code but do
surprising things at runtime. As a practical matter, though, this is
nothing to worry about: no library implementor will do that.

As a matter of fact, the natural implementation of std::vector will be
perfectly happy with incomplete types. One would need to put an extra
concept check in on purpose (e.g., to help programmers find UB in their
programs; I would love to have that at least as a debugging tool). This is
easy in this case -- one could just add a typedef:

template < typename T >
class vector {

// stop compilation for incomplete template parameters:
typedef char dummy [sizeof(T)];

...

};

I do not know if any widespread library has that. Your tests indicate the
contrary.



Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Sure:

[17.4.3.6/1 and 2]

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.

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.

Interesting. This contradicts 14.3.2 's note which says that a template
type argument can be and incomplete type - hence CRTP.

The problem, amongst others is that if Derived derives from Base, its
size is determined by Base. OTOH, if Base depends on derived to such an
extent that its size is determined by derived, then a catch 22 exists.
So it boils down to how std::vector is implemented, which means UB,
yes. A little example:

template <class T>
struct Base
{
int size(){ return sizeof(T); }
//T t_; (1)
};
template <class T>
class Derived : public Base<Derived<T> >
{
};

int main()
{
Derived<int> d;
d.size();
}

...compiles but when I uncomment (1), this does not compile because T
is an incomplete type, and therefore not instantiabable. The code he
submitted compiles under Comeau, but is dependent on whether that STL
vector implementation requires complete types or not.

Regards,

Werner

So if you treat STL as an external library, for example if you are using
STLport, you can write it off as an external library dependence, as
opposed to a non-standard use of the language?

For the record, I tested the following in GCC 3.4 (-pedantic -ansi),
Intel 9.1 (-strict-ansi) and MSVC++ (some 0.5 y.o. version). None of
them complained:

template<typename T>
struct tree : public std:air<T, std::vector< tree<T> > > {};

Just for the record -- the following fails in g++-4.1.1 when concept checks
have been enabled:

#include <utility>
#include <vector>

template<typename T>
struct tree : public std:air<T, std::vector< tree<T> > > {};

int main ( void ) {
tree< int > a;
}


Best

Kai-Uwe Bux