Gennaro Prota wrote:
> On Mon, 11 Sep 2006 04:41:36 GMT, beman@acm.org (Beman Dawes) wrote:
>
>> Yes. One of the reasons we could be more aggressive with Boost was that
>> we had real standard conforming compilers and real standard conforming
>> Standard Libraries to test against. During work on the original
>> standard, neither was available. We had to compile and test as mental
>> exercises.
>
> Isn't that a bit overstated? I find it a bit unbelievable that the
> whole library specification was written without ever having a compiler
> to make at least some proof of concept. And, actually, I thought EDG
> provided such compiler(s).

It wasn't so much whole library as the template heavy parts,
particularly the STL. Remember that a lot of the critical work was done
in the 1993-95 time frame. The Borland compiler was used by many LWG
members. As we got further along in the standards process other
compilers such as EDG eclipsed Borland, but by then the library was
frozen, except for responses to defects that turned up as a result of
the two public Committee Draft comment periods.

--Beman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:
> On Mon, 11 Sep 2006 04:41:36 GMT, beman@acm.org (Beman Dawes) wrote:
>
>> Yes. One of the reasons we could be more aggressive with Boost was that
>> we had real standard conforming compilers and real standard conforming
>> Standard Libraries to test against. During work on the original
>> standard, neither was available. We had to compile and test as mental
>> exercises.
>
> Isn't that a bit overstated? I find it a bit unbelievable that the
> whole library specification was written without ever having a compiler
> to make at least some proof of concept. And, actually, I thought EDG
> provided such compiler(s).

It wasn't so much the whole library as the template heavy parts,
particularly the STL. Remember that a lot of the critical work was done
in the 1993-95 time frame. The Borland compiler was used by many LWG
members. As we got further along in the standards process other
compilers such as EDG eclipsed Borland, but by then the library was
frozen, except for responses to defects that turned up as a result of
the two public Committee Draft comment periods.

--Beman

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

In article <45134381.40003@acm.org>, Beman Dawes <beman@acm.org> writes
>It wasn't so much the whole library as the template heavy parts,
>particularly the STL. Remember that a lot of the critical work was done
>in the 1993-95 time frame. The Borland compiler was used by many LWG
>members. As we got further along in the standards process other
>compilers such as EDG eclipsed Borland, but by then the library was
>frozen, except for responses to defects that turned up as a result of
>the two public Committee Draft comment periods.
>
IIRC much of the template template stuff was written on faith.

--
Francis Glassborow      ACCU
Author of 'You Can Do It!' and "You Can Program in C++"
see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

James Kanze wrote:

>> It's one of the distinct features of shared_ptr that it's
>> pointee may be incomplete at any time but construction.
>
> It's all a question of contract.  The author's of the smart
> pointers in Boost decided to guarantee certain things which
> aren't guaranteed for the templates in the standard library.

Yes. One of the reasons we could be more aggressive with Boost was that
we had real standard conforming compilers and real standard conforming
Standard Libraries to test against. During work on the original
standard, neither was available. We had to compile and test as mental
exercises. Being conservative WRT incomplete types was one of the things
done to limit mistakes.

> If
> anyone felt it worthwhile to write up a proposal, I imagine that
> the library committee would be willing to consider increasing
> the guarantees for standard classes in the next version of the
> standard.

Yes, I would think so to. Particularly with C++0X Concepts, which allow
us to discover errors in requirements much earlier. (Since many prose
requirements are replaced by Concept constraints in the actual code,
compilers tell us right away if we get the requiremetn wrong.)

> But of course, if no one takes the time to actually write up a
> proposal, it isn't going to happen.  (From what I've seen, the
> people actively working in the library group aren't lacking in
> things to do.)

Yes. Threads is sucking up all the non-existent free time that the LWG
members never really had anyhow.

--Beman Dawes

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

James Kanze wrote:

>> It's one of the distinct features of shared_ptr that it's
>> pointee may be incomplete at any time but construction.
>
> It's all a question of contract.  The author's of the smart
> pointers in Boost decided to guarantee certain things which
> aren't guaranteed for the templates in the standard library.

