struct in struct

[Gunnar G]

Hello.
My compiler (GCC 3.3.*) does not complain about the following:

#include <iostream>
#include <vector>
using namespace std;

struct X{
int a,b,c;
vector<X> pp;
};

int main(){
X a;
}


So there is not a problem with this self-refering struct, why?
Must not vector know the size of what it should contain?

 

[Leor Zolman]

Hello.
My compiler (GCC 3.3.*) does not complain about the following:

#include <iostream>
#include <vector>
using namespace std;

struct X{
int a,b,c;
vector<X> pp;
};

int main(){
X a;
}


So there is not a problem with this self-refering struct, why?
Must not vector know the size of what it should contain?

Ah, but not /yet/. At the point where pp is declared, there's nothing yet
happening where the vector "needs to know" the size of X. Go take a look at
std::vector's class definition in whatever lib (gcc, I guess) you're using,
and you'll see that it probably makes use of a pointer to X, but you won't
see any X objects themselves declared in the class definition. By the time
it needs to specialize member functions such as push_back [say, for
example, if you were to add this line to main:
a.pp.push_back(X());
] then X is a complete type and it works.
-leor

 

[E. Robert Tisdale]

My compiler (GCC 3.3.*) does not complain about the following:

#include <iostream>
#include <vector>
using namespace std;

struct X{
int a,b,c;
vector<X> pp;
};

int main(){
X a;
}


So there is not a problem with this self-refering struct, why?
Must not vector know the size of what it should contain?

cat self.cc

#include <iostream>
#include <vector>

