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,632 times
2

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 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,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
-
-
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