Yes. One of the reasons we could be more aggressive with Boost was that
we had real standard conforming compilers and real standard conforming
Standard Libraries to test against. During work on the original
standard, neither was available. We had to compile and test as mental
exercises. Being conservative WRT incomplete types was one of the things
done to limit mistakes.

> If
> anyone felt it worthwhile to write up a proposal, I imagine that
> the library committee would be willing to consider increasing
> the guarantees for standard classes in the next version of the
> standard.

Yes, I would think so to. Particularly with C++0X Concepts, which allow
us to discover errors in requirements much earlier. (Since many prose
requirements are replaced by Concept constraints in the actual code,
compilers tell us right away if we get the requiremetn wrong.)

> But of course, if no one takes the time to actually write up a
> proposal, it isn't going to happen.  (From what I've seen, the
> people actively working in the library group aren't lacking in
> things to do.)

Yes. Threads is sucking up all the non-existent free time that the LWG
members never really had anyhow.

--Beman Dawes

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Mon, 11 Sep 2006 04:41:36 GMT, beman@acm.org (Beman Dawes) wrote:

>Yes. One of the reasons we could be more aggressive with Boost was that
>we had real standard conforming compilers and real standard conforming
>Standard Libraries to test against. During work on the original
>standard, neither was available. We had to compile and test as mental
>exercises.

Isn't that a bit overstated? I find it a bit unbelievable that the
whole library specification was written without ever having a compiler
to make at least some proof of concept. And, actually, I thought EDG
provided such compiler(s).

--
Gennaro Prota

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

kanze wrote:
> Jens Theisen wrote:
> > Greg Herlihy wrote:
> > > Both compilers should accept this code - there is nothing
> > > undefined about it at all. The tlist_iterator typedef is
> > > neither an explicit instantiation nor a specialization of
> > > std::list::iterator
>
> > Do you know where the requirement of list being instantiable
> > with incomplete T is in the standard? It should be somewhere.
>
>    17.4.3.6/2: "In particular, the effects are undefined in the
> following cases: [...] -- if an incomplete type is used as a
> template arugment when instantiating a template component."

Declaring an empty, derived class of T would be an obvious
"workaround". There is no question that T is complete in the program
below. But it should just as clear that the program's behavior is
indistinguishable from the original. After all, a program's behavior is
affected soley by the instructions it executes and the data it
processes. Instantiating std::list<T> (or any template class) creates
neither code nor data. And there cannot be undefined behavior when
there is no behavior at all.

    #include <list>

    struct T { int x; };

    template <class Type>
    struct SelfIter : public Type
    {
        SelfIter() : Type() {}

        typename std::list<Type>::iterator mIterator;
    };


    int main()
    {
        SelfIter<T> ti;

        std::list<T> tList;

        // insert ti in list while storing its iterator
        ti.mIterator = tList.insert( tList.begin(), ti);

    }

> The code you posted is illegal, and at least one
> compiler/library implemenation rejects it.

I would note that gcc's -D_GLIBCXX_CONCEPT_CHECK will reject any
program that so much as declares a std::list<T>. A concept check tests
a template class for its completeness - it does not test a program for
its correctness. In fact, a concept check essentially does nothing more
than declare a complete, explicit instantiation of std::list<T> like
so:

     template class std::list<T>;

and with the same, predictable results. As a test, a concept check is
useful (and is in fact intended only for) a person actually writing a
template class library. For any other type of programming, the types of
"failures" reported - such as the fact that T does not implement either
a < or a == operator are simply not relevant. A program that never
compares or sorts T objects and never calls any method in std::list
that does - has no reason (and certainly no obligation) to overload
those operators in T.

Greg


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> kanze wrote:
>> Jens Theisen wrote:
>>> Greg Herlihy wrote:
>>>> Both compilers should accept this code - there is nothing
>>>> undefined about it at all. The tlist_iterator typedef is
>>>> neither an explicit instantiation nor a specialization of
>>>> std::list::iterator
>>> Do you know where the requirement of list being instantiable
>>> with incomplete T is in the standard? It should be somewhere.
>> =A717.4.3.6/2: "In particular, the effects are undefined in the
>> following cases: [...] -- if an incomplete type is used as a
>> template arugment when instantiating a template component."
>=20
> Declaring an empty, derived class of T would be an obvious
> "workaround".

