8 ms·
Deleting from a container while you are iterating over it should always raise red flags.
by praptak 15y ago
Deleting from a container while you are iterating over it should always raise red flags.
- morsch 15y agoDepends on what you want to accomplish and what your container and iterators support. If your Iterator offers a delete method, I think it's a very elegant and clear way to filter a container. for (Iterator it = container.iterator(); it.hasNext(); ) if (!predicate(it.next())( it.remove(); It's more ugly and error prone if you've got to juggle an index, though.
- JoachimSchipper 15y agoEven with plain C, you can just iterate backwards: for (i = ctr_size(container); i > 0; i--) if (!predicate(container, i - 1)) ctr_remove(container, i - 1);
- hxa7241 15y agofor (i = ctr_size(container); i--; ) if (!predicate(container, i)) ctr_remove(container, i);
- JoachimSchipper 15y agoThat's arguably better. Nitpick: start at ctr_size(container) - 1. [Feel free to edit your post, and I'll just delete this one.]
- BrandonM 15y agoNope. The decrement is occurring in the test, so it occurs after the initialization and before the first iteration.
- sid0 15y agofilter predicate xs :)
- rtperson 15y agoHaskell, I assume. Two things really make Haskell shine when it comes to problems like this: 1) higher-order list operations -- you're not iterating through indices, so there is no possibility for off-by-one errors, and 2) immutability -- your code takes a new list with the undesirable elements removed; you can't remove elements of a structure at the same time you're iterating through it. I always love the problems on SPOJ where they give you the number of cases up front, because in Haskell you can almost always throw out that value. Your map function knows when the list is out of elements.
- sid0 15y agoYeah, I was thinking Haskell, but any functional language will do. Problems like the one in the blog post really make you appreciate them.
- morsch 15y agoThe snippet I posted can easily be made into a generic function<T> that takes a collection<T> and a predicate<T>. For example, the Apache Commons library offers such a function for Java, so where available the code comes down to the fairly similar CollectionUtils.filter(collection, predicate); Of course aside from being a bit more verbose, predicate needs to be an object (often a singleton), because you can't pass around functions.
- wanorris 15y agoIt's not as concise as Haskell, but the addition of FP capabilities to C# make it a lot more pleasant as a practical language than it was in earlier days. var filteredCollection = collection.Where(x => predicate(x));
- sid0 15y agoAs far as I remember you can write that as var filteredCollection = collection.Where(predicate); I agree that C# is a fundamentally usable language.
- WildUtah 15y agoUse the goes-to-zero operator. for (i = container.size; i-->0;) if(deletep(container, i)) container.remove(i);
- romac 15y agoReminds me of something :)
- Flow 15y agowhile(container.Size > 0) container.Remove(0); No need for variables.
- huhtenberg 15y agocontainer.clear(); No need for looping :)
- Flow 15y agoYeah sure, :) , but I meant for those other cases when there are no Clear() method. :)
- sunir 15y agoThe correct idiom is delete list head until list is empty. The iterator may become invalid if the collection it derived from changes. Iterator delete methods are crazy to begin with since iteration does not correlate with deletion. But anyway it is not clear where the iterator's cursor will point after you delete the current element. You could end up deleting every second element in the container.
- morsch 15y agoMy example wasn't clearing the list, it's a filter. And depending on what language and library you're talking about, it's very clear where the cursor will point to after a delete. There's nothing crazy about it with an even halfway sane collection framework.
- scott_s 15y agoDiscussion about iterators removing anything aside, I don't think your example disagrees with the parents point. His point was that iterating over a containing while removing items should raise red flags. And it should, always. You should always inspect such loops with more scrutiny because more things are going on, and it's surprisingly easy to get such code correct as multiple things are changing out from under you. In the systems class I TAed, when students had memory corruption problems, removing items while iterating over a linked list was at the top of my list of things to look for.
- altrego99 15y agoIsn't clear() itself a "while (not empty) delete element"?
- dkersten 15y agoMaybe, maybe not - depends on the container. But thats not the point - while (not empty) is not iterating over the loop, so there is no danger of corrupting the iterator.
- benhoyt 15y agoVery unlikely. There class implementation can almost certainly do it with an O-1 operation, like "self._internal_count = 0".
- jcromartie 15y agoor self._tabs = new List();
- eropple 15y agoIt might be. It also might be a "new List<TabPage>" or even some faster, internal construct. I don't think .NET makes a promise here, though I could be wrong.
- StrawberryFrog 15y agoA while loop isn't in itself an iterator. There's a difference between while(collection.Count > 0) { collection.Delete(0); } .. which is a working implementation of clear, though probably superfluous. and... int i = 0; while(i < collection.Count) { collection.Delete(i); i++; } which does try to walk along the list and is broken. Also, .Net has a specific exception to stop you modifying a collection while an enumerator is walking along it. Google for "Collection was modified; enumeration operation may not execute"
- jqueryin 15y agoEspecially when you're re-calculating the count on each iteration :) Inefficient and incorrect. Double whammy. While not as efficient as while(--), the fix get's the point across: for (int i=0,j=this.MyControl.TabPages.Count; i < j; i++) { this.MyControl.TabPages.Remove(this.MyControl.TabPages[i]); }
- dkersten 15y agoWon't this.MyControl.TabPages[i] be invalid once i becomes greater than what this.MyControl.TabPages.Count now is? Since the "always remove element 0" code from the article works, I expect your code won't work because when you remove an element form the list, all subsequent elements now have an index one less than before, so after j/2 elements, you'll overrun the list.
- billybob 15y agoCorrect. I think the logical thing to do would be to delete from the end so that the index is always valid. for (int i=this.MyControl.TabPages.Count - 1; i > 0; i--) { this.MyControl.TabPages.Remove(this.MyControl.TabPages[i]); } Imagine the count is 2. The first iteration you delete item 1, the second you delete item 0, and then the loop exits. EDIT: Actually, as someone else pointed out, it's clearer to use a while loop that deletes the 0th item until the collection is empty.
- kevinkemp 15y agoActually, you will never delete the final element with that code. I think what you meant was: for (int i=this.MyControl.TabPages.Count; i > 0; i--) { this.MyControl.TabPages.Remove(this.MyControl.TabPages[i-1]); }
- dkersten 15y agoI prefer: for (int i=this.MyControl.TabPages.Count - 1; i >= 0; i--) { this.MyControl.TabPages.Remove(this.MyControl.TabPages[i]); } Though a simple while loop is much easier to follow, even if its less efficient than removing the elements in reverse.