有没有同时实现按键删除和获取值的方法？

Question

我正在编写一款性能关键的程序（不是很学术），并且我正在寻找尽可能优化的方法（并不像证明“这是”瓶颈）。

我有一个自定义的字典结构（.NET Dictionary<,>的包装器），并且在某个阶段我需要不断地删除项目（按Key值）。我需要已删除项的Value。目前我需要执行以下操作：

T t;
if !TryGet(key, out t)
   return false;

Remove(key);

这需要进行两次查找。我希望可以做到以下简化：

public bool Remove(S key, out T value)
{
    // implementation
}

我知道框架中没有相关实现，但是是否有其他地方有这方面的实现呢？如果有的话，我会用那个字典替换我的后备字典。

编辑： 嗯，我知道TryGetValue和Remove都是O（1）的。只是想知道是否有任何集合结构可以在一次查找中达到同样的效果。就像我说的，我正在尽可能地优化。只是想知道。

- nawfal

---

嗯，Dictionary 中的 Get 和 Remove 都具有摊销复杂度为 O(1)，因此调用 Get + Remove 仍将给您提供 O(1)... - Patryk Ćwiek

看起来我不得不自己写一个... - nawfal

看起来是这样，没有内置的方法可以返回从字典中删除的项。 - Patryk Ćwiek

@nawfal 在自己实现 Dictionary<,> 之前，请运行分析器（或进行自己的分析）来识别真正的瓶颈。 （或者，您可以从其源代码存储库中获取 Mono Dictionary<,> 实现...) - Chris Sinclair

@ChrisSinclair 不用担心，如果我写自己的代码，我会先获取原始源代码并在此基础上进行开发。当然，时间也是我的首要考虑因素。 - nawfal

使用重复链接关闭问题。原始问题今天已有答案（.NET Core 2.0及以上版本）。 - nawfal

Answer 1

ConcurrentDictionary有一个TryRemove方法可以实现此功能。它的工作方式与TryGet相同，但它还会删除元素。

- javaNinja

Answer 2

Dictionary<TKey, TValue>.TryGetValue 和 Dictionary<TKey, TValue>.Remove 方法都是 O(1) 操作，所以我认为你不需要担心性能问题。

- MarcinJuraszek

---

抱歉，很遗憾这并没有回答问题。也许我的要求表述不够清楚。 - nawfal

我基本上同意，但 O(1) 并不能说明操作所需的绝对时间，它只说明了随着项目数量的变化执行时间如何发展。一个始终需要10秒的操作是 O(1) 但仍然可能是性能问题。因此，“O(1) = 快速”并不总是正确的结论。话虽如此，在使用分析器之前对任意事物进行优化都是过早的优化和不好的想法。 - Daniel Hilgarth

@DanielHilgarth 当然，这正是我所考虑的（尽管.NET字典非常快）。 - nawfal

所以你必须自己编写一些代码（但我真的不知道如何在“字典”上完成它）。 “字典”之所以快速，是因为它使用哈希来查找集合中的项。这个*O(1)*操作只是计算HashCode并检查它是否已经设置。 - MarcinJuraszek

@MarcinJuraszek 是的，但在删除之前，我可以把Value用 out 退回。我的意思是，如果需要自己创建一个自定义字典。我不是说标准字典。 - nawfal

Answer 3

哥本哈根大学通用集合库提供了Dictionary.Remove()方法，看起来可以满足你的需求:

bool Remove(K k, out V v)

如果字典包含一个键等于k的条目，则返回true， 并移除该条目并将关联值分配给v； 否则返回false，并将T类型的默认值分配给v。

我自己没有使用过这个库，但是我在Stack Overflow上看到过几次推荐。它可以免费商业使用，但需要遵守MIT-style许可证。

- Matthew Watson

---

你做了什么样的搜索才找到这个？谢谢 :) - nawfal

我有一个很久以前的旧书签，最近终于想起来了。 :) - Matthew Watson

我刚刚查看了源代码，它们确实完全符合我的要求。我的意思是单次查找。 - nawfal