C# dictionary vs list usage

Question

I had two questions. I was wondering if there is an easy class in the C# library that stores pairs of values instead of just one, so that I can store a class and an integer in the same node of the list. I think the easiest way is to just make a container class, but as this is extra work each time. I wanted to know whether I should be doing so or not. I know that in later versions of .NET ( i am using 3.5) that there are tuples that I can store, but that's not available to me.

I guess the bigger question is what are the memory disadvantages of using a dictionary to store the integer class map even though I don't need to access in O(1) and could afford to just search the list? What is the minimum size of the hash table? should i just make the wrapper class I need?

Solution 1

If you need to store an unordered list of {integer, value}, then I would suggest making the wrapper class. If you need a data structure in which you can look up integer to get value (or, look up value to get integer), then I would suggest a dictionary.

Solution 2

The decision of List<Tuple<T1, T2>> (or List<KeyValuePair<T1, T2>>) vs Dictionary<T1, T2> is largely going to come down to what you want to do with it.

If you're going to be storing information and then iterating over it, without needing to do frequent lookups based on a particular key value, then a List is probably what you want. Depending on how you're going to use it, a LinkedList might be even better - slightly higher memory overheads, faster content manipulation (add/remove) operations.

On the other hand, if you're going to be primarily using the first value as a key to do frequent lookups, then a Dictionary is designed specifically for this purpose. Key value searching and comparison is significantly improved, so if you do much with the keys and your list is big a Dictionary will give you a big speed boost.

Data size is important to the decision. If you're talking about a couple hundred items or less, a List is probably fine. Above that point the lookup times will probably impact more significantly on execution time, so Dictionary might be more worth it.

There are no hard and fast rules. Every use case is different, so you'll have to balance your requirements against the overheads.

Solution 3

You can use a list of KeyValuePair:http://msdn.microsoft.com/en-us/library/5tbh8a42.aspx

Comments

[Sani Singh Huttunen]

Not a class but a struct: KeyValuePair. There's also Tuple (which is a class).

[Jim Mischel]

A good suggestion, although it's important to note that KeyValuePair<TKey, TValue> is a struct, meaning you have to deal with the sometimes inconvenient struct semantics.

[Corey]

I shudder any time I see anonymous types used for anything other than intermediate results. I know they're part of the language, and handy for specific cases, but they're so... untidy :)

[James Joshua Street]

thanks a lot for the advice. Do you happen to know what the minimum size on a dictionary is? does it waste a lot of memory if you use a dictionary for small numbers of values?

[James Joshua Street]

Thanks. this is probably what I'll end up using. Key value pair cause tuple isn't available. Forgot about this class

[Jim Mischel]

Tuple is not available in .NET 3.5, which the OP specifically stated that he's using.

[Jim Mischel]

I the minimum size of a Dictionary in .NET 4.5 appears to be 3 items. After that, it grows by doubling. Testing in the past indicates that Dictionary overhead is about 24 bytes per entry. The overhead for the Dictionary itself is somewhere between 50 and 100 bytes (not much more than the overhead for a List, actually).

[James Joshua Street]

wow, interesting. I would have expected the dictionary to need a lot more overhead.

[Tarec]

It's not a class. Also - it's way much slower than simple tuple class when working with it so if you can't use .NET 3.5 then I'd recommend creating simple custom class for that purpose.