IndexOf too slow on list. Faster solution?

Question

I have generic list which must be a preserved order so I can retrieve the index of an object in the list. The problem is IndexOf is way too slow. If I comment the IndexOf out, the code runs fast as can be. Is there a better way, such as a preserved ordered hash list for c#?

Thanks, Nate

• Edit - The order in which the items are added/inserted is the order it needs to be. No sorting on them is necessary. Also this list has the potential to be updated often, add, remove, insert. Basically I need to translate the object to an index due to them being represented in a grid control so I can perform operations on the grid control based on index.

Answer 1

If it's not sorted, but the order needs to be preserved, then you could have a separate Dictionary<YourClass, int> which would contain the index for each element.

If you want a sorted list, then check previous posts - you can use SortedList<Tkey, TValue> in .Net 3.5, or sort it and use BinarySearch in older .Net versions.

[Edit] You can find similar examples on the web, e.g.: OrderedList. This one internally uses an ArrayList and a HashTable, but you can easily make it generic.

[Edit2] Ooops.. the example I gave you doesn't implement IndexOf the way I described at the beginning... But you get the point - one list should be ordered, the other one used for quick lookup.

Answer 2

Sort it using List<T>.Sort, then use the List<T>.BinarySearch method: "Searches the entire sorted List(T) for an element [...] This method is an O(log n) operation, where n is the number of elements in the range."