Re: tree_node using std::vector
On 18 Mai, 07:29, Greg Herlihy <gre...@mac.com> wrote:
On May 17, 1:31 pm, Daniel Kr?gler <daniel.krueg...@googlemail.com>
wrote:
On 17 Mai, 01:26, Maik Beckmann <maikbeckm...@gmx.de> wrote:
Are there compilers around which STL implementations doesn't compile
this
struct tree_node {
std::vector<tree_node> children;
};
I came across this when I've tried mingw's gcc-4.3 alpha release which
was
configured with concept-checks enabled. The above code fails to
compile
because tree_node is incomplete when its used inside it's definition.
So you found at least one compiler who rejects this code.
Not exactly. It is an optional "concept-check" test that rejects the
std::vector instantiated with an incomplete type. But the failure of
this test is less informative than at first it might seem. Because the
only conclusion that we can draw from the failure is that this
particular std::vector specialization is not portable - that is, a C++
compiler might not be able to compile it. Note, that the failure does -
not- imply that the current implementation's own C++ compiler will
reject the vector specialization. In fact, the C++ compiler in this
case accepts it.
To begin with, any form of compiler-configuration is outside
of the scope of the standard. So, if some gcc-configuration
rejects this code it's valid to say that a compiler rejects
the code. We can argue now whether the compiler is conforming
to do that and the current state of the standard is, that
such rejection is conforming, because the code causes undefined
behavior. I do not understand what you mean with "In fact, the
C++ compiler in this case accepts it", but the OP has clearly
said "The above code fails to compile because tree_node is
incomplete when its used inside it's definition.". The only
reasonable correspondence to what the standard nominates as a
"diagnostic" for a violation of the standard which does not
require a diagnostic.
I know the standard forbids incomplete types to be used with STL
containers.
Does the above code work on any STL implemention anyway (in case
mentioned
kind of concept-checks are disabled) and is thus portable?
You can definitely not nominate this as portable, because
the standard says that it will cause undefined behavior
([lib.res.on.functions]/2, last bullet). Seemingly working
code is one possible outcome of undefined behavior, see
[intro.compliance], footnote 3:
Actually, the C++ Standard states that the "effects" (presumably upon
the C++ Standard Library) of instantiating a library class template
with an incomplete type, is "undefined." Not the program's behavior.
You are right, that the standard says the the "effects are undefined".
But the OP is going to construct a C++ with the C++ library and this
program will cause undefined behavior, [defns.undefined]/1.
Undefined behavior is a permission, it is not a must and the standard
also allows a run-time behavior with correct execution,
[intro.compliance]. But the standard also says clearly that this is
an "erroneous program construct [..] for which this International
Standard imposes no requirements".
In other words, undefined effects upon the Standard Library do not
(necessarily) imply undefined behavior on the part of the C++ program.
The standard does not differentiate here. Either an erroneous program
construct or erroneous data, see above. If the OP uses the standard
libary as part of his program in some way which has undefined
effects, this influences the program, not any specific parts of it.
Because, it could be the case that the behavior left undefined by the
Standard Library specification portion of the C++ Standard is
nonetheless defined by the C++ language specification portion of the
same Standard.
Sorry, this does not apply or I miss a definite quote of the
standard which says exactly this.
In fact, such is the case here. According to the C++
language specification - only one of two things can ever happen when a
program instantiates a template (such as a std::vector) with an
incomplete type.
According to the C++ Standard, a program that uses an incomplete type
wherever a complete type is required - is ill-formed. So the worst
that can happen to a program that tries to instantiate a std::vector
with an incomplete type is that the program will not compile. By the
same token, a C++ program that -is- able to instantiate (without any
error message) a std::vector with a incomplete type is at no risk of
behaving in an undefined manner (for having instantiated the vector).
Essentially, according to the C++ Standard, it is not possible for the
presence of an incomplete type in a C++ program to have any effect -
other than to make the program itself, ill-formed.
Sorry, this is wrong. There is an easy counter example for
this:
struct C {
class Impl;
Impl* p;
C();
~C() {
delete p;
}
} c;
#include <string>
struct C::Impl {
std::string s;
Impl() : s("Hello") {}
};
C::C() : p(new Impl()) {
}
int main() {
return c.p->s.size() > 0;
}
This program causes undefined behavior, because
it violates [expr.delete]/5:
"If the object being deleted has incomplete class type
at the point of deletion and the complete class has a
non-trivial destructor or a deallocation function, the
behavior is undefined."
In this case C::Impl does not have a trivial d'tor.
Another example is directly obtainable from
[expr.unary.op]/4:
"The address of an object of incomplete type can be
taken, but if the complete type of that object is a
class type that declares operator&() as a member
function, then the behavior is undefined (and no
diagnostic is required)".
"?Correct execution? can include undefined behavior,
depending on the data being processed; see 1.3 and 1.9."
The issue in this case is not whether the program has undefined
behavior (it does not) - but whether the program itself is well-
formed.
Your conclusion is wrong, the program causes undefined
behavior, even if it is well-formed.
This code will probably be accepted on most compilers,
but you shouldn't ignore those who explicitly check
that - this is conforming.
As noted above, the std::vector instantiation in question is well-
behaved for any implementation which accepts it. So, as long as the
vector compiles on every implementation that the programmer happens to
care about, then the fact that the std::vector specialization might
not compile on some other, hypothetical implementation would seem, at
best, a purely academic point.
I demonstrated above, that this assumption is invalid and
clearly not supported by the standard.
Greetings from Bremen,
Daniel Kr?gler
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]