I must be missing some context: it appears from above that
you're suggesting deriving from an incomplete type.

> There is no question that T is complete in the program
> below. But it should just as clear that the program's behavior is
> indistinguishable from the original. After all, a program's behavior is
> affected soley by the instructions it executes and the data it
> processes.=20

Except in cases where translation may fail, so that the
program's behavior is purely at translation time (there
being no runtime in that situation).

> Instantiating std::list<T> (or any template class) creates
> neither code nor data.=20

It could; in typical implementations it doesn't.  But
that's not relevant; instantiation can fail, with an
error message.

> And there cannot be undefined behavior when
> there is no behavior at all.

Incorrect.  Undefined behavior just means "the standard
places no requirement on a conforming implementation if
it encounters code with this property".

[snip]

> I would note that gcc's -D_GLIBCXX_CONCEPT_CHECK will reject any
> program that so much as declares a std::list<T>. A concept check tests
> a template class for its completeness - it does not test a program for
> its correctness.=20

However, a failure of a concept check does indicate that
the code is not portable, as it fails to meet some
requirement placed on it by the C++ standard.  (If that
is not so, it's a bug in g++'s libstdc++.)

> In fact, a concept check essentially does nothing more
> than declare a complete, explicit instantiation of std::list<T> like
> so:
>=20
>      template class std::list<T>;
>=20
> and with the same, predictable results.=20

Not quite true; it can (and sometimes does) check for
properties not exercised by the implementation of
std::list, such as requiring copy assignment to be
defined on T.

> As a test, a concept check is
> useful (and is in fact intended only for) a person actually writing a
> template class library.=20

Not so, and indeed such implementors are better served
by some exemplar types which implement only the required
operations.

> For any other type of programming, the types of
> "failures" reported - such as the fact that T does not implement either
> a < or a =3D=3D operator are simply not relevant.=20

std::list does not require either, so its concept checks
should not test for those.

> A program that never
> compares or sorts T objects and never calls any method in std::list
> that does - has no reason (and certainly no obligation) to overload
> those operators in T.=20

Indeed.  That's standard-specified, if g++ gets it wrong
it's a defect that will likely be corrected promptly.

-- James

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> kanze wrote:
> > Jens Theisen wrote:
> > > Greg Herlihy wrote:
> > > > Both compilers should accept this code - there is nothing
> > > > undefined about it at all. The tlist_iterator typedef is
> > > > neither an explicit instantiation nor a specialization of
> > > > std::list::iterator

> > > Do you know where the requirement of list being instantiable
> > > with incomplete T is in the standard? It should be somewhere.

> >    17.4.3.6/2: "In particular, the effects are undefined in the
> > following cases: [...] -- if an incomplete type is used as a
> > template arugment when instantiating a template component."

> Declaring an empty, derived class of T would be an obvious
> "workaround".

For what?  The standard (   14.7.1/4) explicitly says that "A
class template specialization is implicitly instantiated if the
class type is uned in a context that requires a
completely-defined object type or if the completeness of the
class type affects the semantics of the program; [...]"   If you
derive from a template specialization, the specialization will
be instantiated.

> There is no question that T is complete in the program below.
> But it should just as clear that the program's behavior is
> indistinguishable from the original.

Why?

> After all, a program's behavior is affected soley by the
> instructions it executes and the data it processes.

I'd say that it could also be affected by whether the program
compiles or not.  A program with undefined behavior has just
that, undefined behavior.  The compiler might not compile it, or
it might generate different instructions.  The standard makes no
requirements.  (In the case in question, of course, it seems a
rather safe bet that if the code compiles, it will work.)

> Instantiating std::list<T> (or any template class) creates
> neither code nor data. And there cannot be undefined behavior
> when there is no behavior at all.

