Find-or-insert with only one lookup in c# dictionary

Question

I'm a former C++/STL programmer trying to code a fast marching algorithm using c#/.NET technology...

I'm searching for an equivalent of STL method "map::insert" that insert a value at given key if not exists, else returns an iterator to the existing key-value pair.

The only way I found does this with two lookups : one inside TryGetValue and another one in Add method :

List<Point> list;
if (!_dictionary.TryGetValue (pcost, out list))
{
    list = new List<Point> ();
    dictionary.Add (pcost, list);
}
list.Add (new Point { X = n.x, Y = n.y });

Is there something that explains why this is not possible using .NET containers ? Or did I missed some point ?

Thanks.

Answer 1

You can just assign your value in the following way:

var dict = new Dictionary<int, int>();
dict[2] = 11;

if value with key 2 does not exist - it will be added and otherwise it will be just overriden.

Dictionary does not have method GetOrAdd, but ConcurrentDictionary from C# 4.0 does:

var dict = new ConcurrentDictionary<int, int>();
dict[2] = 10;
int a = dict.GetOrAdd(2, 11);// a == 10

Answer 2

The standard generic dictionary does not support this, the 2 lookups are required. Though the cost of the look ups are normally negligible so this isn't a problem, and you can often get better results tuning other parts of the system rather than trying to micro-optimise dictionary lookups.

The only dictionary that comes with .net that supports this that I know of is ConcurrentDictionary with the method GetOrAdd. Though now you're paying the cost of synchronization instead.

Answer 3

Is there something that explains why this is not possible using .NET containers ?

Without knowing the real background, I assume it is because of simplicity of the Dictionary. There are only the basic, easy to understand functions: Add, Remove a.s.o., while the index operator does a little bit of magic, which was probably assumed to be intuitive.

Answer 4

Sadly, there isn't one in bcl's implementation. The closest alternative is doing two lookups, but one can have a generic extension method to make it easy, as shown here

public static T GetOrAdd<S, T>(this IDictionary<S, T> dict, S key, 
                               Func<T> valueCreator)
{
    T value;
    return dict.TryGetValue(key, out value) ? value : dict[key] = valueCreator();
}

But there is C5's implementation which does this out of the box. The method definition looks like this:

public virtual bool FindOrAdd(K key, ref V value)
{

}

I don't know why they don't accept a Func<V> instead of V to defer object creation. C5 has a lot of nice similar tricks, for eg,

public virtual bool Remove(K key, out V value)

public virtual bool Update(K key, V value, out V oldvalue)

public virtual bool UpdateOrAdd(K key, V value, out V oldvalue)