C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Shouldn't iterators be ordered?          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message David Turner Guest Posted: Mon Feb 16, 2004 11:14 pm    Post subject: Shouldn't iterators be ordered? Hi Shouldn't it be a requirement on all iterators that they have a strict weak ordering? This is to facilitate things like: typedef std::map<A, B> MapType; typedef std::map<MapType::const_iterator, C> AuxMap; where we have a transitive relationship A -> B -> C. Of course, there is a fundamental problem with using an iterator (of any sort) as a key, which I'll get to later (it's a separate issue). First, here is an alternative formulation: template<typename T> struct iterator_less { bool operator ()(const T& lhs, const T& rhs) { return &*lhs < &*rhs; } }; typedef std::map typedef std::map< MapType::const_iterator, C, iterator_less Quote: AuxMap; Has anybody come up with a better solution than this? The fundamental problem with using iterators as keys is that they are transient, which means there is no way to guarantee this assertion: "The existence of a key in the auxiliary map implies the existence of the same key in the primary map". This is a purely practical problem: it is often necessary to build an auxiliary map without modifying the primary map (separation of concerns). There doesn't seem to be any way to do this safely. One possibility I had thought of was to give iterators locking semantics: iterators could preserve a reference count on the element to which they refer. This would operate as a read/write lock. However, this implies that no const_iterators must be outstanding when one wanted to acquire a non-const iterator. What to do? Throw an exception? To facilitate auxiliary maps, one would also need a weak_const_iterator. Alarm bells are ringing. Regards David Turner [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Tue Feb 17, 2004 11:42 am    Post subject: Re: Shouldn't iterators be ordered? "David Turner" <david (AT) firepro (DOT) co.za> writes: Quote: Hi Shouldn't it be a requirement on all iterators that they have a strict weak ordering? Probably not; what about iterators over non-lvalues (input iterators that are not forward iterators)? Quote: This is to facilitate things like: typedef std::map<A, B> MapType; typedef std::map<MapType::const_iterator, C> AuxMap; where we have a transitive relationship A -> B -> C. Of course, there is a fundamental problem with using an iterator (of any sort) as a key, which I'll get to later (it's a separate issue). First, here is an alternative formulation: template<typename T struct iterator_less { bool operator ()(const T& lhs, const T& rhs) { return &*lhs < &*rhs; } }; That's a good solution for lvalue iterators. Quote: typedef std::map typedef std::map MapType::const_iterator, C, iterator_less AuxMap; Has anybody come up with a better solution than this? The fundamental problem with using iterators as keys is that they are transient, What do you mean by "transient"? Quote: which means there is no way to guarantee this assertion: "The existence of a key in the auxiliary map implies the existence of the same key in the primary map". You need to build a compound object and maintain an invariant. This is basic software design AFAICT, and has nothing in particular to do with iterators. Quote: This is a purely practical problem: it is often necessary to build an auxiliary map without modifying the primary map (separation of concerns). There doesn't seem to be any way to do this safely. One possibility I had thought of was to give iterators locking semantics: iterators could preserve a reference count on the element to which they refer. This would operate as a read/write lock. However, this implies that no const_iterators must be outstanding when one wanted to acquire a non-const iterator. No, writing into an iterator of a standard container doesn't change the address of the element it refers to. Quote: What to do? Throw an exception? To facilitate auxiliary maps, one would also need a weak_const_iterator. Alarm bells are ringing. I think this is simpler than you're making it. HTH, -- Dave Abrahams Boost Consulting www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alexander J. Oss Guest Posted: Tue Feb 17, 2004 2:24 pm    Post subject: Re: Shouldn't iterators be ordered? "David Turner" <david (AT) firepro (DOT) co.za> wrote Quote: Shouldn't it be a requirement on all iterators that they have a strict weak ordering? This is to facilitate things like: typedef std::map<A, B> MapType; typedef std::map<MapType::const_iterator, C> AuxMap; where we have a transitive relationship A -> B -> C. I think for something like this it's not uncommon to include a key value in the second element type of MapType that is used to index AuxMap: struct MapTypeValue { B b; int i; }; typedef std::map<A, MapTypeValue> MapType; typedef std::map<int, C> AuxMap; Of course, this then requires providing your own method to ensure the uniqueness of the MapTypeValue::i values. But this is not difficult. (And depending on how you do it, AuxMap could become AuxVector for improved performance.) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Turner Guest Posted: Tue Feb 17, 2004 5:10 pm    Post subject: Synchronizing auxiliary maps (was: Re: Shouldn't iterators b Hi Quote: Shouldn't it be a requirement on all iterators that they have a strict weak ordering? Probably not; what about iterators over non-lvalues (input iterators that are not forward iterators)? Amend "all" to "lvalue-referencing", or just "referencing" for short. Quote: The fundamental problem with using iterators as keys is that they are transient, What do you mean by "transient"? transient, adj., "passing with time". The lifetime of a [referencing] iterator is (or should be) strictly less than that of the referent object. Of course, that's not what I wanted to say. Serves me write for adding spur-of-the-moment thoughts to an otherwise innocent question. Here's the sample code that inspired my OP: //----------------------------------------------- typedef std::map<std::string, Foo> primary_map; primary_map a; // Declaration beyond my control typedef std::map<primary_map::const_iterator, Bar> auxiliary_map; auxiliary_map b; void update(const std::string& key) { primary_map::const_iterator idx = a.find(key); if(idx == a.end()) throw std::logic_error("attempt to set auxiliary property for undefined object"); ++ b[idx].access_count; } //----------------------------------------------- What I wanted to do was ensure that b's keys are all valid iterators in a. I don't see any obvious easy way to do it. Unfortunately my tendancy to muse out loud took over as I was framing my original question. Sorry, everyone . So, question number 2: Does anybody know of a good way to keep b's keys in sync with a's iterators? "Good" is defined to be "better than strategically-placed O(n) garbage collection sweeps", and "in sync" is defined to be "(key in b => iterator in a) == true". Quote: I think this is simpler than you're making it. No doubt . Regards David Turner [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Pierre Baillargeon Guest Posted: Tue Feb 17, 2004 6:33 pm    Post subject: Re: Shouldn't iterators be ordered? Seems to me that what you are looking for can be done by reversing the declaration order: typedef std::map<B, C> AuxMap; typedef std::map<A, AuxMap> MapType; This pretty much ensure that you won't have a C without a B or an A. Since they are map, element are never invalidated or moved by insertion or deletion of other elements, so it is efficient. If you really need the two maps to be independant, then you need to extract what constitutes the fundamental identity of a B: typedef std::map<A, B> MapType; struct BID { BID( const B & ); bool operator<( const BID & ) const; }; typedef std::map [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alexander J. Oss Guest Posted: Wed Feb 18, 2004 12:27 pm    Post subject: Re: Synchronizing auxiliary maps (was: Re: Shouldn't iterato "David Turner" <david (AT) firepro (DOT) co.za> wrote Quote: typedef std::map<std::string, Foo> primary_map; primary_map a; // Declaration beyond my control typedef std::map<primary_map::const_iterator, Bar> auxiliary_map; auxiliary_map b; void update(const std::string& key) { primary_map::const_iterator idx = a.find(key); if(idx == a.end()) throw std::logic_error("attempt to set auxiliary property for undefined object"); ++ b[idx].access_count; } //----------------------------------------------- What I wanted to do was ensure that b's keys are all valid iterators in a. I don't see any obvious easy way to do it. Unfortunately my tendancy to muse out loud took over as I was framing my original question. Sorry, everyone . It looks like you're uniquely identifying all Foo's with a string. So why not keep access counts keyed the same way? Like: typedef std::map<std::string, Foo> primary_map; typedef std::map<std::string, Bar> auxiliary_map; primary_map a; auxiliary_map b; void update(const std::string &key) { primary_map::const_iterator idx = a.find(key); if (idx == a.end()) throw std::logic_error("unfound"); ++b[key].access_count; } [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jim Melton Guest Posted: Thu Feb 19, 2004 10:35 am    Post subject: Re: Shouldn't iterators be ordered? "David Turner" <david (AT) firepro (DOT) co.za> wrote Quote: Hi Shouldn't it be a requirement on all iterators that they have a strict weak ordering? This is to facilitate things like: typedef std::map<A, B> MapType; typedef std::map<MapType::const_iterator, C> AuxMap; Without addressing the basic question, it seems to me that this construct is inherently flawed. There are too many things that can invalidate an iterator to make an iterator a suitable key for a map. -- <disclaimer> Opinions posted are those of the author. My company doesn't pay me enough to speak for them. </disclaimer> -- Jim Melton Software Architect, Fusion Programs Lockheed Martin IS&S (303) 971-3846 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Thu Feb 19, 2004 2:27 pm    Post subject: Re: Shouldn't iterators be ordered? [email]david (AT) firepro (DOT) co.za[/email] (David Turner) wrote (abridged): Quote: Shouldn't it be a requirement on all iterators that they have a strict weak ordering? That could be quite a burden for the implementation. Suppose the container is paging items in and out of memory behind the scenes. You may not be able to order by address. Quote: template<typename T struct iterator_less { bool operator ()(const T& lhs, const T& rhs) { return &*lhs < &*rhs; } }; This assumes the arguments are from the same array. For, eg, list std::less() instead of operator<(), though. -- Dave Harris, Nottingham, UK [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Fri Feb 20, 2004 1:18 pm    Post subject: Re: Shouldn't iterators be ordered? Jim Melton <jim.melton (AT) lmco (DOT) com> writes: Quote: "David Turner" <david (AT) firepro (DOT) co.za> wrote in message news:1076925452.669531 (AT) tanzanite (DOT) firepro.co.za... Hi Shouldn't it be a requirement on all iterators that they have a strict weak ordering? This is to facilitate things like: typedef std::map<A, B> MapType; typedef std::map<MapType::const_iterator, C> AuxMap; Without addressing the basic question, it seems to me that this construct is inherently flawed. There are too many things that can invalidate an iterator to make an iterator a suitable key for a map. Likewise pointers? I've used exactly that sort of arrangement very effectively in the past. It just requires some care w.r.t. maintaining the whole-system invariants of the two maps. -- Dave Abrahams Boost Consulting www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jim Melton Guest Posted: Sat Feb 21, 2004 11:03 am    Post subject: Re: Shouldn't iterators be ordered? "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote Quote: Jim Melton <jim.melton (AT) lmco (DOT) com> writes: Without addressing the basic question, it seems to me that this construct is inherently flawed. There are too many things that can invalidate an iterator to make an iterator a suitable key for a map. Likewise pointers? It depends. A pointer into a region of memory that is subject to being "realloc"d is certainly dangerous. But a pointer that is explicitly managed should be more stable than iterators. I suppose the problem lies in the fact that an iterator is a thinly veiled encapsulation of implementation details of the container. Operations on the container (completely indepedent and external to the iterator) can cause the iterator to become invalid. Consequently, I think it is safest if iterators not become too widely separated from their associated containers. Using an iterator as a key into an associative container certainly is wide separation. Quote: I've used exactly that sort of arrangement very effectively in the past. It just requires some care w.r.t. maintaining the whole-system invariants of the two maps. With care, lots of dangerous things can be done. As long as the dangers are well understood (and documented for the next person who comes along), it can be an acceptable design choice. But usually not my first one. -- <disclaimer> Opinions posted are those of the author. My company doesn't pay me enough to speak for them. </disclaimer> -- Jim Melton Software Architect, Fusion Programs Lockheed Martin IS&S (303) 971-3846 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Sat Feb 21, 2004 6:16 pm    Post subject: Re: Shouldn't iterators be ordered? Jim Melton <jim.melton (AT) lmco (DOT) com> writes: Quote: "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote in message news:uwu6j6t72.fsf (AT) boost-consulting (DOT) com... Jim Melton <jim.melton (AT) lmco (DOT) com> writes: Without addressing the basic question, it seems to me that this construct is inherently flawed. There are too many things that can invalidate an iterator to make an iterator a suitable key for a map. Likewise pointers? It depends. A pointer into a region of memory that is subject to being "realloc"d is certainly dangerous. But a pointer that is explicitly managed should be more stable than iterators. I don't know what you mean by "explicitly managed". If I do: std::auto_ptr<int> p(new int(0)); is p.get() a pointer that's explicitly managed? Quote: I suppose the problem lies in the fact that an iterator is a thinly veiled encapsulation of implementation details of the container. Operations on the container (completely indepedent and external to the iterator) can cause the iterator to become invalid. Consequently, I think it is safest if iterators not become too widely separated from their associated containers. Using an iterator as a key into an associative container certainly is wide separation. Quote: I've used exactly that sort of arrangement very effectively in the past. It just requires some care w.r.t. maintaining the whole-system invariants of the two maps. With care, lots of dangerous things can be done. Oh, come now. This is no more dangerous than any other composite structure with an invariant. For example, a binary tree where parents point to their children and children also point to their parents comes to mind. Quote: As long as the dangers are well understood (and documented for the next person who comes along), it can be an acceptable design choice. But usually not my first one. My point is that this is just a simple matter of maintaining invariants, and just like any other such problem you can make it safe by pushing the details (e.g. the two maps) into a class that encapsulates the system, and not providing easy mutable access to the parts of the system which, if changed, could break the invariants. -- Dave Abrahams Boost Consulting www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andreas Huber Guest Posted: Sun Feb 22, 2004 1:39 am    Post subject: Re: Shouldn't iterators be ordered? Jim Melton wrote: Quote: "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote in message news:uwu6j6t72.fsf (AT) boost-consulting (DOT) com... Jim Melton <jim.melton (AT) lmco (DOT) com> writes: Without addressing the basic question, it seems to me that this construct is inherently flawed. There are too many things that can invalidate an iterator to make an iterator a suitable key for a map. Likewise pointers? It depends. A pointer into a region of memory that is subject to being "realloc"d is certainly dangerous. But a pointer that is explicitly managed should be more stable than iterators. 23.1.2/8 sais that an iterator into a map is only invalidated when you remove the object the interator refers to. This is, as David Abrahams already pointed out, equally "dangerous" as keeping a plain pointer to an object. A map does not invalidate all iterators on insert like a vector does. Regards, Andreas [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jim Melton Guest Posted: Tue Feb 24, 2004 3:29 am    Post subject: Re: Shouldn't iterators be ordered? "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote Quote: Jim Melton <jim.melton (AT) lmco (DOT) com> writes: "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote in message news:uwu6j6t72.fsf (AT) boost-consulting (DOT) com... Jim Melton <jim.melton (AT) lmco (DOT) com> writes: Without addressing the basic question, it seems to me that this construct is inherently flawed. There are too many things that can invalidate an iterator to make an iterator a suitable key for a map. Likewise pointers? It depends. A pointer into a region of memory that is subject to being "realloc"d is certainly dangerous. But a pointer that is explicitly managed should be more stable than iterators. I don't know what you mean by "explicitly managed". If I do: std::auto_ptr<int> p(new int(0)); is p.get() a pointer that's explicitly managed? Yes. But, hanging on to the pointer returned by p.get() is analogous to the iterator problem. You certainly wouldn't want the pointer returned by p.get() to be used as a key into any data structure. And it illustrates the point you make below that it is important to make sure your invariants are invariant. The above is little different than: int* p(new int(0)); int* q=p; delete p; (other than the explicit delete is not visible in your code snippet). Here the pointer has been explicitly managed. Badly. Quote: I've used exactly that sort of arrangement very effectively in the past. It just requires some care w.r.t. maintaining the whole-system invariants of the two maps. With care, lots of dangerous things can be done. Oh, come now. This is no more dangerous than any other composite structure with an invariant. For example, a binary tree where parents point to their children and children also point to their parents comes to mind. I think we are coming at this from two different levels. I'm talking about using iterators (in general) as keys in maps (in general). If I remember the OP's context, it wasn't at all clear that the two maps he proposed were encapsulated in a class that was concerned with maintaining the coherency of the structures. As pointed out elsewhere, std::map iterators are more stable than other kinds of iterators; In general, though, I still think that using iterators as primary keys is dangerous. Quote: As long as the dangers are well understood (and documented for the next person who comes along), it can be an acceptable design choice. But usually not my first one. My point is that this is just a simple matter of maintaining invariants, and just like any other such problem you can make it safe by pushing the details (e.g. the two maps) into a class that encapsulates the system, and not providing easy mutable access to the parts of the system which, if changed, could break the invariants. Agreed. That's exactly what I meant when I said that well understood dangers can be acceptable. -- <disclaimer> Opinions posted are those of the author. My company doesn't pay me enough to speak for them. </disclaimer> -- Jim Melton Software Architect, Fusion Programs Lockheed Martin IS&S (303) 971-3846 [ 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.