   C# Collection Question
  So i've recently become aware of the difference in speeds through the various collections offered in C# (ArrayList, SortedList, List, Dictionary, etc) and so far I have learned the difference in speed for inserting, removing and iterating. I have tried to do quite a bit of searching and haven't been able to find anything conclusive on the problem I am facing.So far it seems that List is the best for most cases where you just need an array however I am doing numerous things where I need to be able to lookup an id very fast (1000+ objects) so Dictionary definately seems to fit the bill.However, there are some cases where even though I need to be able to lookup by id I also need to iterate through the entire list very fast and a Dictionary enumerator is atleast 2x slower, sometimes 3x slower than a List to iterate through (in my testing). Is the difference not enough to worry about or is there a better way to do both? Is the solution to just create a List and a Dictionary and maintain both (doesn't seem ideal to me) - or finally, is there a better Collection class that gives me the best of both worlds?   
  I wouldn't worry about it until profiling tells you that the iteration has become a bottleneck. You may want to investigate the SortedList or SortedDictionary classes further, depending on exactly how you need to use the collection.In general, I would avoid any of the nongeneric types such as ArrayList. They provide no advantages over their generic counterparts and can actually be somewhat less optimal especially if the type you're storing is a value type and thus must be boxed and unboxed all the time.   ;  How important is insertion speed? A SortedList will give you fast iteration and lookups (both by key and by index) at the cost of insertion speed.   ;  As far as importance goes I am looking for lookup speed > iteration speed > insertion speed - however, inserting/removing is still very important as I will be doing it consistently throughout.I was actually using SortedList before but because it doesn't have a template type it takes it almost 3x longer to insert over Dictionary.I also did test SortedDictionary and it's actually 3x slower than Dictionary at enumerating.Also - when looking up a value with Dictionary it's actually roughly 14x faster at retrieval than SortedList.Basically Dictionary > SortedList in every single case except iterating... which is the one problem I am trying to solve. But then it boils down to List > Dictionary > SortedList when relation to iterating so basically.. I want all the benefits of Dictionary in relation to fast lookup - but all the benefits of List being able to iterate fast... and I don't know if that is possible without two lists - which is why I was asking.   ;  I'm very skeptical of your numbers, and you should be too. Benchmarking is a very difficult task that should not be done lightly; read more here.As Josh already stated, take a generic type that provides the functionality you need, and worry about performance after a proper profiler has determined that it is indeed a bottleneck.   ;Quote:Original post by NabrenI was actually using SortedList before but because it doesn't have a template type it takes it almost 3x longer to insert over Dictionary.Hold! Always use the generic versions of collections.Try again with System.Collections.Generic.SortedList<TKey, TValue> instead of System.Collections.SortedList.   ;  Aye, I was doing very simple tests... doing ~10 million operations with each object and comparing the time immediately before and immediately after - while it may not get me scientific results - it should atleast be accurate enough to show which object is faster at which operation - even if the scale is off... doesn't matter how much - even MSDN says Dictionary is faster than SortedList.However, I agree with your point and will take your advice. Seems this is a very special case because usually if you want to a fast lookup structure you won't need to iterate on it.Quote:Hold! Always use the generic versions of collections.Try again with System.Collections.Generic.SortedList<TKey, TValue> instead of System.Collections.SortedList.I actually noticed that after posting my previous post and did test it - it did improve insertion however Dictionary still won in the end, just not by as much.   ;  Ok, good to know :)Maybe the C5 library has something that could be of use here.   ;  I'd like to point out that some basic knowledge of data structures, plus the implementation notes on MSDN, would have told you exactly the same things without having to cook up half baked and unreliable benchmarks. Benchmarking and profiling can be effective, but start from a theoretical grounding first.   ;  I think I put too much focus on the 5 second benchmarking (if you can even call it that) I did before breaking out into a 2 day research that eventually lead me to here to ask a question, lol.My true question, I guess, is what is the best structure for a key value pair (with very fast lookup time) that also allows easy and quick access based on index as well?Because, basically, I haven't been able to come up with conclusive results - I am sure if I kept looking/reading I would find something, but felt it just quicker to ask in the off chance someone might know and save me several hours of searching.   