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?

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

Starting from .NET 6, it is now possible to implement a GetOrAdd extension method for the Dictionary<TKey, TValue> class that takes a key and a valueFactory, and hashes the key only once. The new API is the CollectionsMarshal.GetValueRefOrAddDefault method, with this signature:

// Gets a reference to a TValue in the specified dictionary, adding a new entry
// with a default value if the key does not exist.
public static ref TValue? GetValueRefOrAddDefault<TKey,TValue> (
    Dictionary<TKey,TValue> dictionary, TKey key, out bool exists);

This is a ref returning method. It can be used to implement the GetOrAdd like this:

/// <summary>
/// Adds a key/value pair to the dictionary by using the specified function
/// if the key does not already exist. Returns the new value, or the
/// existing value if the key exists.
/// </summary>
public static TValue GetOrAdd<TKey, TValue>(
    this Dictionary<TKey, TValue> dictionary,
    TKey key,
    Func<TKey, TValue> valueFactory)
{
    ArgumentNullException.ThrowIfNull(dictionary);
    ArgumentNullException.ThrowIfNull(valueFactory);

    ref TValue value = ref CollectionsMarshal
        .GetValueRefOrAddDefault(dictionary, key, out bool exists);
    if (!exists)
    {
        try { value = valueFactory(key); }
        catch { dictionary.Remove(key); throw; }
    }
    return value;
}

Usage example:

List<Point> list = dictionary.GetOrAdd(pcost, key => new List<Point>());
list.Add(new Point { X = n.x, Y = n.y });

Online demo, featuring also an overload with generic parameter TArg.

The try/catch in the implementation is required in order to remove the empty entry, in case the valueFactory throws an exception. Otherwise the exception would leave the dictionary in a corrupted state (containing a key with a default value).

Btw a proposal to add this method in the standard .NET libraries has been submitted on GitHub, but it didn't generate enough traction and it was closed.

Answer 6

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 7

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;
    }
}