在 C# 字典中仅通过一次查找查找或插入

Question

我是一名前 C++/STL 程序员，尝试使用 C#/.NET 技术编写快速行进算法...

我正在寻找 STL 方法

map::insert

的等效方法，如果不存在，则在给定键处插入一个值，否则返回一个迭代器到现有的键值对。

我发现的唯一方法是通过两次查找来做到这一点：一个在

TryGetValue

内部，另一个在

Add

方法中：

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

是否有什么可以解释为什么使用 .NET 容器不可能做到这一点？或者我错过了什么？

Answer 1

您可以通过以下方式分配您的价值：

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

如果带有键 2 的值不存在 - 它将被添加，否则它将被覆盖。

Dictionary 没有方法 GetOrAdd，但是 C# 4.0 中的 ConcurrentDictionary 有：

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

Answer 2

标准通用字典不支持这个，需要2次查找。虽然查找的成本通常可以忽略不计，所以这不是问题，而且您通常可以通过调整系统的其他部分而不是尝试微优化字典查找来获得更好的结果。

据我所知，.net 附带的唯一支持此功能的词典是 ConcurrentDictionary，其方法为 GetOrAdd。尽管现在您要支付同步费用。

Answer 3

有什么可以解释为什么 使用 .NET 是不可能的 容器 ?

在不知道真实背景的情况下，我认为这是因为词典的简单性。只有基本的、易于理解的功能：

Add

、

Remove

a.s.o.，而索引运算符有一点魔法，这可能被认为是直观的。

Answer 4

遗憾的是，bcl 的实现中没有。最接近的替代方法是进行两次查找，但可以使用通用扩展方法来简化查找，如此处所示

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

但是有 C5 的实现 开箱即用。方法定义如下所示：

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

}

我不知道他们为什么不接受

Func<V>

而不是

V

来推迟对象创建。 C5 有很多不错的类似技巧，例如，

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 5

从 .NET 6 开始，现在可以为

GetOrAdd

 类实现一个 

Dictionary<TKey, TValue> 扩展方法，它接受一个

key

和一个

valueFactory

，并且只对密钥进行一次哈希处理。新的 API 是

CollectionsMarshal.GetValueRefOrAddDefault

方法，具有以下签名：

// 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);

这是一个

ref

的返回方法。它可以用来实现像这样的

GetOrAdd

：

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

用法示例：

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

在线演示，还具有泛型参数重载

TArg

.

需要实现中的 try/catch 以删除空条目，以防

valueFactory

抛出异常。否则异常将使字典处于损坏状态（包含具有

default

值的键）。

Btw 在 GitHub 上提交了在标准 .NET 库中添加此方法的提案，但它没有产生足够的牵引力，因此被关闭了。

Answer 6

老问题，但我可能只是偶然发现了一个可接受的解决方案。我结合使用了 TryGetValue、三元运算符和索引赋值。

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

我为此写了一个小例子。

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

编辑：⚠️这个解决方案存在不确定性。查看解决方案的评论。

Answer 7

您可以为此创建扩展方法：

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