Cyclic dependency? - comp.lang.c++.moderated

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; struct Vertex { Eit eit; }; struct Edge { Vit vit; }; int main() { Vertex v; Edge e; } /* test.cpp end */ Thanks Louis. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

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; The C++ standard requires that "The type of objects stored in these components must meet the requirements of CopyConstructible types (20.1.3), and the additional requirements of Assignable types." (23.1 3) Since Vertex and Edge have not been fully defined yet, it is unclear whether they meet those requirements. Therefore the compiler is allowed to reject list<Vertex> and list<Edge>. For example, new versions of g++ do this when they have been compiler with the --enable-concept-checks option: > g++ -c t.cc /usr/local/gcc-4.1.1/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++ /4.1.1/bits/boost_concept_check.h: In instantiation of '__gnu_cxx::_SGIAssignableConcept<Vertex>': /usr/local/gcc-4.1.1/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++ /4.1.1/bits/stl_list.h:402: instantiated from 'std::list<Vertex, std::allocator<Vertex> >' t.cc:8: instantiated from here /usr/local/gcc-4.1.1/lib/gcc/i686-pc-linux-gnu/4.1.1/../../../../include/c++ /4.1.1/bits/boost_concept_check.h:216: error: '__gnu_cxx::_SGIAssignableConcept<_Tp>::__a' has incomplete type -- ------------- Matti Rintala ------------ matti.rintala@tut.fi ------------ Painting is the art of inclusion. Photography is an art of exclusion. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

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. 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. -- 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 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

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; > > struct Vertex > { > Eit eit; > }; > > struct Edge > { > Vit vit; > }; Yes, the declarations of Vertex and Edge are portable. The fact that each struct has an iterator data member referring to the other is perfectly valid. After all, an iterator is much like a pointer (and in fact may be a pointer). So replacing the iterator data member with a pointer may help illustrate the relationship between Vertex and Edge. struct Edge; struct Vertex { Edge* eit; }; struct Edge { Vertex* vit; }; In fact, the pointer is probably more useful than a lone iterator. Because wthout its container, an iterator cannot be used to iterate. For example, there is no way to tell whether ++eit or --eit can be safely dereferenced - in fact there is no way tell whether eit itself has been initialized with a valid iterator and can itself be safely deferenced. A pointer that cannot safely be dereferenced could be set to NULL. Furthermore, it seems likely a Vertex object may have more than one associated Edge, and likewise that an Edge object may have more than one associated Vertex. So instead of an iterator data member, why not have the data member be the iterator's container itself? For one reason, neither Edge or Vertex could have a data member container that stored Edges and Vertexes by value - since each type would end up containing an instance of the other - and indirectly an instance of its own type. There are ways to avoid self-inclusion: the data member container could be declared as a pointer or as a reference to a container - or the data member container could hold pointers to - or std::tr1::reference_wrappers of - instances of the other type. Greg [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

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>? > 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. Louis. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

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. The Vit and Eit typedefs don't instantiate anything. A typedef simply creates another name for a class (or typedef). And there is no code or data that needs to be instantiated for std::list<Edge>::iterator to be called by another name. The std::list template classes are not instantiated until they are needed - that is not until the Edge and Vertex declarations in main(). In other words, both the Vertex and Edge classes are complete by the time they are used as template type parameters. Greg [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

Greg Herlihy wrote: > kanze wrote: > > Louis Lavery wrote: > > > 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 > > The Vit and Eit typedefs don't instantiate anything ... This topic came up before and kanze stated the standard is clear that using a component of a template requires instantiation. Though unfortunately he didn't provide a reference to the appropriate sections of the standard. http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/8cc414252702238b > The std::list template classes are not instantiated until > they are needed - that is not until the Edge and Vertex > declarations in main(). In other words, both the Vertex > and Edge classes are complete by the time they are used as > template type parameters. Your argument is circular. The declarations of Edge and Vertex require instantiation of list. Instantiation of list requires /complete/ declaration of Edge and Vertex. But Edge and Vertex cannot be completed until list is instantiated. But list cannot be instantiated until ... -- Keith -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

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! ]

Greg Herlihy 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. > The Vit and Eit typedefs don't instantiate anything. That's not what my version of the standard says. Particularly �7.4/4: "A class template specialization is implicitly instantiated if the class type is used in a context that requires a completely-defined object type or if the completeness of the class type affects the semantics of the program; [...]" The compiler cannot know whether std::list<Vertex>::iterator names a type unless it has instantiated the template. And the legality of the program depends on whether it names a type or not. > A typedef simply creates another name for a class (or > typedef). And the compiler needs to know a certain number of things about that type. It may be an incomplete type, but it must be known to be a type; in practice, it must also be known whether it is a class type or not, and if it is not a class type, the complete type must be known. > And there is no code or data that needs to be instantiated for > std::list<Edge>::iterator to be called by another name. I can see you've not much experience with C++ compilers, and how they do name mangling. The standard doesn't impose name mangling, of course, but it is an almost universal implementation technique, and the standard doesn't require anything which would make it impossible. Consider the similar case of std::vector<SomeType>::iterator. In some implementations, this is a typedef to SomeType*; in others, it is a typedef to a class type, or a nested class. All three possibilities mangle differently, at least with all C++ compilers I've used. > The std::list template classes are not instantiated until they > are needed - that is not until the Edge and Vertex > declarations in main(). They're needed anytime you write std::list<SomeType>::whatever. The compiler must know what whatever is, particularly, whether it is a type or not, in order to parse the program. > In other words, both the Vertex and Edge classes are complete > by the time they are used as template type parameters. Maybe in some other language, but not in C++. -- 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! ]

Similiar Articles:

Dos and don'ts in C++ unit testing? - comp.lang.c++.moderated ...
Interfaces were introduced to reduce coupling and avoid cyclic dependencies. The work proceeded smoothly and at all times there was a working component that could have ...

Sampling: What Nyquist Didn't Say, and What to Do About It - comp ...
> >You're taking advantage of the fact that the signal you're acquiring is >very cyclic in character. So (for instance), instead of taking samples >every 1/600 seconds ...

cyclic dependency (Beginning Java forum at JavaRanch)
Hi, I'm trying to get a few classes to call each other's methods. It's been driving me nuts for a while and eventually I read that this was a cyclic

Cyclic dependency (OO, Patterns, UML and Refactoring forum at ...
Hi All, What is cyclic redundancy and how that can be solved??? Thanks, kundan [ February 25, 2006: Message edited by: kundan varma ]

7/17/2012 12:01:17 PM