C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Iterators and containers STL          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Merlin Guest Posted: Wed Apr 28, 2004 9:34 am    Post subject: Iterators and containers STL Hi, I am a C++ developer and would like to implement container classes for various types of objects. I use MS Visual C++ to compile my code. Nevertheless I like to write code that is independent from MFC and intentionally I am trying to avoid inheriting from CList and CArray classes. Recently, I became familiar with iterators and have read many articles including the GOF description on what they help to achieve. My understanding so far has led me to believe to the following A) Client has to declare the container, populate it and THEN instatiate the iterator by passing the container as an argument. This approach does not require deleting the iterator object as it is declared on the stack (local). However, the client must know the type of the container class (whether it is a List, etc) B)polymorphic iterators use the factory method to create the iterator when the client requests it. This apporach will require the client to delete the iterator at some stage. The second approach suggests that the container provides only 1 method to create an iterator... What happens if we like to have a forward iterator and a backward iterator for a container that uses the B approach above... does this mean we will have 2 methods in its interface, eg CreateForwardIterator() and CreateBackwardIterator()? The problem with deletion can be resolved with a proxy pattern but can this be inefficient in any way? The GOF book suggests an interface for the iterator which is textual. Should I use that interface or adopt the style where one uses pointer operators? Now lets say the above questions are answered and I have decided on which iterator (A or B) to use and established its interface. What will my container class inherit from? Will it inherit from an appropriate STL container class? If so doesnt this mean that I dont need to implement any iterator classes as STL already supports iterators for its containers. If I did inherit from a container class in STL would anyone see the benefits of wrapping up the STL iterators in my own classes. Obviously I could just write my container classes from scratch but that wouldnt be taking advantage of code reuse. Can I implement the iterator pattern and use STL at the same time... I hope I have made sense.... Many Thanks Merlin [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Philipp Bachmann Guest Posted: Wed Apr 28, 2004 7:53 pm    Post subject: Re: Iterators and containers STL Quote: Recently, I became familiar with iterators and have read many articles including the GOF description on what they help to achieve. My understanding so far has led me to believe to the following The implemetation within GOF of the "iterator" pattern slightly differs from what STL does. E.g. GOF adds a member function "Iterator<>::IsDone()", which renders their "iterators" more like the Java "Enumeration" pattern, which is strongly related. Another difference is, that GOF discusses run time polymorphism (i.e. (pure) virtual functions, abstract base classes), which isn't necessary with STL, because the latter is designed using compile time polymorphism (i.e. templates). Quote: A) Client has to declare the container, populate it and THEN instatiate the iterator by passing the container as an argument. This approach does not require deleting the iterator object as it is declared on the stack (local). However, the client must know the type of the container class (whether it is a List, etc) B)polymorphic iterators use the factory method to create the iterator when the client requests it. This apporach will require the client to delete the iterator at some stage. C) Do it as STL does it: Let the container return (not "create" in the sense of a factory pattern) your iterator. Doing this means of course, that the iterator can be constructed with a pointer or reference to the container instance, but this constructor doesn't need to be "public", given that the container is a "friend" of its iterator. Quote: The second approach suggests that the container provides only 1 method to create an iterator... What happens if we like to have a forward iterator and a backward iterator for a container that uses the B approach above... does this mean we will have 2 methods in its interface, eg CreateForwardIterator() and CreateBackwardIterator()? The problem with deletion can be resolved with a proxy pattern but can this be inefficient in any way? If you really need polymorphic iterators, I'd go for a proxy because of two reasons: - They behave like STL iterators, so you and your collegues are used to them, - you can better avoid memory leaks. Because deletion only happens once, whereas access to the data the iterator refers to potentially happens as often as you've elements within your container, deletion shouldn't be the bottleneck. If the member functions of your proxy are declared "inline", then even the indirection shouldn't cause much trouble. But honestly answering your question would require a test case and a profiler... Quote: The GOF book suggests an interface for the iterator which is textual. Should I use that interface or adopt the style where one uses pointer operators? As said above, I'd design my iterators similar to the STL ones, not to the GOF ones. This holds even for the case, that you want to go for runtime polymorphism. Quote: Now lets say the above questions are answered and I have decided on which iterator (A or B) to use and established its interface. What will my container class inherit from? Will it inherit from an appropriate STL container class? If so doesnt this mean that I dont need to implement any iterator classes as STL already supports iterators for its containers. If I did inherit from a container class in STL would anyone see the benefits of wrapping up the STL iterators in my own classes. STL containers are not base classes. So better don't derive from them. Better use aggregation. Quote: Can I implement the iterator pattern and use STL at the same time... Because the STL is somehow built around the iterator pattern as its central design concept, STL and iterators don't contradict by any means. Cheers, Philipp. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Fri Apr 30, 2004 9:01 am    Post subject: Re: Iterators and containers STL [email]merlin2769 (AT) hotmail (DOT) com[/email] (Merlin) wrote in message news:<12235816.0404271239.fdc45b3 (AT) posting (DOT) google.com>... Quote: I am a C++ developer and would like to implement container classes for various types of objects. I use MS Visual C++ to compile my code. Nevertheless I like to write code that is independent from MFC and intentionally I am trying to avoid inheriting from CList and CArray classes. Recently, I became familiar with iterators and have read many articles including the GOF description on what they help to achieve. Attention: in C++, when you speak of iterators, most people immediately imagine the iterators defined in the standard library. Which aren't iterators in the classical sense, but are more like a special type of smart pointer, which makes the internal structure of the container look like a flat array in memory. If you want to understand what most C++ programmers understand by iterators, you should look at the standard library. If you want to see a quality library which uses GoF-like iterators, you might try the OSE library ([url]http://ose.sourceforge.net/)[/url]. Quote: My understanding so far has led me to believe to the following A) Client has to declare the container, populate it and THEN instatiate the iterator by passing the container as an argument. This approach does not require deleting the iterator object as it is declared on the stack (local). However, the client must know the type of the container class (whether it is a List, etc) At some point, someone must know the type of the container. I experimented some with polymorphic containers when I started C++. In my experience, they aren't generally worth the bother -- you almost always have a single type, which is known at compile time, so the polymorphic interface is additional cost for almost nothing. That is, of course, my experience, and others may have different experiences. Never the less, since most libraries do not provide polymorphic containers, there doesn't seem to be a great demand for them. Quote: B)polymorphic iterators use the factory method to create the iterator when the client requests it. This apporach will require the client to delete the iterator at some stage. The second approach suggests that the container provides only 1 method to create an iterator... What happens if we like to have a forward iterator and a backward iterator for a container that uses the B approach above... does this mean we will have 2 methods in its interface, eg CreateForwardIterator() and CreateBackwardIterator()? Anytime you want several different types of iterators over the same container, you either need different functions, or a parameter to the function. If the iterators are to be polymorphic; as with containers, I've not found a great need for this. If you are using value semantics for the iterators, then you only need different types. Quote: The problem with deletion can be resolved with a proxy pattern but can this be inefficient in any way? It can definitly be inefficient:-). It can be relatively efficient if implemented carefully, but if real efficiency is a concern, the iterators should have value semantics. The OSE mentionned above uses a handle idiom (which is what I think you mean by proxy -- it's not quite the same thing, though); because it gives iterators reference semantics, it is actually relatively efficient, although Dereferencing requires a virtual function, which can cost if it is used in tight loops. My own solution had gradually evolved to fully value oriented iterators, with normal copy semantics. No polymorphism, but extremely efficient. And I usually offer the user the choice: the iterator has a constructor which takes a container, but the container also has a function which returns an iterator. (As I update such code, I am gradually adding STL compatibility to these iterators, so that they can be used both as a traditional iterator, and as an STL iterator.) There is one exception to this rule. When parsing, I will often use something that I call a ParseContext, which in fact is also a sort of an iterator. Unlike the other iterators, it is designed to be polymorphic, and use reference semantics. Once you've extracted a token in a function, you don't want to see it again in the calling function. And it is useful to be able to parse directly from strings or from a file. And finally, since the type I'm iterating over is a character type, I generally use a sentinal value to signal the end, rather than a separate function. In all, it is more like a simplified streambuf, without the buffering, and with more logical names for the functions (peek and get), than anything else. (But when you think about it, streambuf is also a type of iterator.) Quote: The GOF book suggests an interface for the iterator which is textual. Should I use that interface or adopt the style where one uses pointer operators? I'm not sure what you mean by "textual". Logically, an iterator (what computer scientists have traditionally considered an iterator) has three functions: next(), isDone() and value(). Some variation is to be expected: advance() instead of next(), etc. The iterators in the standard library are a bit different -- they consciously emulate pointers. In such cases, operator overloading is to be expected. But IMHO, any use of it with a classical iterator would be flagrant abuse. And what operator would you overload for isDone()? (I once saw unary + used for this:-(.) Quote: Now lets say the above questions are answered and I have decided on which iterator (A or B) to use and established its interface. What will my container class inherit from? Not necessarily anything. Quote: Will it inherit from an appropriate STL container class? Definitly not. It has nothing to do with the STL containers. (It could, of course, use a standard container in its implementation.) Quote: If so doesnt this mean that I dont need to implement any iterator classes as STL already supports iterators for its containers. What the standard library calls iterators have nothing to do with what you are describing. If you want something like classical iterators, you can implement them (rather trivially) using the STL iterators. Quote: If I did inherit from a container class in STL would anyone see the benefits of wrapping up the STL iterators in my own classes. Obviously I could just write my container classes from scratch but that wouldnt be taking advantage of code reuse. Can I implement the iterator pattern and use STL at the same time... The STL provides a low level implementation, which can definitly be used. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr 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! ] Back to top kanze@gabi-soft.fr Guest Posted: Fri Apr 30, 2004 9:17 am    Post subject: Re: Iterators and containers STL ""Philipp Bachmann" <"reverse email address"" Quote: Recently, I became familiar with iterators and have read many articles including the GOF description on what they help to achieve. My understanding so far has led me to believe to the following The implemetation within GOF of the "iterator" pattern slightly differs from what STL does. What the STL does has very little, if anything to do with the "iterator" pattern in GoF. Quote: E.g. GOF adds a member function "Iterator<>::IsDone()", which renders their "iterators" more like the Java "Enumeration" pattern, which is strongly related. This is what was traditionally meant by "iterator" before the STL, and is still what anyone working in the field and not using C++ would understand by the term. Quote: Another difference is, that GOF discusses run time polymorphism (i.e. (pure) virtual functions, abstract base classes), which isn't necessary with STL, because the latter is designed using compile time polymorphism (i.e. templates). In use, at the application level, the STL iterators are not polymorphic. They are only polymorphic within a template function. IMHO, this is not a problem; while I code in a very OO style, I've still never needed polymorphism on containers or iterators. It's one case where dynamic polymorphism doesn't seem to buy that much. Quote: A) Client has to declare the container, populate it and THEN instatiate the iterator by passing the container as an argument. This approach does not require deleting the iterator object as it is declared on the stack (local). However, the client must know the type of the container class (whether it is a List, etc) B)polymorphic iterators use the factory method to create the iterator when the client requests it. This apporach will require the client to delete the iterator at some stage. C) Do it as STL does it: Let the container return (not "create" in the sense of a factory pattern) your iterator. Doing this means of course, that the iterator can be constructed with a pointer or reference to the container instance, but this constructor doesn't need to be "public", given that the container is a "friend" of its iterator. The STL probably does it only this way because you need two iterators, which differ only in value, and not in type. The alternative is used with io iterators -- you don't call a member function of istream to get an istream_iterator. But the result requires a special end iterator, and would result in less efficiency for things like vector::iterator. I guess you could say that the standard library is incoherent in this respect. It's true that: std::vector< int > v( std::cin.begin< int >(), std::cin.end< int >() ) ; would not suffer from a certain well known parser problem:-). (And it looks a lot more like the use of iterators over other sequences.) My own solution with value oriented iterators has always been to allow both for ( Container::Iterator iter( container ) ; ! iter.isDone() ; iter.next() ) and for ( Container::Iterator iter = container.iterator() ; ! iter.isDone() ; iter.next() ) The advantage of a polymorphic solution is that only the container knows about its private iterator type. But it means that the iterator must be created by the container. The equivalent in OSE would be: for ( OTC_Iterator<int> iter = container.items() ; ! iter.isValid() ; iter.next() ) Quote: The second approach suggests that the container provides only 1 method to create an iterator... What happens if we like to have a forward iterator and a backward iterator for a container that uses the B approach above... does this mean we will have 2 methods in its interface, eg CreateForwardIterator() and CreateBackwardIterator()? The problem with deletion can be resolved with a proxy pattern but can this be inefficient in any way? If you really need polymorphic iterators, I'd go for a proxy because of two reasons: - They behave like STL iterators, so you and your collegues are used to them, Making a polymorphic STL compatible iterator is far from trivial. In fact, what I did was first made a polymorphic GoF iterator, and then designed an adapter for it (integrated into the base class), to implement the STL interface. Again, the problem is the two iterator idiom. Operator overloading and virtual functions doesn't work that well together to begin with, and it doesn't work well at all for binary operators. I used Copliens letter/envelope idiom to give the iterator value semantics. With deep copy, since that is what the STL requires. It works, but it is *very* expensive in terms of run-time. And as I said before, I've not found dynamic polymorphism to be that useful for iterators and containers. Quote: - you can better avoid memory leaks. Because deletion only happens once, whereas access to the data the iterator refers to potentially happens as often as you've elements within your container, deletion shouldn't be the bottleneck. If the member functions of your proxy are declared "inline", then even the indirection shouldn't cause much trouble. But honestly answering your question would require a test case and a profiler... If you really want to support STL, your iterator needs full value semantics. Which means a deep copy -- including dynamic allocation -- on assignment. Given the way the STL algorithms are designed, it IS expensive. How expensive, of course, depends on the algorithm and the actual implementation. Quote: The GOF book suggests an interface for the iterator which is textual. Should I use that interface or adopt the style where one uses pointer operators? As said above, I'd design my iterators similar to the STL ones, not to the GOF ones. This holds even for the case, that you want to go for runtime polymorphism. If runtime polymorphism is important, and you have a choice, I'd go for the classical iterator idiom. From personal experience. The key is, if you have a choice: regardless of any strictly technical merits or demerits, the standard iterators have two enormous advantages: 1. Any experienced C++ is familiar with them. If I see code with a object whose type is named Iterator, with member functions isDone(), next(), and value(), I can make a pretty good guess about its semantics. But I still have to go back to the header file and the documentation to be sure. When I see a nested type iterator, initialized with a member function begin(), compared with the results of a member function end(), and otherwise treated like a limited pointer, I KNOW what is going on (unless I have a particularly perverse author). I don't have to look any farther. So unless your project explicitly defines something else in its guidelines (in which case, everybody working on the project will know what it is), you need a very strong set of advantages to justify using another idiom. About the only cases I've found this to be true to date have been when parsing, in which case I've defined a ParsingContext (which is a sort of a GoF iterator, generally polymorphic, with reference semantics, signaling the end by means of a sentinal, and usually also maintaining various other odd information, like line number and file name). 2. It's what other software will expect. If you want to use any of the standard algorithms (and one or two of them are occasionnally useful), you need an STL compatible iterator. And one would expect newer third party libraries to require them as well. Quote: Now lets say the above questions are answered and I have decided on which iterator (A or B) to use and established its interface. What will my container class inherit from? Will it inherit from an appropriate STL container class? If so doesnt this mean that I dont need to implement any iterator classes as STL already supports iterators for its containers. If I did inherit from a container class in STL would anyone see the benefits of wrapping up the STL iterators in my own classes. STL containers are not base classes. So better don't derive from them. Better use aggregation. Can I implement the iterator pattern and use STL at the same time... Because the STL is somehow built around the iterator pattern as its central design concept, STL and iterators don't contradict by any means. The STL is built around ITS iterator concept. Which is a bit different from what is commonly called an iterator otherwise. And for what it's worth, it is possible to implement iterators compatible with both STL and the GoF pattern. In my case, I've done so as a transition measure -- adding the STL compatible interface didn't break any existing code which used the pre-standard iterface. For new work, I rather doubt that the effort is worth it. Most of the time, just about any iterator idiom is good enough, and in the absence of any overwhelming technical constraints, points 1 and 2, above, reign. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr 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! ] Back to top John Potter Guest Posted: Sat May 01, 2004 2:54 am    Post subject: Re: Iterators and containers STL On 30 Apr 2004 05:01:33 -0400, [email]kanze (AT) gabi-soft (DOT) fr[/email] wrote: Quote: I'm not sure what you mean by "textual". Logically, an iterator (what computer scientists have traditionally considered an iterator) has three functions: next(), isDone() and value(). Some variation is to be expected: advance() instead of next(), etc. isValid instead of ! isDone is positive thinking. Quote: The iterators in the standard library are a bit different -- they consciously emulate pointers. In such cases, operator overloading is to be expected. But IMHO, any use of it with a classical iterator would be flagrant abuse. And what operator would you overload for isDone()? (I once saw unary + used for this:-(.) operator void const volatile * is the obvious choice. for (init(it); ! it.isDone(); it.next()) use(it.value()); for (init(it); it.isValid(); it.next()) use(it.value()); for (init(it); it; ++ it) use(*it); For those who like negative thinking, also provide operator !. for (init(it); ! ! it; ++ it) use(*it); John [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Mon May 03, 2004 9:53 am    Post subject: Re: Iterators and containers STL John Potter <jpotter (AT) falcon (DOT) lhup.edu> wrote Quote: On 30 Apr 2004 05:01:33 -0400, [email]kanze (AT) gabi-soft (DOT) fr[/email] wrote: I'm not sure what you mean by "textual". Logically, an iterator (what computer scientists have traditionally considered an iterator) has three functions: next(), isDone() and value(). Some variation is to be expected: advance() instead of next(), etc. isValid instead of ! isDone is positive thinking. But it says something different. In my case, my iterators allowed removal of the element under the iterator, without moving the iterator. So the iterator could be invalide without the iteration being done. And I supported both functions, with different semantics. But it's not a big point. Quote: The iterators in the standard library are a bit different -- they consciously emulate pointers. In such cases, operator overloading is to be expected. But IMHO, any use of it with a classical iterator would be flagrant abuse. And what operator would you overload for isDone()? (I once saw unary + used for this:-(.) operator void const volatile * is the obvious choice. One might think so. Personally, I like to say what I mean and mean what I say. So I tend to eschew abusing operator overloading. I'm also very, very sceptical about implicit conversion operators -- somehow or other, they always seem to come back and bite you. But if you insist on abusing operators for this, yes, that would seem to be the obvious choice. Quote: for (init(it); ! it.isDone(); it.next()) use(it.value()); for (init(it); it.isValid(); it.next()) use(it.value()); for (init(it); it; ++ it) use(*it); For those who like negative thinking, also provide operator !. for (init(it); ! ! it; ++ it) use(*it); IMHO, *if* you provide the conversion operator, as a pseudo conversion to bool, you should also provide !. Orthogonality reigns. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr 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! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.