Any way to purge a Dictionary of items meeting some criterion?
-
I understand the general difficulty of allowing an enumerable class to be modified within an enumerator. Nonetheless, there are times when it would be very useful to go through a dictionary and purge all items meeting some criterion. While it would be possible to produce a list of the keys of the items to be deleted and then iterate through that list, doing so would seem needlessly complex and expensive. I've searched for messages related to this subject and none that I've found seem to offer a solution except to note the general difficulties of allowing modification to an object within an enumerator. What would seem most useful would be to have an object that supported an interface similar to iEnumerable but with the addition of a method RemoveAndMoveNext. Use of that method would remove the currently-selected item from the collection and advance to the next one. It would disqualify any other enumerators that exist to the collection, but would do whatever was necessary to maintain its own correct operation. An alternative would be to have a ConditionalRemove method which would call a function on all items in the collection and remove those for which the function returns true. Such an approach could work well, but could be a nuisance in languages which don't support anonymous delegates. Are there any free dictionary-style collections that support anything like either of those suggestions?
-
I understand the general difficulty of allowing an enumerable class to be modified within an enumerator. Nonetheless, there are times when it would be very useful to go through a dictionary and purge all items meeting some criterion. While it would be possible to produce a list of the keys of the items to be deleted and then iterate through that list, doing so would seem needlessly complex and expensive. I've searched for messages related to this subject and none that I've found seem to offer a solution except to note the general difficulties of allowing modification to an object within an enumerator. What would seem most useful would be to have an object that supported an interface similar to iEnumerable but with the addition of a method RemoveAndMoveNext. Use of that method would remove the currently-selected item from the collection and advance to the next one. It would disqualify any other enumerators that exist to the collection, but would do whatever was necessary to maintain its own correct operation. An alternative would be to have a ConditionalRemove method which would call a function on all items in the collection and remove those for which the function returns true. Such an approach could work well, but could be a nuisance in languages which don't support anonymous delegates. Are there any free dictionary-style collections that support anything like either of those suggestions?
Or you could instantiate a new Dictionary, then iterate the existing one, adding the items you do want to the new one.
-
I understand the general difficulty of allowing an enumerable class to be modified within an enumerator. Nonetheless, there are times when it would be very useful to go through a dictionary and purge all items meeting some criterion. While it would be possible to produce a list of the keys of the items to be deleted and then iterate through that list, doing so would seem needlessly complex and expensive. I've searched for messages related to this subject and none that I've found seem to offer a solution except to note the general difficulties of allowing modification to an object within an enumerator. What would seem most useful would be to have an object that supported an interface similar to iEnumerable but with the addition of a method RemoveAndMoveNext. Use of that method would remove the currently-selected item from the collection and advance to the next one. It would disqualify any other enumerators that exist to the collection, but would do whatever was necessary to maintain its own correct operation. An alternative would be to have a ConditionalRemove method which would call a function on all items in the collection and remove those for which the function returns true. Such an approach could work well, but could be a nuisance in languages which don't support anonymous delegates. Are there any free dictionary-style collections that support anything like either of those suggestions?
supercat9 wrote:
Use of that method would remove the currently-selected item from the collection and
...invalidate the Enumerator all in one shot. As you've found out, you cannot modify a collection during an Enumeration ("for each" operation). The only solution would be to use in Indexed (for(i=0;i<10;i++) item(i)...) operation, treating the collection as an array instead.
A guide to posting questions on CodeProject[^]
Dave Kreskowiak Microsoft MVP Visual Developer - Visual Basic
2006, 2007, 2008 -
supercat9 wrote:
Use of that method would remove the currently-selected item from the collection and
...invalidate the Enumerator all in one shot. As you've found out, you cannot modify a collection during an Enumeration ("for each" operation). The only solution would be to use in Indexed (for(i=0;i<10;i++) item(i)...) operation, treating the collection as an array instead.
A guide to posting questions on CodeProject[^]
Dave Kreskowiak Microsoft MVP Visual Developer - Visual Basic
2006, 2007, 2008Dave Kreskowiak wrote:
...invalidate the Enumerator all in one shot. As you've found out, you cannot modify a collection during an Enumeration ("for each" operation).
The whole idea of having an object return an enumerator that supported a DeleteAndMoveNext object would be that such a function would do whatever was necessary to avoid jinxing the enumerator. Note that the DeleteAndMoveNext would not be a general-purpose delete; it could only delete the current object. A simple implementation for an array-based list, if one wanted deletes to be performed immediately, would be to move down all objects above the present object, without bumping the object index. A singly-linked list object whose iterator kept a pointer to the previous object could 'swing' that pointer to point to the object following the present one and then advance the present object (note that this would be much faster than doing a search-and-delete). An alternative general approach to allow deletions while traversing an iEnumerable object would be to have the 'delete' function mark an item as invalid (using either a 'valid' flag or a sentinel value) and also set a flag in the collection to indicate that one or more deletions had taken place. If 'add' operations are not allowed during an enumeration, the next add operation could check whether any items are marked for deletion (using the collection's flag to start with) and then remove all items that are so marked. For an array-based implementation, this could be much faster than having all deletes performed 'instantly'.
-
Or you could instantiate a new Dictionary, then iterate the existing one, adding the items you do want to the new one.
That could be done, but it would seem rather wasteful. In nearly all common practical algorithms for storing collections, support for DeleteAndMoveNext could be added relatively simply. In many cases, it would add no extra work to the iterator's normal operation; in others, it would add a small amount of work (e.g. a singly linked list would need to keep a pointer to the item before the current one). Given the number of tasks that require striking from a collection objects which meet a particular criterion, and given that an iterator will often have information that would facilitate the deletion of an object from a collection, having an extended iEnumerator interface would seem useful. BTW, for some types of collection, where the enumerator contains all the information about an object (e.g. a KeyValuePair) it may be useful to have general-purpose Add and Delete functions within the enumerator itself. Such functions would invalidate any other enumerators to the root object, but would do whatever was necessary to maintain their own validity. Not sure that would have much added utility beyond DeleteAndMoveNext, though.
-
Dave Kreskowiak wrote:
...invalidate the Enumerator all in one shot. As you've found out, you cannot modify a collection during an Enumeration ("for each" operation).
The whole idea of having an object return an enumerator that supported a DeleteAndMoveNext object would be that such a function would do whatever was necessary to avoid jinxing the enumerator. Note that the DeleteAndMoveNext would not be a general-purpose delete; it could only delete the current object. A simple implementation for an array-based list, if one wanted deletes to be performed immediately, would be to move down all objects above the present object, without bumping the object index. A singly-linked list object whose iterator kept a pointer to the previous object could 'swing' that pointer to point to the object following the present one and then advance the present object (note that this would be much faster than doing a search-and-delete). An alternative general approach to allow deletions while traversing an iEnumerable object would be to have the 'delete' function mark an item as invalid (using either a 'valid' flag or a sentinel value) and also set a flag in the collection to indicate that one or more deletions had taken place. If 'add' operations are not allowed during an enumeration, the next add operation could check whether any items are marked for deletion (using the collection's flag to start with) and then remove all items that are so marked. For an array-based implementation, this could be much faster than having all deletes performed 'instantly'.
Hi, two comments: 1. I too would like to have a non-resettable enumerator that remains operational when elements are modified, deleted or new ones inserted at a point that has already been passed. 2. There is a nice List.RemoveAll() Method that accepts a predicate. That should solve your problem. :)
Luc Pattyn [Forum Guidelines] [My Articles]
Fixturized forever. :confused:
-
Hi, two comments: 1. I too would like to have a non-resettable enumerator that remains operational when elements are modified, deleted or new ones inserted at a point that has already been passed. 2. There is a nice List.RemoveAll() Method that accepts a predicate. That should solve your problem. :)
Luc Pattyn [Forum Guidelines] [My Articles]
Fixturized forever. :confused:
Luc Pattyn wrote:
There is a nice List.RemoveAll() Method that accepts a predicate.
Good to know. Unfortunately I need a collection that behaves like a dictionary. Perhaps the best approach would be to have something that's like a dictionary with the addition of RemoveForAll; unfortunately I know no good way to adapt the existing dictionary to fit that need except by having the removeForAll create a list of keys of objects to be deleted, which would likely take time n^2.