4

I'm looking for a SortedBag implementation for C#, my use case is the following: I have a series of objects that are being estimated and sorted out using custom IComparer implementation, the problem is that totally different objects may yield to the same estimate, and when I'm trying to use C#'s default sorted collections such as SortedSet, SortedDictionary implementations, I'm unable to insert several objects to these collections with the same estimate because collections consider these objects equal and refuse to insert them. I need a SortedBag implementation that has O(log(N)) for insertion and removal since I'm doing inserts/removals pretty actively.

Has anyone stumbled upon such implementation?

Thank you!

Edit

It seems that I was looking for Priority Queue not the SortedBag...

Community
  • 1
  • 1
Lu4
  • 14,873
  • 15
  • 79
  • 132
  • 1
    having sorting kinda invalidates the concept of a bag. – Daniel A. White Aug 28 '13 at 16:30
  • 1
    @DanielA.White No it doesn't... – Servy Aug 28 '13 at 16:30
  • You could dig out the source for a `SortedSet` implementation and simply modify it slightly to handle duplicates. There should already be a case to check for duplicates. If the order among duplicates can be undefined just remove that check and voila, you have a `SortedBag`. – Servy Aug 28 '13 at 16:33
  • Does [Lookup](http://msdn.microsoft.com/library/bb460184.aspx) do what you want? – Corak Aug 28 '13 at 16:33
  • 4
    `SortedDictionary>` may be enough - lookup by key first, than append to list if already there... – Alexei Levenkov Aug 28 '13 at 16:39
  • @AlexeiLevenkov or `SortedDictionary>` if you are not going to have items that evaluate true to `Equals(...)` sharing the same key. – Scott Chamberlain Aug 28 '13 at 16:56
  • Yes, Scott, you are right, also I don't have any key, the object itself is a key... – Lu4 Aug 28 '13 at 20:05
  • duplicate: [is-there-a-sortedlistt-class-in-net-not-sortedlistkey-value](http://stackoverflow.com/questions/389813/is-there-a-sortedlistt-class-in-net-not-sortedlistkey-value-which-is-act) – nawfal May 21 '14 at 20:25

1 Answers1

7

The TreeBag<T> from the The C5 Generic Collection Library should be O(log(n)) both in insert and in remove, otherwise there is the Wintellect's Power Collections for .NET with its OrderedBag<T>.

xanatos
  • 109,618
  • 12
  • 197
  • 280