What makes you say that?  The standard says that instantiating a
standard template with an incomplete class is undefined
behavior.  Even if instantiating a class (as opposed to
instantiating the members of the class) does not necessarily
generate code or data, the standard signals other reasons why
the definition is necessary.

>     #include <list>

>     struct T { int x; };

>     template <class Type>
>     struct SelfIter : public Type
>     {
>         SelfIter() : Type() {}

>         typename std::list<Type>::iterator mIterator;
>     };

>     int main()
>     {
>         SelfIter<T> ti;

>         std::list<T> tList;

>         // insert ti in list while storing its iterator
>         ti.mIterator = tList.insert( tList.begin(), ti);

>     }

> > The code you posted is illegal, and at least one
> > compiler/library implemenation rejects it.

> I would note that gcc's -D_GLIBCXX_CONCEPT_CHECK will reject
> any program that so much as declares a std::list<T>.

Have you actually tried it?  I has no problems with the following
(legal) program:

    #include <list>

    class T ;
    typedef std::list< T > ListT ;

    extern void f( ListT& ) ;

The key is whether a complete type is needed or not.  In this
code, there is no place where a complete type is needed, so the
template specialization isn't instantiated, and there is no
problem.  Derive from std::list<T>, or use it on the left side
of a :: operator, and a complete type is needed, the compiler
instantiates the template, and g++ complains, because the
standard says that you have undefined behavior.

> A concept check tests a template class for its completeness -
> it does not test a program for its correctness.

I don't think you understand the concept checking done by g++
(which derives from that developped by Boost).

I've cut the rest, because your descriptions bear no resemblance
to what g++ does in its concept checking.

> In fact, a concept check essentially does nothing more than
> declare a complete, explicit instantiation of std::list<T>
> like so:

>      template class std::list<T>;

This is simply false.  The concept checking in g++ verifies a
lot of things: it insists, for example, that T be assignable,
even though the implementation of std::list in g++ never uses
assignment.  It does NOT force a complete instantiation of the
class; the only instantiations you get are those that you would
normally get.

> and with the same, predictable results. As a test, a concept
> check is useful (and is in fact intended only for) a person
> actually writing a template class library.

The concept check is designed for people using the class
library, not for those writing it.  It is designed to ensure
that you fulfil the contractual obligations, even if the actual
generated code doesn't require them.  It requires that the
instantiation type of std::list support assignment, for example,
although the g++ implementation (and I suspect most others) of
std::list never uses it.  Because the standard says that the
contained type of ALL standard containers must support
assignment, even if it isn't technically necessary for
std::list.

> For any other type of programming, the types of "failures"
> reported - such as the fact that T does not implement either a
> < or a == operator are simply not relevant.

And are not reported, unless you use a function which requires
them.  I don't know where you got your information about concept
checking, but it certainly doesn't come from using the g++
implementation.

> A program that never compares or sorts T objects and never
> calls any method in std::list that does - has no reason (and
> certainly no obligation) to overload those operators in T.

A program that never calls a function in std::list<T> which
contractually requires a < operator will not fail the concept
checks.  A program that calls, say, std::list<T>::sort will fail
to compile if it doesn't define an operator< for T.  In this
particular case, concept checks aren't even necessary, and
change nothing.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Jens Theisen wrote:
> Greg Herlihy wrote:

> > Furthermore, the T class can be just as easily implemented without a
> > typedef:

> >     #include <list>

> >     struct T
> >     {
> >          std::list<T>::iterator mIter;
> >     };

> Undefined behaviour as well, unless there is a guarantee in
> the standard that says otherwise. If std::list does something
> like the following Foo

> template< class T >
> struct Foo
> {
>    enum { s = sizeof(T) };
> };

> the above example will fail. If kanze is right, then an
> implementation is allowed to do that - though admittedly, I
> can't see a reason why it should.

In more than a few cases, the standard takes a simple approach.
Rather than trying to specify exactly what can and cannot be
instantiated with an incomplete type, it says that it is
undefined behavior to instantiate ANY template in the standard
library with an incomplete type.  In practice, I can't see a
real need for not supporting it for any of the standard
containers, but the author's of the standard chose not to go
into detail.

