Re: Efficient Data Structures

Curious wrote: 
I am searching for a data structure that stores key-value pairs in it.
This data structure is to hold large amounts of key-value pairs, and so
needs to be efficient both in insertion and deletion.

Does anybody know of ready data structures that can be freely used
under the .Net framwork.

Also: 
I forgot to mention, that the data needs to be maintained sorted.
When removing the data, the minimum key with its data is to be removed.

You won't *necessarily* get great efficiency on both insertion and removal. But given your description so far it sounds as if you can - I would try a SortedList. The insertion uses .Add(object key, object value) - which *should* be efficient, at least if the key elements arrive in anything like random order. (Test it!) You can remove elements either with .Remove(object key) or ..RemoveAt(int index) - index being 0 in your case of removing the element with least key. Either of these *should* be quite efficient (O(log n) at worst) *if* the list is internally maintained sorted as per the documentation. (Again, test it!)

HTH,
-rick-
.

Relevant Pages

  • Re: Efficient Data Structures
    ... I agree with the others that the Red/Black tree should be easy to fix, and the SortedList will probably do what you want, too. ... This data structure is to hold large amounts of key-value pairs, and so needs to be efficient both in insertion and deletion. ... When removing the data, the minimum key with its data is to be removed. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Intervals tree
    ... I'm looking for a data structure to handle intervals (numeric range ... deleted and queries about intersecation are required. ... implementation seems not to allow insertion and deletion. ...
    (comp.graphics.algorithms)
  • Re: Efficient Data Structures
    ... > This data structure is to hold large amounts of key-value pairs, ... > needs to be efficient both in insertion and deletion. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: lxml/ElementTree and .tail
    ... Stefan Behnel wrote: ... What other API do you know where removing an element from a data structure ...
    (comp.lang.python)