Asking for trouble with incomplete types?

Hi,

I am trying to reduce the complexity of a set of classes I made a couple of
years ago, what equates to a set of trees, for which I want to use std::list
and avoid having to use direct pointers anywhere.

I wish to have a class contain a list of itself, as so:

class B;
class A
{
public:
std::list<B> List;
typedef std::list<B>::iterator iterator;
iterator begin() { return List.begin(); }
};

class B
{
public:
A m_a;
};

My question is, provided I ensure there is no in class A referencing direct
instances of B, can I be fairly certain im not launching into a world of c++
driven pain, for example no:

class A
{
...
B GetSomething();
};

I expect that as long as thing that call items such as copy constructors
or -> / * operators of list<B>::iterator are in cpp files there should be no
issue.

Could anyone tell me different?

Regards,

--
- Mark Randall
http://www.temporal-solutions.co.uk
http://www.awportals.com

Igor
Wed Feb 21 15:38:08 CST 2007

Mark Randall <markyr@gEEEEEmail.com> wrote:
> I wish to have a class contain a list of itself

You can't, in general. You might get away with it with some containers
on some STL implementations, but it's non-portable. From C++ standard:

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

(meaning a template component that's part of standard C++ library, not
any odd template you might have written yourself - I.T.)

Basically, it's allowed for sizeof(list<T>) to depend on sizeof(T)

> class B;
> class A
> {
> public:
> std::list<B> List;
> typedef std::list<B>::iterator iterator;
> iterator begin() { return List.begin(); }
> };
>
> class B
> {
> public:
> A m_a;
> };

B contains an instance of A, which contains an instance of list<B>,
which may, on some STL implementations, contain an instance of B. So B
may indirectly contain an instance of itself. Which is, of course,
impossible.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

Mark
Wed Feb 21 15:52:05 CST 2007

"Igor Tandetnik" <itandetnik@mvps.org> wrote in message
news:uNv8UCgVHHA.4964@TK2MSFTNGP06.phx.gbl...
> Mark Randall <markyr@gEEEEEmail.com> wrote:
>> I wish to have a class contain a list of itself
>
> You can't, in general. You might get away with it with some containers on
> some STL implementations, but it's non-portable. From C++ standard:
>
> 17.4.3.6/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.
>
> (meaning a template component that's part of standard C++ library, not any
> odd template you might have written yourself - I.T.)

> B contains an instance of A, which contains an instance of list<B>, which
> may, on some STL implementations, contain an instance of B. So B may
> indirectly contain an instance of itself. Which is, of course, impossible.

I don't need to worry about portability, its written in MFC.

My understanding is that std::list in the MS library will never have any
need store an instance as a member (by defenition of it being a linked
list), and it is not an actual incomplete type at the time it is
instantiated.

--
- Mark Randall
http://www.temporal-solutions.co.uk
http://www.awportals.com

Ben
Wed Feb 21 17:05:12 CST 2007


"Igor Tandetnik" <itandetnik@mvps.org> wrote in message
news:uNv8UCgVHHA.4964@TK2MSFTNGP06.phx.gbl...
> Mark Randall <markyr@gEEEEEmail.com> wrote:
>> I wish to have a class contain a list of itself
>
> You can't, in general. You might get away with it with some containers on
> some STL implementations, but it's non-portable. From C++ standard:
>
> 17.4.3.6/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.

Couldn't Curiously Recurring Template Pattern be used to overcome this?

>
> (meaning a template component that's part of standard C++ library, not any
> odd template you might have written yourself - I.T.)
>
> Basically, it's allowed for sizeof(list<T>) to depend on sizeof(T)
>
>> class B;
>> class A
>> {
>> public:
>> std::list<B> List;
>> typedef std::list<B>::iterator iterator;
>> iterator begin() { return List.begin(); }
>> };
>>
>> class B
>> {
>> public:
>> A m_a;
>> };
>
> B contains an instance of A, which contains an instance of list<B>, which
> may, on some STL implementations, contain an instance of B. So B may
> indirectly contain an instance of itself. Which is, of course, impossible.
> --
> With best wishes,
> Igor Tandetnik
>
> With sufficient thrust, pigs fly just fine. However, this is not
> necessarily a good idea. It is hard to be sure where they are going to
> land, and it could be dangerous sitting under them as they fly
> overhead. -- RFC 1925
>
>