struct X{
int a,b,c;
std::vector<X> pp(1);
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc:6: error: invalid data member initialization
self.cc:6: error: (use `=' to initialize static data members)

g++ --version

g++ (GCC) 3.3.3 20040412 (Red Hat Linux 3.3.3-7)

 

[E. Robert Tisdale]

Ah, but not /yet/. At the point where pp is declared,
there's nothing yet happening where the vector "needs to know" the size of X.
Go take a look at std::vector's class definition
in whatever lib (gcc, I guess) you're using,
and you'll see that it probably makes use of a pointer to X,
but you won't see any X objects themselves declared in the class definition.

Are you saying that this behavior is implementation dependent?

By the time it needs to specialize member functions such as push_back
[say, for example, if you were to add this line to main:
a.pp.push_back(X());
] then X is a complete type and it works.

 

[Leor Zolman]

#include <iostream>
#include <vector>

struct X{
int a,b,c;
std::vector<X> pp(1);

Um, the OP's original example somehow seems to have grown a "(1)" by the
time it reached your computer. I can't explain why. Using the original
example,

d:\src\learn>g++ -Wall -ansi -pedantic x.cpp
d:\src\learn>

-leor

};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc:6: error: invalid data member initialization
self.cc:6: error: (use `=' to initialize static data members)

g++ --version

g++ (GCC) 3.3.3 20040412 (Red Hat Linux 3.3.3-7)

 

[Leor Zolman]

Are you saying that this behavior is implementation dependent?

No I'm not; nor am I saying it isn't. I don't truly know. I was suggesting
how it could be possible, on the OP's platform, for that declaration of pp
to work with the incomplete (at that point) type X.
-leor

By the time it needs to specialize member functions such as push_back
[say, for example, if you were to add this line to main:
a.pp.push_back(X());
] then X is a complete type and it works.

 

[E. Robert Tisdale]

Um, the OP's original example somehow seems to have grown a "(1)" by the
time it reached your computer. I can't explain why. Using the original
example,

d:\src\learn>g++ -Wall -ansi -pedantic x.cpp
d:\src\learn>

Which, I believe,
is what Gunnar G was reporting for an *empty* container.

cat self.cc

#include <iostream>

template <typename T>
struct myVector {
T a[1];
};

struct X{
int a,b,c;
myVector<X> pp;
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc: In instantiation of `myVector<X>':
self.cc:10: instantiated from here
self.cc:5: error: `myVector<T>::a' has incomplete type
self.cc:8: error: forward declaration of `struct X'
self.cc: In function `int main(int, char**)':
self.cc:14: warning: unused variable `X a'

is probably the case that Gunnar G was concerned about.

 

[Denis Remezov]

Which, I believe,
is what Gunnar G was reporting for an *empty* container.

cat self.cc

#include <iostream>

template <typename T>
struct myVector {
T a[1];
};

struct X{
int a,b,c;
myVector<X> pp;
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc: In instantiation of `myVector<X>':
self.cc:10: instantiated from here
self.cc:5: error: `myVector<T>::a' has incomplete type
self.cc:8: error: forward declaration of `struct X'
self.cc: In function `int main(int, char**)':
self.cc:14: warning: unused variable `X a'

is probably the case that Gunnar G was concerned about.

So, you get an error here since you are declaring the array T a[1], and that
implies that something (the compiler?) would have to know the size of the
"T" in order to allocate memory? But with a STL-vector , it uses (perhaps
pointers) so it would not have to know the size, or the size is easy to
find, since it's just an sizeof(int)+sizeof(X-pointer)+overhead ?

I think there is a way to break your original example by requiring the
template parameter to be a complete type for the purpose of vector's member
specification. Imagine an implementation like this:

template <typename T, class Allocator = allocator <T> >
class vector {
enum {
element_size = sizeof(T)
};

//...
};

I haven't decided why anyone would want to do that, but wouldn't it
still be a conforming implementation?

Denis

 

[Leor Zolman]

Which, I believe,
is what Gunnar G was reporting for an *empty* container.

Sorry, I have no idea what you're talking about. He was reporting that
he drew no errors, and asking how that could be--a perfectly
reasonable question, IMO. I would probably have guessed, if shown his
code, without being told it compiles, that it should have drawn an
error. But it does not; so, as per Mr. Holmes, "When you have
eliminated the impossible..."

cat self.cc

#include <iostream>

template <typename T>
struct myVector {
T a[1];
};

struct X{
int a,b,c;
myVector<X> pp;
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc: In instantiation of `myVector<X>':
self.cc:10: instantiated from here
self.cc:5: error: `myVector<T>::a' has incomplete type
self.cc:8: error: forward declaration of `struct X'
self.cc: In function `int main(int, char**)':
self.cc:14: warning: unused variable `X a'

is probably the case that Gunnar G was concerned about.

Why isn't the case he actually showed us the one he was most likely to
actually be concerned about? Why would he have taken the trouble to
obfuscate what he was /really/ wanting to know about, by conjuring up
such an example that does not draw an error?
-leor

 

[Gunnar G]

Which, I believe,

is what Gunnar G was reporting for an *empty* container.

cat self.cc

#include <iostream>

template <typename T>
struct myVector {
T a[1];
};

struct X{
int a,b,c;
myVector<X> pp;
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc: In instantiation of `myVector<X>':
self.cc:10: instantiated from here
self.cc:5: error: `myVector<T>::a' has incomplete type
self.cc:8: error: forward declaration of `struct X'
self.cc: In function `int main(int, char**)':
self.cc:14: warning: unused variable `X a'

is probably the case that Gunnar G was concerned about.

So, you get an error here since you are declaring the array T a[1], and that
implies that something (the compiler?) would have to know the size of the
"T" in order to allocate memory? But with a STL-vector , it uses (perhaps
pointers) so it would not have to know the size, or the size is easy to
find, since it's just an sizeof(int)+sizeof(X-pointer)+overhead ?

 

[E. Robert Tisdale]

Which, I believe,
is what Gunnar G was reporting for an *empty* container.

cat self.cc

#include <iostream>

template <typename T>
struct myVector {
T a[1];
};

struct X{
int a,b,c;
myVector<X> pp;
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc: In instantiation of `myVector<X>':
self.cc:10: instantiated from here
self.cc:5: error: `myVector<T>::a' has incomplete type
self.cc:8: error: forward declaration of `struct X'
self.cc: In function `int main(int, char**)':
self.cc:14: warning: unused variable `X a'

is probably the case that Gunnar G was concerned about.

So, you get an error here since you are declaring the array T a[1]
and that implies that something (the compiler?)
would have to know the size of the "T" in order to allocate memory?
But, with a STL-vector, it uses (perhaps pointers)
so it would not have to know the size, or the size is easy to find
since it's just an sizeof(int)+sizeof(X-pointer)+overhead?

I think that that's right. What I can't tell you is
whether the standard specifies that behavior for template class vectors.
What we need is a good language lawyer.

 

[Leor Zolman]

Which, I believe,
is what Gunnar G was reporting for an *empty* container.

cat self.cc

#include <iostream>

template <typename T>
struct myVector {
T a[1];
};

struct X{
int a,b,c;
myVector<X> pp;
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc: In instantiation of `myVector<X>':
self.cc:10: instantiated from here
self.cc:5: error: `myVector<T>::a' has incomplete type
self.cc:8: error: forward declaration of `struct X'
self.cc: In function `int main(int, char**)':
self.cc:14: warning: unused variable `X a'

is probably the case that Gunnar G was concerned about.

So, you get an error here since you are declaring the array T a[1], and that
implies that something (the compiler?) would have to know the size of the
"T" in order to allocate memory?

Right. "myVector" contains a data declaration
T a[1];
(which doesn't need to be an array; a simple
T a;
would have similar results for the purpose of this example) that requires
a complete definition for the type T, which, at the point of pp's
declaration, is not available.

But with a STL-vector , it uses (perhaps
pointers) so it would not have to know the size, or the size is easy to
find, since it's just an sizeof(int)+sizeof(X-pointer)+overhead ?

Right, std::vector would not have to know the size of its value_type at the
point of pp's declaration in your original example.
-leor

 

[Wouter Lievens]

definition.

Are you saying that this behavior is implementation dependent?

No, the size of std::vector<T> is a constant. It does not change during
run-time execution, because all classes have a constant size. The elemens an
std::vector contains are located on the heap.

By the time it needs to specialize member functions such as push_back
[say, for example, if you were to add this line to main:
a.pp.push_back(X());
] then X is a complete type and it works.

 

[John Carson]

Hello.
My compiler (GCC 3.3.*) does not complain about the following:

#include <iostream>
#include <vector>
using namespace std;

struct X{
int a,b,c;
vector<X> pp;
};

int main(){
X a;
}


So there is not a problem with this self-refering struct, why?
Must not vector know the size of what it should contain?

This was discussed some time ago both on this newsgroup and
comp.lang.c++.moderated. There are two statements in the standard that are
relevant. The first is in 14.3.1 p2 of the 2003 standard. It says:

"[Note: a template type argument may be an incomplete type (3.9). ]"

The second is in section 17.4.3.6 of the standard. It says:

"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:
[snip]
- if an incomplete type (3.9) is used as a template argument when
instantiating a template component."

The second quotation prompts the question of exactly when "instantiation"
takes place. The newsgroup discussion suggested that the use of the
vector<X> pp; in your struct declaration DOES constitute instantiation for
the purposes of the quoted passage.

The general conclusion from the discussion (as interpreted by me) was:

1. In general, there is no language bar against template arguments that are
incomplete types in the contexts that you are discussing,
2. Whether or not incomplete types are allowed in this context depends on
the details of the template class concerned. The passage from 17.4.3.6 says
that the standard library is not required to accept incomplete types as
arguments. This was originally because it was not known if the standard
library could be implemented in such a way as to allow incomplete types (in
fact, there were some claims that vectors could not be implemented in such a
way).

The Dinkumware library (which ships with VC++ 7.1, among others) does allow
containers with incomplete types in the context you have described. gcc
apparently does too. Now that its technical feasibility has been shown, it
is likely to make it into the standard. For the present, however, the
property is implementation-dependent.

Two of the original discussions are here (I seem to remember a third thread
but can't find it):

http://groups.google.com/groups?hl=...dZ_b.1662%24SZ.61136%40news.xtra.co.nz&rnum=4

and here

http://groups.google.com/groups?hl=...02170837.7f182aab%40posting.google.com&rnum=1

 

[josh]

cat self.cc

#include <iostream>
#include <vector>

struct X{
int a,b,c;
std::vector<X> pp(1);
};

int main(int argc, char* argv[]){
X a;
return 0;
}

g++ -Wall -ansi -pedantic -o self self.cc

self.cc:6: error: invalid data member initialization
self.cc:6: error: (use `=' to initialize static data members)

gcc seems pretty clear on the matter: you can't initialize data members
like that.

try:
struct X{
int a,b,c;
std::vector<int> pp(1);
};

Same error, I'll bet.

-josh