Re: tree_node using std::vector
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.
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.
In other words, undefined effects upon the Standard Library do not
(necessarily) imply undefined behavior on the part of the C++ program.
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. 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.
"?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.
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.
Greg
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]