Re: container traits
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 orient9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S9mard, 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 ]