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#?
Asked
Active
Viewed 3,020 times
2
Ivaylo Strandjev
- 66,530
- 15
- 117
- 170
-
@Mankarse thanks for this link – Ivaylo Strandjev Mar 30 '13 at 13:24
-
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 Answers
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,046
- 2
- 34
- 63
-
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
-
-
1Please include the relevant information in the actual answer and only use links to back up your answer. – ChrisF Mar 30 '13 at 13:31
-
-
`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