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

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)

Answer 3

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 4

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 5

Old question, but I may have just stumbled across an acceptable solution. I use a combination of TryGetValue, ternary operator and index assignment.

var thing = _dictionary.TryGetValue(key, out var existing) ? existing : _dictionary[key] = new Thing(); 

I have written a small example for that.

class Program
{
    private static readonly Dictionary<string, string> _translations
        = new Dictionary<string, string>() { { "en", "Hello world!" } };

    private static string AddOrGetTranslation(string locale, string defaultText)
        => _translations.TryGetValue(locale, out var existingTranslation)
            ? existingTranslation
            : _translations[locale] = defaultText;

    static void Main()
    {
        var defaultText = "#hello world#";

        Console.WriteLine(AddOrGetTranslation("en", defaultText)); // -> Hello world!

        Console.WriteLine(AddOrGetTranslation("de", defaultText)); // -> #hello world#
        Console.WriteLine(AddOrGetTranslation("de", "differentDefaultText")); // -> #hello world#

        _translations["de"] = "Hallo Welt!";
        Console.WriteLine(AddOrGetTranslation("de", defaultText)); // -> Hallo Welt!
    }
}

EDIT: ⚠️ There is an uncertainty of this solution. See comments on the solution.

Answer 6

You can create extension method for that:

IDictionary<string, Point> _dictionary = GetDictionary();
_dictionary.GetOrAdd( "asdf" ).Add( new Point(14, 15) );

// ... elsewhere ...
public static class DictionaryExtensions {
    public static List<TValue> GetOrAdd<TKey, TValue>( this IDictionary<TKey, List<TValue>> self, TKey key ) {
        List<TValue> result;
        self.TryGetValue( key, out result );
        if ( null == result ) {
            // the key value can be set to the null
            result = new List<TValue>();
            self[key] = result;
        }

        return result;
    }
}