(Wisely, IMHO.  At the time the standard was being finalized, we
lacked much real experience with most of the standard library.
In such cases, it is almost always preferrable to be
conservative; it's easier to make undefined behavior defined in
a later version of the standard, than vice versa.)

> > In other words an class object would not be able to hold a
> > shared pointer to its own type.

> It's one of the distinct features of shared_ptr that it's
> pointee may be incomplete at any time but construction.

It's all a question of contract.  The author's of the smart
pointers in Boost decided to guarantee certain things which
aren't guaranteed for the templates in the standard library.  If
anyone felt it worthwhile to write up a proposal, I imagine that
the library committee would be willing to consider increasing
the guarantees for standard classes in the next version of the
standard.  I could see, for example, not requiring assignable
for std::list (while still requiring it for the other
collections), or not requiring a complete type to instantiate
one of the standard container (while requiring it for any
function in the container).  Whether such reduced instructions
are worth the bother or not, I don't know; I think it might be
useful to allow a class to contain a container of its types.

But of course, if no one takes the time to actually write up a
proposal, it isn't going to happen.  (From what I've seen, the
people actively working in the library group aren't lacking in
things to do.)

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> Both compilers should accept this code - there is nothing undefined
> about it at all. The tlist_iterator typedef is neither an explicit
> instantiation nor a specialization of std::list::iterator

Do you know where the requirement of list being instantiable with
incomplete T is in the standard? It should be somewhere.

Jens

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Jens Theisen wrote:
> Greg Herlihy wrote:
> > Both compilers should accept this code - there is nothing
> > undefined about it at all. The tlist_iterator typedef is
> > neither an explicit instantiation nor a specialization of
> > std::list::iterator

> Do you know where the requirement of list being instantiable
> with incomplete T is in the standard? It should be somewhere.

   17.4.3.6/2: "In particular, the effects are undefined in the
following cases: [...] -- if an incomplete type is used as a
template arugment when instantiating a template component."

The code you posted is illegal, and at least one
compiler/library implemenation rejects it.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> Louis Lavery wrote:
> > {I originally posted this on the 20/8/06 but didn't seem to
> > get any acknowledgement so am reposting.}

> > Is there a fundamental reason why the forward definition of
> > a container's iterators is not possible?

> No reason, since it is possible.

It depends on whether the container supports it.  The standard
containers don't.

> > Something akin to boost's adjacency_list_traits class[1] but
> > for std lists etc.  With such a mechanism, writing self (or
> > mutually) referencing containers would be a lot easier (in
> > fact, as things are, it is not possible to have a std::list
> > of Ts that hold iterators to themselves).

> There is no problem with declaring a std::list of class
> objects - each of which contains an iterator for the same type
> of std::list that is being instantiated.

I don't see how you can do it.

> > I know this can be modeled by, say, a std::list of T*s and
> > (depending how close a model you want) wrapping that list's
> > iterator in a transform iterator that dereferences the T*s.
> > But all that code is, well, code - and as such is bloat.  It
> > seems to me to be unnecessary as both of the two compilers I
> > use (vc7 and gcc 3.2) happily accept this code...

> > struct T;

> > typedef std::list<T>::iterator tlist_iterator; // <- UB

> > struct T {
> > tlist_iterator iter;
> > };

> > std::list<T> tlist;

> > which, although is formally UB, implies it's possible.

G++ 4.1.0 rejects it, at least when compiled with debugging and
checking options.

Technically, I think it should be possible.  But deciding
exactly what was or was not possible with an incomplete class is
a very complex affaire, and the committee decided to take the
easy way out, and just not allow it.  (Note that I don't think
that an implementation of std::list should ever assign an
object, so you could probably get away with instantiating it
with std::auto_ptr.  There, too, the committee felt it wiser to
not handle such special cases, and simply stated that all
containers require Assignable.)

> Both compilers should accept this code - there is nothing
> undefined about it at all.