Igor
Wed Feb 21 17:49:08 CST 2007

Ben Voigt <rbv@nospam.nospam> wrote:
> "Igor Tandetnik" <itandetnik@mvps.org> wrote in message
> news:uNv8UCgVHHA.4964@TK2MSFTNGP06.phx.gbl...
>> Mark Randall <markyr@gEEEEEmail.com> wrote:
>>> I wish to have a class contain a list of itself
>>
>> You can't, in general. You might get away with it with some
>> containers on some STL implementations, but it's non-portable. From
>> C++ standard: 17.4.3.6/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.
>
> Couldn't Curiously Recurring Template Pattern be used to overcome
> this?

I'm not sure what you have in mind. Could you demonstrate?

Usually "Curiously Recurring Template Pattern" means something like
this:

template <class T> class Base { ... };
class Derived : public Base<Derived> { ... };

Here, quite obviously, Base is designed to be instantiated on an
incomplete type. On the other hand, C++ standard library templates
explicitly must not be instantiated on an incomplete type. I don't quite
see how Curiously Recurring Template Pattern applies.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925

John
Wed Feb 21 17:58:25 CST 2007

"Mark Randall" <markyr@gEEEEEmail.com> wrote in message
news:evkhl2fVHHA.4764@TK2MSFTNGP05.phx.gbl
> Hi,
>
> I am trying to reduce the complexity of a set of classes I made a
> couple of years ago, what equates to a set of trees, for which I want
> to use std::list and avoid having to use direct pointers anywhere.
>
> I wish to have a class contain a list of itself, as so:
>
> class B;
> class A
> {
> public:
> std::list<B> List;
> typedef std::list<B>::iterator iterator;
> iterator begin() { return List.begin(); }
> };
>
> class B
> {
> public:
> A m_a;
> };
>
> My question is, provided I ensure there is no in class A referencing
> direct instances of B, can I be fairly certain im not launching into
> a world of c++ driven pain, for example no:
>
> class A
> {
> ...
> B GetSomething();
> };
>
> I expect that as long as thing that call items such as copy
> constructors or -> / * operators of list<B>::iterator are in cpp files
> there
> should be no issue.
>
> Could anyone tell me different?


As Igor says, the Standard doesn't guarantee that it will work, but it does
currently work with VC++.

Note that class B is unnecessary, e.g., the following works.

class A
{
public:
A() : x(0)
{}
A(int a_x) : x(a_x)
{}
std::list<A> List;
typedef std::list<A>::iterator iterator;
iterator begin() { return List.begin(); }
iterator end() { return List.end(); }
void pushback(const A&arg)
{
List.push_back(arg);
}
void pop_back()
{
List.pop_back();
}
int GetValue()
{return x;}
private:
int x;
};


int main()
{
A a(1),b(2),c(3);
a.pushback(b);
a.pushback(c);

cout << a.GetValue() << endl;
for(A::iterator it = a.begin(); it!=a.end(); ++it)
cout << it->GetValue() << endl;


return 0;
}


--
John Carson

Ulrich
Thu Feb 22 03:30:09 CST 2007

Mark Randall wrote:
> I don't need to worry about portability, its written in MFC.

You will never want to compile this with another version of MFC, using
another version of the compiler to run on another version of MS Windows?
Okay, your choice.

> My understanding is that std::list in the MS library will never have any
> need store an instance as a member (by defenition of it being a linked
> list), and it is not an actual incomplete type at the time it is
> instantiated.

So? Did MS really guarantee that? Just fast-forward to the next release and
your code might stop working. In fact there is a growing trend of
intentionally making things that cause 'undefined behaviour' compile-time
errors or runtime errors.

Uli

Mark
Thu Feb 22 06:46:55 CST 2007

