Working with Dictionaries in C# - the Good & Bad of it...

Posted By: Urjit Singh Bhatia | Aug 8th, 2008 @ 11:36 AM | 18,365 Views | 13 Comments

Formats:

I am working on a project using XNA Game studios. The usual problem reared up one day - What data structure to use to store my objects like missiles and bots !!
The possible solutions?

Use array of objects
Use linked list of objects
Use dictionaries (now that sounds interesting!!)

I decided to use Dictionaries, since I had to access the objects directly by key.
The most advantageous point for using them is that, knowing the key the value access takes the least time. So using Linked Lists was totally out of question.
But dictionaries have another problem!! You can't deleted or modify elements of the dictionary during an active iteration like - ForEach loop.
Solution?
Well, might not be the most novel way out, but I guess it works fine...
I decided to store the keys of the elements to be deleted in an array, and after the loop expired, ran a simple for loop to delete the elements.
The accompanying code will make it clear.
foreach (KeyValuePair<int, EnemyShip> kvpenemy in dushman)
                        {
                            if (**Some Condition**)
                            {
                                miss[kvp.Key].IsCreated = false;
                                MissilesToUnload_Keys[MissileUnloadKey_Index] = kvp.Key;
                                MissileUnloadKey_Index++;

                                kvpenemy.Value.Explode = 1;
                                explosion = true;
                            }
                            if (kvpenemy.Value.Explode == 2)
                            {
                                EnemysToUnload_Keys[EnemyUnloadKey_Index] = kvpenemy.Key;
                                EnemyUnloadKey_Index++;
                            }
                        }

for(int i=0;i<MissileUnloadKey_Index;i++)
            {
                miss.Remove(MissilesToUnload_Keys[i]);
            }
            for (int i = 0; i < EnemyUnloadKey_Index; i++)
            {
                dushman.Remove(EnemysToUnload_Keys[i]);
            }

Rating:

gogole
Dude outside, Geek inside :)

Hi Urjit, Dictionary <> types are immutable during iteration (changing the collection throws an error due to execution gurantee issues ), you had to find out the hard way . To have a pleasant experience with them i would suggest in the case of missiles you have a damage/missile obj pair. This would require that you predetermine all the effects and relations (damage etc) of the object before runtime. The speed of object retrieval from the dictionary type would make up for all your hassle Wink

but if you'd want more control then i suggest you use arrays and relate the objects using an common index mapping ( damage for a missile maps to the missile through a common index shared).

//Donald

littleguru
(microsoft student partnering)++

In reply to gogole

#Aug 9th, 2008 @ 12:51 PM

It is not the generic (<>) types that are immutable during iteration but it's rather all types that you can enumerate and that are part of the .NET base class library. The exception was also thrown in .NET 1.0 and 1.1 where .NET didn't have generics. "foreach" does internally get the enumerator (calling the GetEnumerator method) and that enumerator throws if you change the collection.

That makes sense because the enumerator needs to know whether it is possible to move to the next object. A sucessful enumeration can't be guaranteed if you mess with the object that you want to enumerate on.

What I usually do is also to store the keys or elements and then after I got all of them remove them one by one.

littleguru
(microsoft student partnering)++

In reply to gogole

#Aug 9th, 2008 @ 12:51 PM

In .NET 3.5 (and C# 3.5, or VB9) you could do the following:

// build a dictionary with some dummy data.
Dictionary<int, string> store = new Dictionary<int, string>
{
    {1, "test1"}, {2, "test2"}, {3, "test3"}, {4, "test4"}, {5, "test5"}
};

// filter by key. get all keys that are higher than 3 and select only the key value.
// put the result into a list.
var keys = store.Where(x => x.Key > 3).Select(x => x.Key).ToList();

// the following call is the same as the line above.
// var keys = (from s in store
//             where s.Key > 3
//            select s.Key).ToList();

// loop over the keys and remove from the dictionary.
foreach (var key in keys)
{
    store.Remove(key);
}

gogole
Dude outside, Geek inside :)

In reply to littleguru

#Aug 9th, 2008 @ 2:15 PM

>It is not the generic (<>) types that are immutable during iteration but it's rather all types that you can enumerate and that are part of the .NET base class library

Ah ok then it has to do with the IEnumerble and IEnumerable<T> interface..... it is really the IEnumerable interface since the issue occured in .net 1.0's days as Chris pointed out.

littleguru
(microsoft student partnering)++

In reply to gogole

#Aug 10th, 2008 @ 1:03 PM

It's not the interface. It is how the enumerators are implemented... they don't tolerate modifications of the underlying list/collection/... while enumerating over it, which makes perfect sense since you can't guarantuee a true enumeration when the list is modified while going through it.

UrJiT
Live life to the fullest!!

In reply to littleguru

#Aug 10th, 2008 @ 6:24 PM

Ya you are right.. making enumerable items mutable makes no sense and is the correct programming construct. I used to save the Missile ID and the Missile Object in my game in dictionary, so I guess we anyways have to wait for the iteration to terminate and then delete the residual keys. Someone even suggested me to create another dictionary that would contain objects are some time frame old than the objects in the old dictionary. Basically, the idea was to check a property of the missile -> IsAlive (bool), if true then add it to carry over dictionary else do nothing.. and in the next iteration just compare, if there is a key-value-pair (kvp) that doesnt exist in the carry over dictionary then delete it.. But I found using a simple array as shown in the code to be more simple, elegant and hassle-free.
Thanks for your inputs guys..
-Urjit

gogole
Dude outside, Geek inside :)

In reply to UrJiT

#Aug 11th, 2008 @ 12:22 PM

yeah you are right , it makes no sense to make enumerable items mutable espercially during enumeration since it is the same data being enumerated upon.You know , the public key concept (always dynamic value for every item) applies in assigning a key with a dictionary type( MisileID qualifies on all grounds of dynamicity).... a bit of-topic i know Smiley

. Educative and interesing discussion Big Smile

parheric

Using the extension method ElementAt you are able to traverse the dictionary using a simple loop, i'm unsure of the penalty hit for using the extension method however. It might be more performant due to avoiding traversing the collection twice.

Dictionary<int, string> dict = new Dictionary<int, string>();
            for ( int i = 20; i < 30; ++i )
            {
                dict.Add( i, i.ToString() );
            }

            System.Diagnostics.Trace.WriteLine( dict.Count );

            for ( int i = 0; i < dict.Keys.Count; )
            {
                int key = dict.Keys.ElementAt( i );
                string value = dict[ key ];
                 System.Diagnostics.Trace.WriteLine( "value at " + key + " is " + value );
                if ( key % 2 == 0 )
                {
                    dict.Remove( key );
                }
                else
                {
                    ++i;
                }
            }

            System.Diagnostics.Trace.WriteLine( dict.Count );

dcuccia

In reply to parheric

#Aug 19th, 2008 @ 6:24 AM

Good point parheric. Would this work?

IEnmerable<K> SelectKeysWhere<K,V>(this Dictionary<K, V> myDictionary, Predicate<V> criterion)
{
    for(int i=0; i<myDictionary.Keys.Count; i++)
    {
        if (criterion(dict.Keys.ElementAt( i )))
            yield return i;
    }
}

foreach(var key in store.SelectKeysWhere(x=>x >3).ToList())
{
    store.Remove(key);
}

(Nevermind...this is exactly what littleguru was doing with built-in LINQ)