Is there any implementation to Remove by Key and get the Value at the same time? [duplicate]

Question

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.

Laniary

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)... – Sheep

Looks like I will have to write one my own.. – Laniary

Looks that way, there's nothing built-in that would return the removed item from the Dictionary. – Sheep

@Laniary 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...) – Jankey

@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) – Laniary

Closing the question with duplicate link. The original question has an answer today (.NET Core 2.0 onwards). – Laniary

Answer 1

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.

Mango

What kind of searching did you do to find that? Thanks :) – Laniary

I had an old bookmark from ages ago that I finally remembered about. :) – Mango

I just looked the source, and they do what I want exactly. I mean single lookup – Laniary

Answer 2

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

Langlois

Answer 3

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.

Encomiastic

Sorry unfortunately this doesnt answer the question. May be I wasnt clear enough with my requirement. – Laniary

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. – Decrescent

@DanielHilgarth Absolutely, that's what I was thinking about (though .NET Dictionary is insanely fast). – Laniary

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. – Encomiastic

@Encomiastic 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. – Laniary