Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Accessing the item at a specified index in a 'SortedSet'

How can I access the item at a specified index (position) in a SortedSet?

Unlike SortedList, SortedSet does not offer an Item property.

(Also, unlike SortedList, SortedSet enforces each of its members to be unique. That is, a SortedSet is guaranteed not to contain duplicates.)

like image 624
DavidRR Avatar asked Dec 19 '13 21:12

DavidRR


1 Answers

That's because a SortedSet has the semantics of a set and is not a List-like construct. Consequently, it does not implement IList (which give you the ability to address items by index via the Item property).

As noted by @DavidRR, you could use the Linq extension method Enumerable.ElementAt(). However, since the backing store of a SortedSet is a red-black tree -- a height-balanced binary tree, accessing an element by index via ElementAt() involves a tree walk — O(N), worst case and O(N/2) on the average, to get to the desired item. Pretty much the same as traversing a singly-linked list to access the Nth item.

So...for large sets, performance is likely to be poor.

If what you want is a unique collection that offers array-like semantics, why not roll your own IList<T> implementation that would enforce uniqueness, just as SorteSet<T> does (ignoring adds of elements that already exist in the colleciton). Use a List<T> as the backing store. Maintain it in sorted sequence so you can use a binary search to determine if the element being added already exists. Or, simply subtype List<T> and override the appropriate methods to get the semantics you want.

like image 109
Nicholas Carey Avatar answered Sep 25 '22 02:09

Nicholas Carey