The C++ standard explicitly says it's undefined behavior.  G++
4.1.0 rejects it.

> The tlist_iterator typedef is neither an explicit
> instantiation nor a specialization of std::list::iterator (in
> fact, the word "template" does not even appear anywhere in the
> declaration).

No, but it requires an instantiation of std::list<T>.  And the
standard says that instantiating std::list<T> over an incomplete
type is undefined behavior.

> Therefore tlist_iterator is simply an ordinary typedef.
> Incidentally, there is no requirement at this point that the
> "T" class ever be defined in the program. Instead,
> std::list<T> and its individual data members will be
> instantiated on a case-by-case basis, and only as needed to
> complete the program's semantics.

But the class definition itself must be instantiated as sound as
it is used on the left side of ::.  How can the compiler look
something up in the scope of a class if the class is not
complete?

> It is helpful here to recall that the Standard Library's
> iterator classes have "pointer-like" semantics (and some may
> in fact be implemented as pointers).

Which is completely irrelevant, because we cannot even find the
name iterator unless std::list<T> has been instantiated.

> So just as an object can declare a pointer to its own type as
> one of its members - there is likewise no reason why an object
> cannot declare an iterator to a container of objects of its
> own type as one of its own data members - exactly as
> demonstrated above.

Except that the standard says it is illegal.  Also, of course,
just because iterators have pointer like semantics doesn't mean
that you can use them exactly like pointers.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Jens Theisen wrote:
> Greg Herlihy wrote:
> > Both compilers should accept this code - there is nothing undefined
> > about it at all. The tlist_iterator typedef is neither an explicit
> > instantiation nor a specialization of std::list::iterator
>
> Do you know where the requirement of list being instantiable with
> incomplete T is in the standard? It should be somewhere.

T must be a complete type when std::list<T> is instantiated. Moreover
we can readily prove that T will always be a complete type whenever a
std::list<T> data member of T is instantiated:

First, a std::list<T> data member of T cannot be instantiated until a T
object is declared. Second, a T object cannot be declared unless T is a
complete type at the point of the declaration. Therefore T will always
be a complete object before any of its std::list<T> data members is
instantiated. Otherwise, if T were not a complete type, then the
declaration of the T object would fail and no instantiation of a T's
data members would be attempted.

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> T must be a complete type when std::list<T> is instantiated.

Meaning the following is indeed undefined, as the OP suspected.

 >> struct T;
 >>
 >> typedef std::list<T>::iterator tlist_iterator; // <- UB

Jens

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Jens Theisen wrote:
> Greg Herlihy wrote:
> > T must be a complete type when std::list<T> is instantiated.
>
> Meaning the following is indeed undefined, as the OP suspected.
>
>  >> struct T;
>  >>
>  >> typedef std::list<T>::iterator tlist_iterator; // <- UB

Except for the fact that the typedef does not instantiate
std::list<T>::iterator. The type argument for std::list needs to be
complete only at the point of its instantiation, if there is one. (the
latter is a requirement of the Standard Library and not of class
templates in general).

At the point of tlist_iterator's typedef declaration, the compiler has
no idea whether tlist_iterator is ever used subsequently - and
therefore has no idea whether instantiating std::list<T>::iterator is
necessary to complete the program. And unless the instantiation in
question is necessary, the compiler is not allowed to instantiate the
template class implicitly.

Furthermore, the T class can be just as easily implemented without a
typedef:

    #include <list>

    struct T
    {
         std::list<T>::iterator mIter;
    };

    int main()
    {
          T t; // std::list<T>::iterator instantiated here

          ...
    }

With or without the typedef, the program needs T's type to be complete
no earlier than the first line of main - the point at which a T object
is first declared. And clearly, T is a complete type at that point.

After all, if a class could not declare a member function with its own
type as a parameter, the following declaration would be undefined:

    #include <tr1/memory>

    struct A
    {
        std::tr1::shared_ptr<A> next;
    };