"Ulrich Eckhardt" <eckhardt@satorlaser.com> wrote:
> So? Did MS really guarantee that? Just fast-forward to the next release
> and
> your code might stop working. In fact there is a growing trend of
> intentionally making things that cause 'undefined behaviour' compile-time
> errors or runtime errors.

No they did not. But likewise in the VS EULA they failed to guarentee that
visual studio actually worked at all.

The idea of including a member T of a class std::list<T> simply doesnt make
any sense for a container being constructed of 0 size, it would be a waste
of memory, and have the potential to cause absolute chaos, even among
applications that use it perfectly.

I agree that if the list or vector was constructed at run-time with a given
size that was not 0 this would explode quicker than an Iraqi village.

But to me it just doesnt make sense at all for them to wreck their own
classes like that.

--
- Mark Randall
http://www.temporal-solutions.co.uk
http://www.awportals.com

Ulrich
Thu Feb 22 07:25:54 CST 2007

Mark Randall wrote:
> "Ulrich Eckhardt" <eckhardt@satorlaser.com> wrote:
>> So? Did MS really guarantee that? Just fast-forward to the next release
>> and
>> your code might stop working. In fact there is a growing trend of
>> intentionally making things that cause 'undefined behaviour' compile-time
>> errors or runtime errors.
>
> No they did not. But likewise in the VS EULA they failed to guarentee that
> visual studio actually worked at all.

Did they even document that as an intentional feature? That you don't get
any guarantees in general is given, but that's not what I meant. The point
is really that if this just happened by chance that with the next release
it might cease to work, just like converting a vector iterator into a
pointer.

> The idea of including a member T of a class std::list<T> simply doesnt
> make any sense for a container being constructed of 0 size, it would be a
> waste of memory, and have the potential to cause absolute chaos, even
> among applications that use it perfectly.

Imagine a container with this ctor:

container( size_type size = 0, element_type const& val = element_type());

This would break as soon as the type of element_type was incomplete.

> I agree that if the list or vector was constructed at run-time with a
> given size that was not 0 this would explode quicker than an Iraqi
> village.

I find that comparison of really bad taste. I hope you can share this
opinion.

> But to me it just doesnt make sense at all for them to wreck their own
> classes like that.

Depends - there is a distinction between maintaining a feature (hence my
question about guarantees) and using the freedom given by the C++ standard.
I have seen real problems that were caused by this; someone used
a 'feature' that was not guaranteed by anyone (vendor or standard) and then
their code broke on the next upgrade. And, I'm not even talking about the
pointer!=iterator issue. I don't think that this is likely to happen with
this exact example, but I won't rule it out that someone adds a
compile-time assertion that the type is complete somewhere to warn people
that their code is non-portable.

Uli

Mark
Thu Feb 22 08:22:07 CST 2007

"Ulrich Eckhardt" <eckhardt@satorlaser.com> wrote:
> Depends - there is a distinction between maintaining a feature (hence my
> question about guarantees) and using the freedom given by the C++
> standard.
> I have seen real problems that were caused by this; someone used
> a 'feature' that was not guaranteed by anyone (vendor or standard) and
> then
> their code broke on the next upgrade. And, I'm not even talking about the
> pointer!=iterator issue. I don't think that this is likely to happen with
> this exact example, but I won't rule it out that someone adds a
> compile-time assertion that the type is complete somewhere to warn people
> that their code is non-portable.

The template code is placed inline, no?

