Jump to content
  • Advertisement
Sign in to follow this  
Agony

[.net] Modifying IEnumerator Elements

This topic is 4767 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Just learning .NET 2.0 currently, and I've got a problem with the SortedDictionary collection. What I need to do is step through and modify each element in the dictionary. I tried foreach first of all, but then learned that you can't modify elements of a foreach loop. Knowing already that a foreach hides stuff dealing with IEnumerable and IEnumerator, I checked the documentation, and sure enough, "Enumerators can be used to read the data in the collection, but they cannot be used to modify the underlying collection." The only option I can think of currently is to get the Keys collection from the dictionary, and do a foreach on those, and then index into the dictionary using those, but that seems inefficient; a O(log n) search must be done for each element. But that's better than any option I had thought of when I began this post, so I'll go ahead and do that. But if anyone knows of a better and more efficient way to enumerate and modify all the elements of a dictionary, I'd love to hear it. I feel like I'm doing this wrong. A binary tree traversal is a very simple thing to do, and doesn't require any searches at all, and modification of elements is perfectly fine, as long as the keys remain untouched.

Share this post


Link to post
Share on other sites
Advertisement
I can't see any other way to traverse the tree efficiently, other than the enumerator...

While using an enumerator, you cannot modify the collection. But that doesn't mean its items must be immutable!

So while this is forbidden while enumerating:
foreach (Value v in collection.Values) // Same if you enumerate KeyValuePair
v = new Value();

This should be ok (I think):
foreach (Value v in collection.Values) // Same if you enumerate KeyValuePair
v.field = 4;

By the way, I think your solution will not work, if it goes like that:
foreach (Key k in collection.Keys)
collection[k] = new Value();

Because you're modifying the collection, while enumerating (even if the two are not directly related).

I hope it helps,
jods

Share this post


Link to post
Share on other sites
Well, I more or less fixed my problem. I was dumb to an extent. I had a dictionary of structs, so whenever I tried to change the elements, it would do copies and such, since a struct is a value type. Once I realized that this was where some of my errors were coming from, I changed to a class, and then I could alter the elements, because they were just references, and the references themselves weren't changing; only what they were referencing was getting changed.

Your second example, jods, was actually a great example of what I was wanting. If Value is a struct, it seems you can't do that. What I did try to do to get around that was use TryGetValue(), and then change that variable. But I had a problem that later on, the elements didn't seem to have been initialized like I thought. All of their fields were still null, even though I explicitly watched them get set. That's when I realized that TryGetValue() was returning a copy, not a reference, and that's when I remembered that I was messing with structs. Silly me.

Share this post


Link to post
Share on other sites
Quote:
Original post by Agony
The only option I can think of currently is to get the Keys collection from the dictionary, and do a foreach on those, and then index into the dictionary using those, but that seems inefficient; a O(log n) search must be done for each element.

I don't think that's correct. If it's a Dictionary, lookup should be O(1) in the average case and O(n) in the worst case.

Share this post


Link to post
Share on other sites
I could be wrong, I didn't take too much time to think about it, but SortedDictionary is implemented using a red-black binary tree according to the documentation. And lookup I thought for a balanced binary tree was O(log n). The documentation at first seems to agree:
Quote:
The Generic SortedDictionary class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. The implementation is a red-black tree;

But then for the Item property it says:
Quote:
Retrieving the value of this property is an O(1) operation; setting the property is also an O(1) operation.

That doesn't sound right to me, but maybe I'm misthinking. I was under the impression that since it's beta documentation, it's just an error, especially seeing as it is merely saying the exact same thing for Dictionary, which I'm guessing is implemented with a hashtable, which if I am thinking correctly, does indeed have O(1) lookup.

Correct me if I'm wrong on any of this, though, if you care.

Share this post


Link to post
Share on other sites
I've always just used the CopyTo function of collections to copy to an array if I really needed to modify. That or run through the collection by index in a for loop as was suggested above.

Share this post


Link to post
Share on other sites
To those who suggested running an index:
SortedDictionary is a binary tree. It implements ICollection, but NOT IList. Hence there's no number-based indexed access, like dictionary[3]. We're traversing a tree here.

Agony:
yes, struct are a problem here, for sure. As for the Item access, I can't see how a O(1) access would work in a black-red tree. It's most probably a mistake in the preliminary documentation, and I wouldn't count on it. You are right to suppose that finding an element in a tree is a O(lg(n)) operation.

Have a nice day,
jods

Share this post


Link to post
Share on other sites
Quote:
Correct me if I'm wrong on any of this, though, if you care.

No, you're correct. I misread what you were saying. SortedDictionary uses a red-black tree and is most certainly O(lg[n]) retrieval, not O(1). I suspect the documentation just hasn't been updated yet.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!