dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 34

Thread: STL Forward declarations and iterators

  1. #1
    Join Date
    May 2008
    Posts
    8

    STL Forward declarations and iterators

    Hi,

    I just ported a big project that makes extensive use of the STL from Builder 6 to CodeGear Studio 2007. B6 has the Rogue Wave STL implementation, whereas CG2007 has the Dinkumware implementation.

    I have a problem with a forward declaration of a class. My project is quite complex, but I have replicated the error in a simple code snippet:

    [code]
    #include<list>

    class A;

    class B{
    public:
    int ID;
    std::list<A>::iterator iA;

    B() {ID=0;}
    B(int id) {ID=id;}
    B(const B &b) {*this=b;}
    };

    class A{
    public:
    int ID;

    A() {ID=0;}
    A(int id) {ID=id;}
    A(const A &a) {*this=a;}
    };
    [\code]

    Before you ask why I am forward declaring the A class, let me repeat that this is just a toy example where I get the same error as in a bigger project where complex inter-class links exist that require forward declarations as above.

    The thing is: The code above compiles without any problems in B6 (Rogue Wave) but in CG2007 (Dinkumware) the STL "list" source file opens and the compiler signals error: Undefined structure "A".

    Of course, if I move the A definition above B, it compiles. All the same, if in B instead of an iterator, I declare iA as a pointer A *iA, it compiles, but that is not what I want, I want a member of B to be an iterator of a list of A's, not a pointer to A.

    What is happening here? Shouldn't iterators be treated as pointers? Forward declaration of classes is allowed for pointers. Perhaps the Dinkumware implementation does not allow iterators and forward declarations? or perhaps am I missing some compiler directive in Code Gear 2007?

    I decided to use the STL in this big project because it is supposed to give portability and standardization. But this is not what I'd call portable...

    Any hints appreciated.
    Last edited by JB0; May 28th, 2008 at 03:51 AM. Reason: Added [code] tags

  2. #2
    Join Date
    Aug 2005
    Location
    LI, NY
    Posts
    576

    Re: STL Forward declarations and iterators

    It really depends on how std::list is implemented. I can't say exactly why it does or does not work, but it just isn't portable to rely on the ability to provide a forward-declared type to a standard template.

    There is a way around this problem, however, and that is to use the Pimpl idiom. In a nutshell, it goes like this:

    B.h
    Code:
    class B
    {
    public:
    	B();
    	B(const B &);
    	~B();
    	B & operator=(const B &);
    
    private:
    	class impl;
    
    	impl * m_pimpl;
    };
    B.cpp
    Code:
    #include "B.h"
    #include "A.h"
    #include <list>
    
    class B::impl
    {
    public:
    	std::list<A>::iterator iA;
    };
    
    B::B()
    {
    	m_pimpl = new impl;
    }
    B::B(const B & rhs)
    {
    	m_pimpl = new impl(*rhs.m_pimpl);
    }
    B::~B()
    {
    	delete m_pimpl;
    }
    B & B::operator=(const B & rhs)
    {
    	*m_pimpl = *rhs.m_pimpl;
    	return *this;
    }
    This pattern allows you to greatly reduce the interdependence of class declarations.


    PS: Use [code][/code] tags next time.
    Last edited by Hermit; May 27th, 2008 at 02:29 PM.
    - Alon

  3. #3
    Join Date
    Apr 1999
    Posts
    27,449

    Re: STL Forward declarations and iterators

    Quote Originally Posted by JB0
    Before you ask why I am forward declaring the A class, let me repeat that this is just a toy example where I get the same error as in a bigger project where complex inter-class links exist that require forward declarations as above.
    This has nothing to do with STL, and everything to do with assuming that templates will use forward-declared classes within itself.
    The thing is: The code above compiles without any problems in B6 (Rogue Wave) but in CG2007 (Dinkumware) the STL "list" source file opens and the compiler signals error: Undefined structure "A".
    As Hermit mentioned, unless you came up with the template yourself, you can't rely on forward-declared classes.

    As a matter of fact, unless you came up with 100% of the code that uses the forward-declared class, your code that compiled (by chance), is not guaranteed to compile somewhere else. It isn't even guaranteed to compile on another (maybe newer) version of Rogue Wave.
    What is happening here? Shouldn't iterators be treated as pointers?
    No. Iterators are not pointers. Pointers are iterators.

    There is no specification as to how iterators for std::list are implemented. As a matter of fact, there is a similar situation with Visual C++. For Visual C++ 6.0, iterators (at least vector iterators) were implemented as pointers, so programmers started to use the iterators as if they were pointers. Then along comes Visual Studio 2003. Guess what? MS implemented iterators using a struct. Now all of that code that compiled in Visual C++ 6.0 now fails to compile. The programmer's who wrote all of that code have no recourse to complain to Microsoft, since nowhere in the C++ specification does it say how vector iterators are implemented.
    Perhaps the Dinkumware implementation does not allow iterators and forward declarations? or perhaps am I missing some compiler directive in Code Gear 2007?
    Nope. Again, iterators are *not* pointers, even if some implementation just happens to implement list iterators using pointers. That is an implementation detail that you should never had assumed. Iterators are concepts, i.e. the only thing you know about an iterator is how it behaves. For example, for a forward iterator, you know that applying operator ++ advances you to the next item. How it does it is something you shouldn't rely on.
    I decided to use the STL in this big project because it is supposed to give portability and standardization. But this is not what I'd call portable...
    It is portable if you understand the rules of the game. Also, as mentioned before, it isn't a problem with STL -- any code that uses a forward declared class is highly susceptible of not compiling, unless you provided all of the code that uses the class.

    Regards,

    Paul McKenzie

  4. #4
    Join Date
    Apr 2004
    Location
    England, Europe
    Posts
    2,492

    Re: STL Forward declarations and iterators

    Just to explain what might be going on, so you can see why this might be happening ...

    This works with a forward declared class T:
    Code:
    template <class T>
    struct Node
    {
        Node<T>* previous;
        Node<T>* next;
        T*       data; // Do not need to know size of T right away.
    };
    This does not:
    Code:
    template <class T>
    struct Node
    {
        Node<T>* previous;
        Node<T>* next;
        T        data; // Have got to know size of T right away.
    };
    The first example works with forward declared classes, but the second might have better memory allocation performance.

    As others have noted, the STL can be implemented in many different ways.
    Last edited by Zaccheus; May 28th, 2008 at 03:45 AM.
    My hobby projects:
    www.rclsoftware.org.uk

  5. #5
    Join Date
    May 2008
    Posts
    8

    Re: STL Forward declarations and iterators

    Thank you for your replies. I see the point.

    Just a few comments: I did not say that iterators were pointers, or that I used iterators as pointers. I am aware that iterators are not pointers. But it was precisely the iterator "concept", in Paul's words, that led me to believe that iterators should accept forward declarations, as pointers do (my question "Shouldn't iterators be treated as pointers?" was "conceptual", not procedural). I do not see why anybody should implement iterators such that they need to know the element size at declaration time. Zaccheus' example is perfectly clear, and indeed, after checking the code in the two implementations of list, that's (simplified) what's happening. Not that RogueWave used a simple pointer to implement list iterators, but that they were smart enough as to not require the member itself (only base types) for the definition of iterators. Or, in other words, that Dinkumware people were not careful enough as to avoid this (in my view) unnecessary drawback of their iterators.

    Perhaps assuming that I could use forward declaration with STL iterators was na´ve on my part, but I do not think it can be compared to violating the philosophy of the STL, such as trying to sum an integer to an iterator, or fiddling with the inner members of any STL components. My conclusion is the following: If something as simple and straightforward as a forward declaration causes this trouble when porting from one implementation of the STL to another, the STL is not the right choice for me. Yes, if I'd (attentively) read the whole STL and C++ specifications I could probably (or not) be able to infer that forward declarations were not safe with iterators, but then, what else assumptions may I be making that will not hold in future implementations, just because they are not "specified"? I am using preincrements because of efficiency. Will this hold in any implementation? List iterators are preserved after insertions, is this specified or just a matter of "chance" (local to the implementation)? Sorry, this either makes the STL too uncertain as for portability, or poses too much overhead on the programmer. Call me lazy, but I do not want to make a PhD in STL programming, I only want to use it. I cannot afford checking the ISO specification everytime I want to write something beyond a=NULL;

    Either the cost in uncertainty or in mastering the specification (what is written and what is not written), and the restrictions derived, do not rival the cost of programming my own set of lists, sets, and vectors. So farewell STL.

  6. #6
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,762

    Re: STL Forward declarations and iterators

    I am using preincrements because of efficiency. Will this hold in any implementation? List iterators are preserved after insertions, is this specified or just a matter of "chance" (local to the implementation)? Sorry, this either makes the STL too uncertain as for portability, or poses too much overhead on the programmer. Call me lazy, but I do not want to make a PhD in STL programming, I only want to use it. I cannot afford checking the ISO specification everytime I want to write something beyond a=NULL;
    However, this is an inherent problem in using any external library: you need to know what are the published pre-conditions, post-conditions, and limitations of the interface. What you are saying amounts to: "I'd rather re-invent the wheel than learn the highway code".
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  7. #7
    Join Date
    Apr 1999
    Posts
    27,449

    Re: STL Forward declarations and iterators

    Quote Originally Posted by JB0
    Yes, if I'd (attentively) read the whole STL and C++ specifications I could probably (or not) be able to infer that forward declarations were not safe with iterators, but then, what else assumptions may I be making that will not hold in future implementations, just because they are not "specified"?
    This needs to be known by any programmer using any library. Also, it isn't only STL, but any part of C++ has specified and unspecified behaviour. The C++ specification is full of "undefined behaviour" and "implementation defined" behaviour paragraphs.
    I cannot afford checking the ISO specification everytime I want to write something beyond a=NULL;
    What you should be checking the ISO standard for is anything that you feel is suspicious. Any use of a forward declaration in a template, at least to me and to others, is a sign that things may not work in the future or on another compiler. Since a forward declared class has no real "body", assuming that when a template is expanded that all things should work, is a very bad assumption.

    The only thing guaranteed are those specified by ISO. One of the big ones is never assume the underlying implementation of any class, unless the standard specifically states what the underlying implementation is. For example, it is in the standard that vectors must use contiguous memory to store the data.

    Most, if not all good C++ programmers have the spec ready, in case there are any questions as to if a piece of code is valid or produces predictable behaviour. Saying that that "the compiler must have implemented it this way, so I'll write the code this way" is one of the worst things that can bite you if you're going to port to another C++ compiler. The thing that is even worse is given the false sense of security that the code compiled. This is a reason why many have multiple compilers, and sometimes go to the online compiler at Comeau Computing, so as to test anything that may have compiled, but gives any hint of suspicion.
    Either the cost in uncertainty or in mastering the specification (what is written and what is not written), and the restrictions derived, do not rival the cost of programming my own set of lists, sets, and vectors. So farewell STL.
    It's unfortunate that you based your code on what turns out to be unspecified or implementation-defined behaviour.

    But what about all of those other parts of C++ that you may be using that is not specified by the language or will produce undefined/implementation-defined behaviour? You singled out STL, but that is the nature of the whole language. There are things that compile fine and work for some compiler which will not work for another compiler, STL or no STL. This is why peer-review by other C++ programmers is important.

    And BTW, here are the errors when I take your code and compile it using the Comeau on-line compiler (one of the most ANSI C++ compliant compilers available).
    Code:
    Thank you for testing your code with Comeau C/C++!
    Tell others about http://www.comeaucomputing.com/tryitout ! 
    
    Your Comeau C/C++ test results are as follows: 
    
    
    Comeau C/C++ 4.3.10.1 (May  7 2008 20:26:48) for ONLINE_EVALUATION_BETA1
    Copyright 1988-2008 Comeau Computing.  All rights reserved.
    MODE:strict errors C++ C++0x_extensions
    
    "concept_checks.h", line 555: error: incomplete type is not allowed
        static void _Assignable_requirement_violation(_Type __a) {
                                                      ^
              detected during instantiation of "void
                        _Assignable_concept_specification<_Type>::_Assignable_requi
                        rement_violation(_Type) [with _Type=A]" at line 13 of
                        "ComeauTest.c"
    
    "concept_checks.h", line 392: warning: returning pointer to local variable
          return __a;
                 ^
              detected during:
                instantiation of "_Type
                          _STL_ERROR::__assignment_operator_requirement_violation(_
                          Type) [with _Type=<error-type>]" at line 556
                instantiation of "void
                          _Assignable_concept_specification<_Type>::_Assignable_req
                          uirement_violation(_Type) [with _Type=A]" at line 13 of
                          "ComeauTest.c"
    
    "concept_checks.h", line 398: warning: returning pointer to local variable
          return __c;
                 ^
              detected during:
                instantiation of "_Type
                          _STL_ERROR::__copy_constructor_requirement_violation(_Typ
                          e) [with _Type=<error-type>]" at line 557
                instantiation of "void
                          _Assignable_concept_specification<_Type>::_Assignable_req
                          uirement_violation(_Type) [with _Type=A]" at line 13 of
                          "ComeauTest.c"
    
    "concept_checks.h", line 405: warning: returning pointer to local variable
          return __c;
                 ^
              detected during:
                instantiation of "_Type
                          _STL_ERROR::__const_parameter_required_for_copy_construct
                          or(_Type, const _Type &) [with _Type=<error-type>]" at
                          line 558
                instantiation of "void
                          _Assignable_concept_specification<_Type>::_Assignable_req
                          uirement_violation(_Type) [with _Type=A]" at line 13 of
                          "ComeauTest.c"
    
    "concept_checks.h", line 412: warning: returning pointer to local variable
          return __a;
                 ^
              detected during:
                instantiation of "_Type
                          _STL_ERROR::__const_parameter_required_for_assignment_ope
                          rator(_Type, const _Type &) [with _Type=<error-type>]"
                          at line 559
                instantiation of "void
                          _Assignable_concept_specification<_Type>::_Assignable_req
                          uirement_violation(_Type) [with _Type=A]" at line 13 of
                          "ComeauTest.c"
    
    1 error detected in the compilation of "ComeauTest.c".
    
    In strict mode, with -tused, Compile failed
    So it looks like RogueWave was the "fool's gold".

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; May 28th, 2008 at 08:57 AM.

  8. #8
    Join Date
    Apr 1999
    Location
    Altrincham, England
    Posts
    4,470

    Re: STL Forward declarations and iterators

    Quote Originally Posted by JB0
    [...] that led me to believe that iterators should accept forward declarations, as pointers do (my question "Shouldn't iterators be treated as pointers?" was "conceptual", not procedural). I do not see why anybody should implement iterators such that they need to know the element size at declaration time. [...]
    It's not the implementation of the iterator that requires the full class definition, it's the container from which you obtain the iterator that needs it.

    If you had:
    Code:
    class A;
    
    class B
    {
    std::list<A> a_list;
    };
    You wouldn't (or , at least, shouldn't) expect that to compile. So, neither should you really expect it to compile if you just stick a "::iterator" on the end.
    Correct is better than fast. Simple is better than complex. Clear is better than cute. Safe is better than insecure.
    --
    Sutter and Alexandrescu, C++ Coding Standards

    Programs must be written for people to read, and only incidentally for machines to execute.

    --
    Harold Abelson and Gerald Jay Sussman

    The cheapest, fastest and most reliable components of a computer system are those that aren't there.
    -- Gordon Bell


  9. #9
    Join Date
    May 2008
    Posts
    8

    Re: STL Forward declarations and iterators

    Paul, ain't you mixing things here? I don't see the point of the Comeau's dump. It seems quite clear that my problem is not a compiler compatibility issue, but a library implementation issue. More specifically, the differences among different implementations of the same "standard" library. The fact that Comeau's doesn't compile "my code" tells me little: What STL implementation does Comeau's compiler use? Perhaps Comeau's dump is from trying to compile "my code" with the Rogue Wave STL?

    I accept all the generic fuss about knowing the specs and the philosophy and the risk in risky assumptions and how naughty dirt code tricks are. Yes, all that is very nice and quite commonsensical. But my problem here, or the source of my problem here is that I assumed that iterators would be compatible with forward class declarations. Is there in the C++ spec anywhere a explicit warning that iterators are not compatible with forward declarations? Not, that I know. Is there in the C++ spec a warning about "undefined behaviour" or "implementation defined" with regard to forward declarations and iterators? Not, that I know. Should I have guessed it, because the specification does not literally says that iterators are compatible with forward declarations? I don't think so. Otherwise, there are quite a few things we do that we'd never do, because the specification does not specify everything. Does this mean then that I assume that "when a template is expanded all things should work"? Not, of course not. I may not be a "good C++ programmer", but I'm not a fool either (even if seemingly fooled by the "fool's gold" of Rogue Wave...). I thought, and still think, that compatibility of iterators with forward declarations, templates or not templates, is not such a crazy idea, taking into account what an iterator is and what is it for.

    If I translate your considerations about good C++ programmers and testing multiple compilers, then this means that, to use the STL safely, I should test my code on several implmentations of the STL... This just supports my conclusion that the STL is not a solution for me. A real pity, I like the "concept" very much, but I don't like the uncertainty in the implementations. My fault? Maybe. As a programmer, I'm a customer of libraries, compilers, and languages. As a customer, I select what I think is more suitable for me. Cost is a part of the "suitability" equation. The overhead you affirm I must accept if I want to have some reasonable degree of certainty when using the STL beyond the trivial is not an acceptable cost for me.

    Graham, thanks, but not, I would not and did not expect that to compile. But I would (I did) expect the iterator-stuck version to compile, and it compiled. And it not only compiled, it also worked. Perhaps the RogueWave guys besides foolers are also wizards? Your point is founded on a OO vision, and the STL is not OO, but "concept" based.

    As for metaphors, rather than the wheel and the highway code, I prefer this: I'd rather walk in my boots than drift on your hot-air balloon.

  10. #10
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,762

    Re: STL Forward declarations and iterators

    But my problem here, or the source of my problem here is that I assumed that iterators would be compatible with forward class declarations. Is there in the C++ spec anywhere a explicit warning that iterators are not compatible with forward declarations?
    I daresay that it comes close:
    Quote Originally Posted by C++ Standard, 2003 Edition, Section 9.2, Paragraph 8
    Non-static members that are class objects shall be objects of previously defined classes. In particular, a class cl shall not contain an object of class cl, but it can contain a pointer or reference to an object of class cl.
    Assuming that you understand that the set of pointers is a proper subset of the set of iterators, it is clear that although a pointer to an object that is not yet defined is allowed to be a member, an iterator to an object that is not yet defined would not be allowed to be a member, unless that iterator is actually a pointer, since iterators are generally class objects.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  11. #11
    Join Date
    Nov 2002
    Location
    Los Angeles, California
    Posts
    3,863

    Re: STL Forward declarations and iterators

    JBO,

    Why don't you just use the STLport implementation of the STL. It is free, far better (in my experience) to Dinkumware's implementation, and will compile the code you are trying to compile.

    Code:
    class BLAH;
    
    class FOO
    {
    	std::list<BLAH>::iterator iBLAH_;
    };
    Wakeup in the morning and kick the day in the teeth!! Or something like that.

    "i don't want to write leak free code or most efficient code, like others traditional (so called expert) coders do."

  12. #12
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: STL Forward declarations and iterators

    I'm actually curious about the differences between various STL implementations. I know EASTL has some actual API differences; but in practical terms, what differences to the others have?

  13. #13
    Join Date
    Apr 2004
    Location
    England, Europe
    Posts
    2,492

    Re: STL Forward declarations and iterators

    Quote Originally Posted by JB0
    But my problem here, or the source of my problem here is that I assumed that iterators would be compatible with forward class declarations.
    I know what you mean.

    I've had plenty of surprises when I found that some things, which I thought would always work, were in fact implementation dependent.

    Sometimes the only realistic way of finding out these kinds of issues is years (if not decades) of experience. It's one of the reasons I read this forum.
    My hobby projects:
    www.rclsoftware.org.uk

  14. #14
    Join Date
    Aug 2002
    Location
    Madrid
    Posts
    4,588

    Re: STL Forward declarations and iterators

    Well, I have found some differences between STL implementations and their inclusion of std::string functions. Some have += char, some don't. However I haven't had any issues with pointer/iterator stuff. The thing is that just working from www.sgi.com/tech/stl gives a pretty OK idea of how it's supposed to work, even though you have to be aware that they have some extensions like the hashed containers.

    In any case, souldog's solution of using STLPort is a good idea. It's portable to pretty much every compilation system, so even if you have to port the code, you'll still have the same version of the library.
    Get this small utility to do basic syntax highlighting in vBulletin forums (like Codeguru) easily.
    Supports C++ and VB out of the box, but can be configured for other languages.

  15. #15
    Join Date
    Apr 1999
    Posts
    27,449

    Re: STL Forward declarations and iterators

    Quote Originally Posted by laserlight
    Assuming that you understand that the set of pointers is a proper subset of the set of iterators, it is clear that although a pointer to an object that is not yet defined is allowed to be a member, an iterator to an object that is not yet defined would not be allowed to be a member, unless that iterator is actually a pointer, since iterators are generally class objects.
    Therefore since iterators are implementation defined, you cannot guarantee that they're pointers (just ask the VC 6.0 programmers who made this mistake when porting their app to Visual Studio 200x).

    It basically boils down to this: A large codebase was written with the false assumption of something being valid in C++ (I'm not going to mention STL, since this can happen with any part of the language). Then when the code is ported, the surprises start when the code either doesn't compile, or runs erratically.

    This story has been repeated many times in many different flavors when it comes to porting difficulties. Memset or memcpy on non-POD types, using delete instead of delete[] for POD types, assuming iterators are pointers, writing to string-literals, assuming the order of initialization of static objects, etc. etc. There is nothing new about it -- it goes with the territory.

    Regards,

    Paul McKenzie

Page 1 of 3 123 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)