C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  iterator invalidation trouble          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message Alexander Stippler Guest Posted: Mon Dec 29, 2003 5:22 pm    Post subject: iterator invalidation trouble Hi, I've got trouble with some well known issue. Iterator invalidation. My situation: for (it=v.begin(); it!=v.end(); ++it) { f(*it); } Under some circumstances, f may alter the container by removing the current item. Thus the iterator it gets invalid. My question is, if there is a way to handle this specific case. The problem is that the for loop is user code, and the user should not even notice that v changed, so I cannot simply introduce a second iterator inside the for loop. The iterator it should simply go on iterating with the following item, if *it is deleted. *it is defininitely the only item which can be deleted by f. I think this problem is rather general. Are there any threads online on "robust iterators for c++"? Is there a trick for my situation? regards, alex Back to top Gianni Mariani Guest Posted: Mon Dec 29, 2003 5:41 pm    Post subject: Re: iterator invalidation trouble Alexander Stippler wrote: Quote: Hi, I've got trouble with some well known issue. Iterator invalidation. My situation: for (it=v.begin(); it!=v.end(); ++it) { f(*it); } Under some circumstances, f may alter the container by removing the current item. Thus the iterator it gets invalid. My question is, if there is a way to handle this specific case. The problem is that the for loop is user code, and the user should not even notice that v changed, so I cannot simply introduce a second iterator inside the for loop. The iterator it should simply go on iterating with the following item, if *it is deleted. *it is defininitely the only item which can be deleted by f. I think this problem is rather general. Are there any threads online on "robust iterators for c++"? Is there a trick for my situation? The way I've solved this problem in the past is to not erase the objects. I made the container have pointers to the objects and once the user was done with the iterating it would erase the "empty" pointers. I also provided a "traverser" template that would wrap the for loop with the appropriate cleaning call at the end of the loop. Back to top Ron Natalie Guest Posted: Mon Dec 29, 2003 6:08 pm    Post subject: Re: iterator invalidation trouble "Alexander Stippler" <stip (AT) mathematik (DOT) uni-ulm.de> wrote Quote: I think this problem is rather general. Are there any threads online on "robust iterators for c++"? Is there a trick for my situation? You say the user shouldn't know if the container has changed, however since you expose all the ugliness to him, he does have to know. It's hard to understand what solution to propose without a better description of the problem. Why is the user responsible for iterating some function f() over a list when f() is not under their control. Possibly this is better solved by passing the container v (or begin and end iterators) to f() and letting it manage searching over the list itself. Back to top Alexander Stippler Guest Posted: Mon Dec 29, 2003 6:31 pm    Post subject: Re: iterator invalidation trouble Ron Natalie wrote: Quote: "Alexander Stippler" <stip (AT) mathematik (DOT) uni-ulm.de> wrote in message news:3ff061a1 (AT) news (DOT) uni-ulm.de... I think this problem is rather general. Are there any threads online on "robust iterators for c++"? Is there a trick for my situation? You say the user shouldn't know if the container has changed, however since you expose all the ugliness to him, he does have to know. It's hard to understand what solution to propose without a better description of the problem. Why is the user responsible for iterating some function f() over a list when f() is not under their control. Possibly this is better solved by passing the container v (or begin and end iterators) to f() and letting it manage searching over the list itself. As an example of my application, let v be an arithmetic sparse vector, where I only want to store non zero elements. Now I have e.g. operator-(SparseVector v, double c), which could internally have a loop using an iterator _it_ to add c to every non-zero-element. Here is the client code - I do not want to have to consider the possibility of deleting elements in every function using an iterator. If c == *_it_, this would result in *_it_ == 0 and thus the current item is removed. This happens immediately, when assigning *_it_ its new value (through a proxy). That's it. How to handle this? I considered not deleting *_it_ immediately, but then I would have to guess the right time to do it. Is there any simpler solution than registering iterators with their container? regards, alex Back to top Ron Natalie Guest Posted: Mon Dec 29, 2003 6:46 pm    Post subject: Re: iterator invalidation trouble "Alexander Stippler" <stip (AT) mathematik (DOT) uni-ulm.de> wrote Quote: That's it. How to handle this? I considered not deleting *_it_ immediately, but then I would have to guess the right time to do it. Is there any simpler solution than registering iterators with their container? My suggestion is that you not use iterators at all. Make a for_each() like function that transforms the elements, that way it is immune to the traversal of the container. If things are going to magically appear and disappear from the container, best not to expose iterators to the user at all. Back to top Dan W. Guest Posted: Mon Dec 29, 2003 6:52 pm    Post subject: Re: iterator invalidation trouble On Mon, 29 Dec 2003 19:31:48 +0100, Alexander Stippler <stip (AT) mathematik (DOT) uni-ulm.de> wrote: Quote: Ron Natalie wrote: "Alexander Stippler" <stip (AT) mathematik (DOT) uni-ulm.de> wrote in message news:3ff061a1 (AT) news (DOT) uni-ulm.de... I think this problem is rather general. Are there any threads online on "robust iterators for c++"? Is there a trick for my situation? You say the user shouldn't know if the container has changed, however since you expose all the ugliness to him, he does have to know. It's hard to understand what solution to propose without a better description of the problem. Why is the user responsible for iterating some function f() over a list when f() is not under their control. Possibly this is better solved by passing the container v (or begin and end iterators) to f() and letting it manage searching over the list itself. As an example of my application, let v be an arithmetic sparse vector, where I only want to store non zero elements. Now I have e.g. operator-(SparseVector v, double c), which could internally have a loop using an iterator _it_ to add c to every non-zero-element. Here is the client code - I do not want to have to consider the possibility of deleting elements in every function using an iterator. If c == *_it_, this would result in *_it_ == 0 and thus the current item is removed. This happens immediately, when assigning *_it_ its new value (through a proxy). That's it. How to handle this? I considered not deleting *_it_ immediately, but then I would have to guess the right time to do it. Is there any simpler solution than registering iterators with their container? regards, alex You mean you are subtracting a number from all these numbers, and removing them once they become zero? What about if they become negative? You also say "if( c == *it )" but you cannot compare floats or doubles for equality like that. And which iterator(s) become(s) non-valid? You mean that you have multiple iterators in other parts of the code pointing at elements in this container as you're deleting elements. You haven't explained basic things, like, do you need the elements to be sorted? Random accessible? Find-able in constant time? There are containers, for instance hash_set and hash_map, which have the advantage that iterators are not invalidated by insertion or deletion of elements. Or you could achieve something similar by using a vector of pointers to heap-allocated objects, then you keep pointers to particular objects, rather than iterators. HTH Back to top Howard Hinnant Guest Posted: Mon Dec 29, 2003 11:02 pm    Post subject: Re: iterator invalidation trouble In article <3ff061a1 (AT) news (DOT) uni-ulm.de>, Alexander Stippler <stip (AT) mathematik (DOT) uni-ulm.de> wrote: Quote: Hi, I've got trouble with some well known issue. Iterator invalidation. My situation: for (it=v.begin(); it!=v.end(); ++it) { f(*it); } Under some circumstances, f may alter the container by removing the current item. Thus the iterator it gets invalid. My question is, if there is a way to handle this specific case. The problem is that the for loop is user code, and the user should not even notice that v changed, so I cannot simply introduce a second iterator inside the for loop. The iterator it should simply go on iterating with the following item, if *it is deleted. *it is defininitely the only item which can be deleted by f. I think this problem is rather general. Are there any threads online on "robust iterators for c++"? Is there a trick for my situation? You could use a container that only invalidates the erased element (list, set, multiset, etc.) and then do something like: for (it = v.begin(); it != v.end() f(*it++); This is effectively: for (it = v.begin(); it != v.end() { It temp = it; ++it; f(*temp); } That is, you increment off of the iterator before it possibly becomes invalidated. -Howard Back to top Gianni Mariani Guest Posted: Tue Dec 30, 2003 5:39 am    Post subject: Re: iterator invalidation trouble Howard Hinnant wrote: Quote: You could use a container that only invalidates the erased element (list, set, multiset, etc.) and then do something like: for (it = v.begin(); it != v.end() f(*it++); This is effectively: for (it = v.begin(); it != v.end() { It temp = it; ++it; f(*temp); } That is, you increment off of the iterator before it possibly becomes invalidated. This is not a general solution. This assumes that the current object is the one that gets removed, what if it is the next object instread, what it there is a cascade effect and all objects in the container get removed ? I'll give you an example. Consider a list (like this one) that has "client contexts". Each client may cause a disconnect (destruct) of any number of other clients on the list. Hence each time you traverse, every iterator must remain valid. (this is a true-life example BTW). Back to top Jeff Schwab Guest Posted: Tue Dec 30, 2003 5:41 am    Post subject: Re: iterator invalidation trouble Alexander Stippler wrote: Quote: Hi, I've got trouble with some well known issue. Iterator invalidation. My situation: for (it=v.begin(); it!=v.end(); ++it) { f(*it); } Under some circumstances, f may alter the container by removing the current item. Thus the iterator it gets invalid. My question is, if there is a way to handle this specific case. The problem is that the for loop is user code, and the user should not even notice that v changed, so I cannot simply introduce a second iterator inside the for loop. The iterator it should simply go on iterating with the following item, if *it is deleted. *it is defininitely the only item which can be deleted by f. I think this problem is rather general. Are there any threads online on "robust iterators for c++"? Is there a trick for my situation? regards, alex Write your own "smart iterator" class. Have the constructor and destructor maintain a static count of existing iterators. Only do the cleanup of your sparse matrix (removing zero-valued elements, etc.) when there are no outstanding iterators. -Jeff Back to top Alexander Stippler Guest Posted: Tue Dec 30, 2003 8:55 pm    Post subject: Re: iterator invalidation trouble Thank you for your suggestions. I will investigate the smart iterator approach a bit further, since all other approaches do not leave things transparent to the user or at least restrict his possibilities. 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 (comp.lang.c++) 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.