Updating all values in a C# keyed collection in O(n) time?

Question

This is a problem I have encountered again and again in C#, but haven't found a general solution. In C++/STL, all values in a map can be updated in O(n) time using an iterator without using keys to access each element. Is there a way to obtain similar behavior with any of the C# collections such as SortedList, SortedDictionary?

I can do something like

foreach (int key in list.Keys)
{
    list[key] *= 3;
}

But that would take O(n * log(n)) as the searching each element using key takes log(n).

Just to give an idea, I am looking for something along the lines of:

SortedList<int, double> list = new SortedList<int,double>();

// Add few values fist

// E.g. first try ...
IList<double> values = list.Values;
for (int i = 0; i < values.Count; i++)
{
    values[i] *= 3;
}

// E.g. second try
foreach (KeyValuePair<int, double> kv in list)
{
    kv.Value *= 3;
}

Since the List is already sorted it should be possible to traverse it updating values (not keys) at the same time. It doesn't look like there is a problem with that from the implementation point of view, but for some reason the functionality is not made available it seems.

Also this is not a trivial case as the same method can be used to iterate from a known position to another modifying values in that range.

Is there a way to do this in C# with any of the keyed collections in .NET without using 3rd party libraries?

Thank you

Jeeves

Answer 1

Simplest solution would be to wrap the value in a reference type.

class WrappedInt { public int Value; }
Dictionary<TKey, WrappedInt> dictionary = ...;
foreach (var wrappedVal in dictionary.Values)
{
    wrappedVal.Value *= 3;
}
// or 
foreach (var wrappedVal in dictionary)
{
    wrappedVal.Value.Value *= 3;
}

This approach would work with any collection (list or dictionary). One of the few collections that does this by design without the wrapper is LinkedList.

Of course, if you have a very specific collection (created by some external component), you can always fall back to using reflection and change the values directly in the underlying storage.