For the class itself to be constructed both the template and the class must
be already fully known (from the #include) in the CPP file...

-- header.h --
class B;
class A : public list<B> { }; << unknown here
class B { A m_a; };

-- test.cpp --
#include "header.h" << class becomes complete

int main()
{
B bclass; << class is complete here
...
}

Presuming A and B are both defined within a single header, the class type
should be complete for B to be able to be created I believe?

--
- Mark Randall
http://www.temporal-solutions.co.uk
http://www.awportals.com

John
Thu Feb 22 08:28:22 CST 2007

"Ulrich Eckhardt" <eckhardt@satorlaser.com> wrote in message
news:98i0b4-gr4.ln1@satorlaser.homedns.org
> Mark Randall wrote:
>> "Ulrich Eckhardt" <eckhardt@satorlaser.com> wrote:
>>> So? Did MS really guarantee that? Just fast-forward to the next
>>> release and
>>> your code might stop working. In fact there is a growing trend of
>>> intentionally making things that cause 'undefined behaviour'
>>> compile-time errors or runtime errors.
>>
>> No they did not. But likewise in the VS EULA they failed to
>> guarentee that visual studio actually worked at all.
>
> Did they even document that as an intentional feature? That you don't
> get any guarantees in general is given, but that's not what I meant.
> The point is really that if this just happened by chance that with
> the next release it might cease to work, just like converting a
> vector iterator into a pointer.


I am confident that it is intentional. The general issue has been discussed
in comp.lang.c++ and comp.lang.c++.moderated several times.

Initially, it seems that it was not known how to allow for incomplete types
in containers or at least what problems it might cause. Experience showed
that the problems were less than was feared. Accordingly, there has been a
trend for libraries to allow it. With VC++, it started with version 7.1 if
memory serves. I believe that gcc also allows it. The shared_ptr class in
the proposed new standard explicitly allows for incomplete types.

Incidentally, the code that I supplied also compiles with Comeau online. The
code that Mark originally supplied doesn't. Using list<A> inside A seems
more acceptable than using list<B> inside A when B is incomplete.

--
John Carson

Mark
Thu Feb 22 09:34:47 CST 2007

"John Carson" <jcarson_n_o_sp_am_@netspace.net.au> wrote:
> Incidentally, the code that I supplied also compiles with Comeau online.
> The code that Mark originally supplied doesn't. Using list<A> inside A
> seems more acceptable than using list<B> inside A when B is incomplete.

Indeed I did have the option of putting list<A> inside A, the reason why I
had somewhat side-stepped doing that was to keep code more readable a la
ListB::iterator = m_a.begin() rather than std::list<A>::iterator.

I realised later there was nothing stopping me from putting typedef
std::list<A> ListB after the end of class A { ... };

--
- Mark Randall
http://www.temporal-solutions.co.uk
http://www.awportals.com

Ben
Thu Feb 22 10:44:00 CST 2007

> Usually "Curiously Recurring Template Pattern" means something like this:
>
> template <class T> class Base { ... };
> class Derived : public Base<Derived> { ... };
>
> Here, quite obviously, Base is designed to be instantiated on an
> incomplete type. On the other hand, C++ standard library templates
> explicitly must not be instantiated on an incomplete type. I don't quite
> see how Curiously Recurring Template Pattern applies.

Ok, you're right. Curiously Recurring Template Pattern leaves the template
argument as an incomplete type. Hadn't realized that, and I suppose it
limits its utility somewhat.

(verified with the following, apparently ill-formed, program)
template <typename T>
class A
{
typename T::X i;
};

class B : A<B>
{
typedef int X;
};

int main(void) {}

Tom
Fri Feb 23 08:11:11 CST 2007

Mark Randall wrote:
> The idea of including a member T of a class std::list<T> simply doesnt make
> any sense for a container being constructed of 0 size, it would be a waste
> of memory,

And yet a string of size 0 can contain 16 characters. A deque of size 1
might contain many. etc. If lists of size 1 are quite common, it might
make sense to have a single element in the list.

and have the potential to cause absolute chaos, even among
> applications that use it perfectly.

A simple definition of list like this:

template <...>
class list
{
struct node
{
T value;
...
};
};

is going to require that T is complete. In fact, that's exactly why the
code didn't work in VC6 IIRC. But a legitimate optimized list
implementation might make use of one or more nodes embedded directly
inside the list, though this may cause problems if using a custom
allocator with a non-standard pointer type (which isn't required to be
supported in any case).

Tom

Tom
Fri Feb 23 08:30:29 CST 2007

Ulrich Eckhardt wrote:
> Imagine a container with this ctor:
>
> container( size_type size = 0, element_type const& val = element_type());
>
> This would break as soon as the type of element_type was incomplete.

The element type only need be complete if you actually use the default
argument. See 14.7.1/11.

Tom