2

I need a built-in datastructure in C# that has functionality similar to std::set (or std::map) in c++. What is important to me is that the structure should be sorted(thus Dictionary will not do here) and has a method similar to lower_bound(i.e. return first element with value at least v). I will also need to insert and delete elements from the structure. If possible I need these operations to have complexity O(log(n)). Could you please point me to the appropriate datastructure in C#?

Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • 1
    @Mankarse by the way the question is not exactly duplicate because it assumes one has already heard of SortedSet, while I only heard of it as a result of this question – Ivaylo Strandjev Mar 30 '13 at 13:30
  • I agree, but I think that the questions are similar enough that their answers could be merged (as any answer to one will naturally answer the other). – Mankarse Mar 30 '13 at 13:32

1 Answers1

2

I suspect you are looking for SortedSet in terms of a similar data structure to std::set.

This article goes into its performance characteristics.

A lower_bound functionality seems to be possible using SortedSet.GetViewBetween but has a worse complexity than the desired O(log(n)) according to this discussion.

Community
  • 1
  • 1
Simon Opelt
  • 6,136
  • 2
  • 35
  • 66
  • could you please point me to a way to achieve lower_bound like functionality with it? – Ivaylo Strandjev Mar 30 '13 at 13:22
  • Sorry, i misread the functionality of lower_bound in that context. http://stackoverflow.com/questions/9850975/why-sortedsett-getviewbetween-isnt-olog-n seems to be related to what you are trying to to (but does not look to promising in terms of getting the functionality within the BCL in O(log(n))). – Simon Opelt Mar 30 '13 at 13:27
  • @IvayloStrandjev use .GetViewBetween() on the SortedSet, or the .First() methond (.First() is a linq extension) – nos Mar 30 '13 at 13:27
  • @SimonOpelt take a look at the question linked to as duplicate by Mankrese seems a lower bound can be done using a binary search on the keys. – Ivaylo Strandjev Mar 30 '13 at 13:29
  • @nos what would be the complexity of this method? – Ivaylo Strandjev Mar 30 '13 at 13:29
  • 1
    Please include the relevant information in the actual answer and only use links to back up your answer. – ChrisF Mar 30 '13 at 13:31
  • damn, only from C# 4 :'( – v.oddou Jun 11 '13 at 06:36
  • `GetViewBetween` is indeed really good. .NET doesn't expose the lower/upper bound as iterators directly, but as a subtree of the whole tree. This model is in line with Java's `SortedMap` and `TreeMap`. So no problem here. As to the issue `GetViewBetween` being O(n), it's really tragic. But as a comment in your link points out, Mono & .NET core does have O(logn) implementation for this method. – KFL Jan 27 '18 at 03:56