In other words an class object would not be able to hold a shared
pointer to its own type.

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> Jens Theisen wrote:
> > Greg Herlihy wrote:
> > > Both compilers should accept this code - there is nothing
> > > undefined about it at all. The tlist_iterator typedef is
> > > neither an explicit instantiation nor a specialization of
> > > std::list::iterator

> > Do you know where the requirement of list being instantiable
> > with incomplete T is in the standard? It should be
> > somewhere.

> T must be a complete type when std::list<T> is instantiated.

And it will be instantiated any time the compiler needs a
complete type for std::list<T>.  If std::list<T> is used as a
member, for example, or as a base class.  Or as the qualifier in
a qualified name, e.g. std::list<T>::iterator.

> Moreover we can readily prove that T will always be a complete
> type whenever a std::list<T> data member of T is instantiated:

True, but how is that relevant.

--
James Kanze (Gabi Software)              email: kanze.james@neuf.fr
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
>> >> struct T;
>> >>
>> >> typedef std::list<T>::iterator tlist_iterator; // <- UB
>
> Except for the fact that the typedef does not instantiate
> std::list<T>::iterator.

It instantiates std::list<T>, and it's not guaranteed to be possible
with incomplete T.

> Furthermore, the T class can be just as easily implemented without a
> typedef:
>
>     #include <list>
>
>     struct T
>     {
>          std::list<T>::iterator mIter;
>     };

Undefined behaviour as well, unless there is a guarantee in the standard
that says otherwise. If std::list does something like the following Foo

template< class T >
struct Foo
{
   enum { s = sizeof(T) };
};

the above example will fail. If kanze is right, then an implementation
is allowed to do that - though admittedly, I can't see a reason why it
should.

> In other words an class object would not be able to hold a shared
> pointer to its own type.

It's one of the distinct features of shared_ptr that it's pointee may be
incomplete at any time but construction.

Jens

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

{I originally posted this on the 20/8/06 but didn't seem to
get any acknowledgement so am reposting.}


Is there a fundamental reason why the forward definition of
a container's iterators is not possible? Something akin to
boost's adjacency_list_traits class[1] but for std lists etc.
With such a mechanism, writing self (or mutually) referencing
containers would be a lot easier (in fact, as things are, it
is not possible to have a std::list of Ts that hold iterators
to themselves).

A trivial example of use may help clarify...

struct T;

typedef std::list_traits<T>::iterator tlist_iterator;

struct T {
tlist_iterator iter;
};

std::list<T> tlist;

I know this can be modeled by, say, a std::list of T*s and
(depending how close a model you want) wrapping that list's
iterator in a transform iterator that dereferences the T*s.
But all that code is, well, code - and as such is bloat.
It seems to me to be unnecessary as both of the two compilers
I use (vc7 and gcc 3.2) happily accept this code...

struct T;

typedef std::list<T>::iterator tlist_iterator; // <- UB

struct T {
tlist_iterator iter;
};

std::list<T> tlist;

.which, although is formally UB, implies it's possible.

It's also backward compatible, being merely the addition
of some form of traits class for each container.

Further, that the guys at Boost have resorted to "void*"s
and casting[1] lends heavy weight to the argument that
some form of forward definition of container iterators
is highly desirable.

Louis.

[1] The idea of container traits was inspired by the BGL.
And it has been said, regarding the BGL, that it's possible
container traits would enable the replacement of the "void*"
vertex descriptors (and all of the evil casting that implies)
with actual, typed descriptors.




---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Louis Lavery wrote:
> .which, although is formally UB, implies it's possible.

UB because it's not guaranteed that the template can be instantiated
with an incomplete T? Do you know that this is not guaranteed?

There are range traits in the boost range library, but for standard
containers, their typedefs are just forwarders.

Jens

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Louis Lavery wrote:
> {I originally posted this on the 20/8/06 but didn't seem to
> get any acknowledgement so am reposting.}
>
>
> Is there a fundamental reason why the forward definition of
> a container's iterators is not possible?

No reason, since it is possible.

> Something akin to
> boost's adjacency_list_traits class[1] but for std lists etc.
> With such a mechanism, writing self (or mutually) referencing
> containers would be a lot easier (in fact, as things are, it
> is not possible to have a std::list of Ts that hold iterators
> to themselves).

