Re: Cyclic dependency?
Louis Lavery wrote:
kanze wrote:
Louis Lavery wrote:
The following compiles under g++ 3.2 and vc7, but should it
compile on all platforms?
/* test.cpp */
#include <list>
struct Vertex;
struct Edge;
typedef std::list<Vertex>::iterator Vit;
typedef std::list<Edge>::iterator Eit;
Formally, you have undefined behavior here. The type
expression std::list<>::iterator requires the instantiation
of the template std::list, and the standard says that
instantiating a template from the standard with an incomplete
type is undefined behavior.
Yes, that makes it non-portable :-(
Is there any fundamental reason why something like...
std::list_traits<T>
{
typedef ... iterator;
typedef ... const_iterator;
.
};
...is not possible without instantiating std::list<T>?
Well, it would have been possible to define containers like
this, but that's not the way the standard does it. The type
expression isn't std::list_traits<Vertex>::iterator, but
std::list<Vertex>::iterator. (Of course, if we were going this
route, it would probably be container_traits, and not
list_traits.)
G++ 4.1.0 complains, at least with the options I usually use for
debug builds (-D_GLIBCXX_CONCEPT_CHECKS, for example).
Why do you want to use iterators here? For internal pointers in
graphs, I've yet to see any acceptable replacement for raw
pointers.
If the graph stores its vertices in std::list<Vertex> and its
edges in std::list<Edge> and the vertices hold only pointers
to their edges then to remove a particular edge from a
particular vertex requires searching the whole edge list for
that edge.
If the vertices hold iterators to their edges then the edge
can be removed in constant time.
Good point. As it is currently written, I don't see any simple
work around; about the only possibility I see, in fact, is an
additional level of indirection.
--
James Kanze 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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]