Setting the i-th value of a SortedDictionary

Question

I need to set the value of an element in my sortedDictionary, accessed by index.

I.e.

sortedDictionary.Values[index] = value; // compile error

Note that the following is incorrect because it's accessed by key, not index.

sortedDictionary[index] = value; // incorrect

I came up with the following solution, but intuition tells me it's slow. I'm assuming that accessing by key is O(log N), and accessing by index is O(1), but I'm not certain.

sortedDictionary[sortedDictionary.ElementAt(index).Key] = value;

Some background:

I'm using SortedDictionary because I need fast inserts, deletes, lookups, and to be able to access neighbor elements. (i.e. next highest or next lowest.) Efficiency is important.

Answer 1

It's a bit of a trade off.

You could use a SortedList and get faster index lookup, but you would be sacrificing the insert speed.

To quote MSDN:

...Another difference between the SortedDictionary<(Of <(TKey, TValue>)>) and SortedList<(Of <(TKey, TValue>)>) classes is that SortedList<(Of <(TKey, TValue>)>) supports efficient indexed retrieval of keys and values through the collections returned by the Keys and Values properties. It is not necessary to regenerate the lists when the properties are accessed, because the lists are just wrappers for the internal arrays of keys and values.

Both SortedDictionary and SortedList implemented IDictionary, so I would get some test data and a code profiler together and try both.

If neither are fast enough, you might need to start thinking of using a Dictionary (fast inserts, updates and key lookup) and manually maintaining an index in a second data structure.