There is no problem with declaring a std::list of class objects - each
of which contains an iterator for the same type of std::list that is
being instantiated.

> I know this can be modeled by, say, a std::list of T*s and
> (depending how close a model you want) wrapping that list's
> iterator in a transform iterator that dereferences the T*s.
> But all that code is, well, code - and as such is bloat.
> It seems to me to be unnecessary as both of the two compilers
> I use (vc7 and gcc 3.2) happily accept this code...
>
> struct T;
>
> typedef std::list<T>::iterator tlist_iterator; // <- UB
>
> struct T {
> tlist_iterator iter;
> };
>
> std::list<T> tlist;
>
> which, although is formally UB, implies it's possible.

Both compilers should accept this code - there is nothing undefined
about it at all. The tlist_iterator typedef is neither an explicit
instantiation nor a specialization of std::list::iterator (in fact, the
word "template" does not even appear anywhere in the declaration).
Therefore tlist_iterator is simply an ordinary typedef. Incidentally,
there is no requirement at this point that the "T" class ever be
defined in the program. Instead, std::list<T> and its individual data
members will be instantiated on a case-by-case basis, and only as
needed to complete the program's semantics.

It is helpful here to recall that the Standard Library's iterator
classes have "pointer-like" semantics (and some may in fact be
implemented as pointers). So just as an object can declare a pointer to
its own type as one of its members - there is likewise no reason why an
object cannot declare an iterator to a container of objects of its own
type as one of its own data members - exactly as demonstrated above.

In fact a few additional lines of code should be enough to demonstrate
that there is no undefined behavior with T's declaration or its
behavior:

    int main()
    {
        std::list<T> tlist;

        tlist.push_front(T());
        tlist.push_back(T());
        tlist.pop_front();
        tlist.pop_back();
    }

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Louis Lavery wrote:
> Is there a fundamental reason why the forward definition of
> a container's iterators is not possible?

No reason, since it is possible.

> Something akin to
> boost's adjacency_list_traits class[1] but for std lists etc.
> With such a mechanism, writing self (or mutually) referencing
> containers would be a lot easier (in fact, as things are, it
> is not possible to have a std::list of Ts that hold iterators
> to themselves).

There is no problem with declaring a std::list of class objects - each
of which contains an iterator for the same type of std::list that is
being declared.

> I know this can be modeled by, say, a std::list of T*s and
> (depending how close a model you want) wrapping that list's
> iterator in a transform iterator that dereferences the T*s.
> But all that code is, well, code - and as such is bloat.
> It seems to me to be unnecessary as both of the two compilers
> I use (vc7 and gcc 3.2) happily accept this code...
>
> struct T;
>
> typedef std::list<T>::iterator tlist_iterator; // <- UB
>
> struct T {
> tlist_iterator iter;
> };
>
> std::list<T> tlist;
>
> which, although is formally UB, implies it's possible.

Both compilers should accept this code - there is nothing undefined
about it at all. The tlist_iterator typedef is neither an explicit
instantiation nor a specialization of std::list::iterator (in fact, the
word "template" does not even appear anywhere in the declaration).
Therefore tlist_iterator is simply an ordinary typedef. Incidentally,
there is no requirement at this point that the "T" class ever be
defined in the program. Instead, std::list<T> and its individual data
members will be instantiated on a case-by-case basis, and only as
needed to complete the program's semantics.

It may be helpful to recall that the Standard Library's iterator
classes have "pointer-like" semantics (and some may in fact be
implemented as pointers). So, just as an object can declare a pointer
to its own type as one of its members, there is likewise no reason why
an object cannot declare an iterator to a container of objects of its
own type as one of its own data members - exactly as demonstrated
above.

In fact, a few additional lines of code should be enough to demonstrate
that there is no undefined behavior with T at all:

    int main()
    {
        std::list<T> tlist;

        tlist.push_front(T());
        tlist.push_back(T());
        tlist.pop_front();
        tlist.pop_back();
    }

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]