12

I'm doing a performance critical program (little academic stuff) and I'm looking to optimize wherever possible (not like it proved "this is the" bottleneck).

I have a custom dictionary structure (a wrapper around .NET Dictionary<,>) and I would constantly Remove items at one stage (by the Key value). I need the Value of the removed items. Right now I have to do:

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

Remove(key);

That's two lookups. I would love this:

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

I know there is nothing in the framework, but is there an implementation somewhere? If so I would change my backing dictionary with that one.

Edit: Hmm I know both TryGetValue and Remove are O(1). Just knowing if there is any collection structure that would give the same effect in just one lookup. As I said I'm trying to optimize as much as possible. Just knowing.

nawfal
  • 70,104
  • 56
  • 326
  • 368
  • 2
    Umm, both `Get` and `Remove` in the `Dictionary` have the amortized complexity of `O(1)`, so calling `Get` + `Remove` will still give you `O(1)`... – Patryk Ćwiek Apr 03 '13 at 10:41
  • 1
    Looks like I will have to write one my own.. – nawfal Apr 03 '13 at 10:46
  • Looks that way, there's nothing built-in that would return the removed item from the Dictionary. – Patryk Ćwiek Apr 03 '13 at 10:48
  • 2
    @nawfal Please run a profiler (or do your _own_ profiling) against your application to identify _real_ bottlenecks before rolling your own `Dictionary<,>` implementation. (alternatively, you can grab the [Mono Dictionary<,> implementation from its source code repository...](https://github.com/mono/mono/blob/master/mcs/class/corlib/System.Collections.Generic/Dictionary.cs)) – Chris Sinclair Apr 03 '13 at 10:56
  • @ChrisSinclair don't worry, if ever I'm writing my own I will get the original source first and build on it. Sure I will time too (that's always on the forefront of my thought) – nawfal Apr 03 '13 at 11:03
  • Closing the question with duplicate link. The original question has an answer today (.NET Core 2.0 onwards). – nawfal Jul 26 '20 at 07:39

3 Answers3

8

The ConcurrentDictionary has a TryRemove method that does this. It works just like TryGet but it also removes the element.

javaNinja
  • 521
  • 1
  • 5
  • 13
7

Dictionary<TKey, TValue>.TryGetValue and Dictionary<TKey, TValue>.Remove methods are both O(1) operations, so I don't think you should be concerned about performance here.

MarcinJuraszek
  • 124,003
  • 15
  • 196
  • 263
  • 5
    Sorry unfortunately this doesnt answer the question. May be I wasnt clear enough with my requirement. – nawfal Apr 03 '13 at 10:45
  • 24
    I basically agree, but `O(1)` doesn't say anything about the absolute time an operation takes. It just says something about how the execution time develops with a changing number of items. An operation that always takes 10 seconds is `O(1)` but still can be a very real performance problem. So, "O(1) = fast" is not always a legit conclusion. Having said that, optimizing arbitrary things without attaching a profiler first is premature optimization and a bad idea. – Daniel Hilgarth Apr 03 '13 at 10:47
  • @DanielHilgarth Absolutely, that's what I was thinking about (though .NET Dictionary is insanely fast). – nawfal Apr 03 '13 at 10:48
  • So you'll have to write something on your own (but I don't have an idea how it could be done on `Dictionary`, really). `Dictionary` is that fast, because it uses hashing for finding items within a set. That *O(1)* operation does just that - calculates `HashCode` and check if it's already set. – MarcinJuraszek Apr 03 '13 at 10:51
  • @MarcinJuraszek yes, but along with that, before the removal, I can `out` the `Value` back. I mean in a custom dictionary if I have to roll one myself. I'm not taking about the standard dictionary. – nawfal Apr 03 '13 at 11:05
6

The University of Copenehagen's Generic Collection Library has a Dictionary.Remove() method that appears to do what you want:

bool Remove(K k, out V v)

Returns true if the dictionary contains an entry whose key equals k and if so removes that entry and assigns the associated value to v; otherwise returns false and assigns the default value for T to v.

I've not used this library myself, but I've seen it recommended a few times here on Stack Overflow. It's free to use commercially, subject to this MIT-style license.

Matthew Watson
  • 104,400
  • 10
  • 158
  • 276