Observable order set in .NET?

Question

I need a set that is order which they were added just like a list.

The set may also be observable.

Any built.in set like this in .NET 4?

Answer 1

As far as I know, there is no such type in .NET. I recently needed this and ended up implementing it myself; it's not that difficult.

The trick is to combine a Dictionary<T, LinkedListNode<T>> with a LinkedList<T>. Use the dictionary to query keys and values in O(1) time and the list to iterate in insertion-order. You need a dictionary instead of a set because you want to be able to call LinkedList<T>.Remove(LinkedListNode<T>) and not LinkedList<T>.Remove(T). The former has O(1) time complexity, the latter O(n).

Answer 2

It sounds like you need ReadOnly Queue. In .Net we have built in Queue class but there is no built in ReadOnly Queue. To make sure there is no Duplicate value you can use contains check

There is one Nuget package which has ImmutableQueue. Not sure if it can help you. This creates new Queue object everytime when Enqueue or Dequeue operation is done. https://msdn.microsoft.com/en-us/library/dn467186(v=vs.111).aspx

Answer 3

I guess you could use a SortedDictionary<> and a Dictionary<> together to do this.

Assuming that you are never going to do more than int.MaxValue insertions into the set, you can use an integer "sequence number" as a key into a SortedDictionary that keeps track of the inserted items in insertion order.

Alongside this you need to use a Dictionary to map items to the sequence number that was used to insert them.

Putting this together into a class and a demo program: (NOT THREAD SAFE!)

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

namespace Demo
{
    public sealed class SequencedSet<T>: IEnumerable<T>
    {
        private readonly SortedDictionary<int, T> items = new SortedDictionary<int, T>();
        private readonly Dictionary<T, int> order = new Dictionary<T, int>();

        private int sequenceNumber = 0;

        public void Add(T item)
        {
            if (order.ContainsKey(item))
                return; // Or throw if you want.

            order[item] = sequenceNumber;
            items[sequenceNumber] = item;
            ++sequenceNumber;
        }

        public void Remove(T item)
        {
            if (!order.ContainsKey(item))
                return; // Or throw if you want.

            int sequence = order[item];

            items.Remove(sequence);
            order.Remove(item);
        }

        public bool Contains(T item)
        {
            return order.ContainsKey(item);
        }

        public IEnumerator<T> GetEnumerator()
        {
            return items.Values.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

    internal class Program
    {
        private static void Main()
        {
            var test = new SequencedSet<string>();

            test.Add("One");
            test.Add("Two");
            test.Add("Three");
            test.Add("Four");
            test.Add("Five");

            test.Remove("Four");
            test.Remove("Two");

            foreach (var item in test)
                Console.WriteLine(item);
        }
    }
}

This should be fairly performant for insertions and deletions, but it will take double the memory of course. If you are doing a great number of insertions and deletions you could use a long instead of an int for the sequence numbering.

Unfortunately, if you are doing more than 2^63 deletions, even that won't work - although I would imagine that should be more than enough...