32

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.)

1

4 Answers 4

30

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.

4
  • Thank you for explaining the penalty incurred in accessing a member of SortedSet via ElementAt(). Can you offer an answer to the question that is more efficient?
    – DavidRR
    Commented Dec 19, 2013 at 21:33
  • @DavidRR: see my amended answer. Commented Dec 19, 2013 at 21:46
  • 1
    In the spirit of the cost of code maintenance in the long term, many would argue that using a vendor's API directly is generally preferable to writing custom code, when the vendor's API meets the requirements. (Requirements can include runtime performance.) That said, one's code should certainly be documented to indicate the potential for degraded performance. Microsoft included Enumerable.ElementAt() for a reason...there are certainly occasions where it is convenient and ideal!
    – DavidRR
    Commented Dec 19, 2013 at 22:02
  • 2
    @DavidRR Yes, but I dont conceptually like ElementAt for IEnumerable<T>s since IEnumerable<T> doesn't enforce a certain order. For eg, methods like ElementAt, Last etc doesn't make sense for a HashSet<T>. Nevertheless, you can implement an IndexedSortedSet<T> to avoid the lookup penalty, but that would also mean you degrade Add and Remove performance.
    – nawfal
    Commented May 27, 2014 at 9:13
9

EDIT: An ordinary (unordered) set such as HashSet<T> manages its elements in no particular order. So, the index of a particular element in an unordered set does not carry any particular meaning.

In contrast however, it makes semantic sense to request an element by its position (index) in a SortedSet<T>. Why bother with the overhead of an ordered collection, otherwise?

That said, for a small SortedSet<T> where performance is not a concern (see example below), the Linq extension method Enumerable.ElementAt() provides a convenient means of retrieving an item by its index. However, for a large SortedSet<T> where the runtime performance of retrieving an element is paramount, consider implementing a custom collection as @Nicholas Carey outlines in his answer.


Original Answer:

You can access an item of interest by its index (position) from your SortedSet via the Enumerable.ElementAt<TSource> method:

var item = mySortedSet.ElementAt(index);

Demonstration:

using System;
using System.Collections.Generic;
using System.Linq;

class SortedSetDemo
{
    static void Main(string[] args)
    {
        var words = new string[]
            {"the", "quick", "brown", "fox", "jumps",
             "over", "the", "lazy", "dog"};

        // Create a sorted set.
        var wordSet = new SortedSet<string>();
        foreach (string word in words)
        {
            wordSet.Add(word);
        }

        // List the members of the sorted set.
        Console.WriteLine("Set items in sorted order:");
        int i = 0;
        foreach (string word in wordSet)
        {
            Console.WriteLine("{0}. {1}", i++, word);
        }

        // Access an item at a specified index (position).
        int index = 6;
        var member = wordSet.ElementAt(index);

        Console.WriteLine("\nThe item at index {0} is '{1}'!", index,
                          member);
    }
}

Expected Output:

The set items in sorted order is:
0. brown
1. dog
2. fox
3. jumps
4. lazy
5. over
6. quick
7. the

The item at position 6 is 'quick'!
2

If you intend to load the data into a set, then access the set, use HashSet and ImmutableSortedSet instead of SortedSet.

Load your data into the HashSet, then call ToImmutableSortedSet() to convert to an immutable sorted set that can be indexed.

1

you can use MCollections which do insert, edit, remove, search and index lookup In O(Lg(N)) time, it uses BST and stores count of sub-nodes in each node to access the item at a specified index

1
  • 1
    This is really great library I was just looking for. Thanks for sharing. Commented May 24, 2020 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.