An ordered set in C#

Question

I need a generic data structure that ensures that its elements are unique. C# has HashSet<T>, great!

As it turns out, the elements have to stay in the order in which they were added, too. This sounds more like List<T>.

I tried to create my own:

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

namespace Collections.Generic
{
    public class HashSetList<T> : IList<T>
    {
        private List<T> _list;
        private HashSet<T> _set;

        public HashSetList()
        {
            _list = new List<T>();
            _set = new HashSet<T>();
        }

        public int IndexOf(T item)
        {
            return _list.IndexOf(item);
        }

        public void Insert(int index, T item)
        {
            if (_set.Add(item))
            {
                _list.Insert(index, item);
            }
        }

        public void RemoveAt(int index)
        {
            _set.Remove(_list[index]);

            _list.RemoveAt(index);
        }

        public T this[int index]
        {
            get
            {
                return _list[index];
            }
            set
            {
                if (_set.Add(value))
                {
                    _list[index] = value;
                };
            }
        }

        public void Add(T item)
        {
            if (_set.Add(item))
            {
                _list.Add(item);
            }
        }

        public void Clear()
        {
            _list.Clear();
            _set.Clear();
        }

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

        public void CopyTo(T[] array, int arrayIndex)
        {
            _list.CopyTo(array, arrayIndex);
        }

        public int Count
        {
            get 
            { 
                return _list.Count; 
            }
        }

        public bool IsReadOnly
        {
            get 
            {
                return false;
            }
        }

        public bool Remove(T item)
        {
            _set.Remove(item);
            return _list.Remove(item);
        }

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


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

It's an IList<T> wrapper that delegates method calls of the interface to a List<T> member with an additional HashSet<T> to ensure the uniqueness.

One problem is that it somewhat breaks the IList<T> interface. It's always possible to successfully call Add(T item) on a IList<T>, which is why that method returns void. But my HashSetList<T> rejects elements it already contains. In this regard, it's more like a ISet<T>, which returns bool if the operation was successful or not.

Then why implement IList<T> only? It's an ISet<T> after all, right? Well, yes and no. This is where the problem lies: The two interfaces IList<T> and ISet<T> are incompatible because their Add(T item) methods have incompatible "signatures".

By "signatures" I mean that their signatures are actually the same, because afaik in C# land the return type is not part of the signature. However, the interfaces demand different return types, which means they both have to be implemented, which in turn creates an invalidly overloaded Add(T item) method that is not distinguishable from each other. (singular/plural pun intended)

Should HashSetList<T> implement ISet<T> instead of IList<T>? (I omit its code for brevity)

That would allow code to branch based on the success of the Add(T item) method like so:

 if (orderedSet.Add(foo))
 {
     //added now
 }

vs

 orderedSet.Add(foo);
 if (orderedSet.Contains(foo))
 {
     //added now or already present before
 }

The disadvantage would be that operations one would expect from an ordered data structure, especially those with read/write access via index would be gone. At least in terms of an implemented interface.

Which interface should I choose? Or should I create two classes OrderedSet and UniqueList each implementing either one?

Answer 1

From the technical point of view you could implement both interfaces at the same time but you'd have to implement the Add method explicitly and without repeating yourself it would go like this:

void ICollection<T>.Add(T item)
{
    ((ISet<T>)this).Add(item);
}

bool ISet<T>.Add(T item)
{
    if (_set.Add(item))
    {
        _list.Add(item);
        return true;
    }
    return false;
}

Which leads to one issue in your code namely the indexer repeats the insertion. You should use the insert method here:

public T this[int index]
{
    get
    {
        return _list[index];
    }
    set
    {
        Insert(index, value);
    }
}

Answer 2

You can always add more guarantees, but you should never take them away. This is much better as a Set with the additional property of maintaining insertion order, rather than a List that breaks the spec.

Answer 3

Should HashSetList implement ISet instead of IList?

In my eyes definitely YES!

Some of the IList members doesn't make sense in combinations with a set.

For example:

IList<int> set = new HashSetList<int>();
set.Add(1);
set[0] = 2;
// set[0] remains 1!

I am fine with a set that preserves the order of insertion by implementing ISet with a customized IEnumerable-implementation (something like OrderedSet). Whereas, an UniqueList doesn't make sense for me because it would not behave like a list (see also Liskov Substitution Principle).

Answer 4

Because you don't validate method parameters of your public methods you are leaking implementation details of your class. The user of your class shouldn't know which kind of underlaying datastructure you are using.

Let's take e.g RemoveAt(int):

Calling this method with an index > _list.Count will result in an ArgumentOutOfRangeException with the stacktrace

StackTrace:
at System.ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument argument, ExceptionResource resource)
at System.Collections.Generic.List`1.get_Item(Int32 index)

hence its exposing that you are using aList<T>.

Sure you can say, hey I implement IList<T> that is what expected to be seen here. But if you, like correctly suggested, implement a ISet<T> then it wouldn't be that good if you are leaking the usage of the List<T>.

---

private List<T> _list;
  private HashSet<T> _set;  

does this need to be a List<T> and a HashSet<T> ? I don't think so because you aren't using specific methods of this objects. You should declare them as IList<T> and ISet<T>. You should code against interfaces not implementations.

In addition, by making these variables readonly your code will become more robust.

---

Answer 5

I like the idea of adding guaranteers instead of taking them away.

But to chicane a little bit to the current solution:

public bool Remove(T item)
{
    _set.Remove(item);
    return _list.Remove(item);
}

Looks like you can make it faster if you only remove an item from the list when you successfully remove this item from the set:

public bool Remove(T item)
{
    return _set.Remove(item)
        ? _list.Remove(item)
        : false;    
}

Also,

if (_set.Add(value))
{
    _list[index] = value;
};

You do not need a semicolon here.

Answer 6

I think there's a worthwhile compromise where you implement ISet<T> and IReadOnlyList<T>. This exposes the ordering efficiently (a caller can get the nth item in constant time rather than time linear in n) without committing you to the mutating methods of List<T>.

Answer 7

I believe requirements around the contract should be more specific as well. Is there a reason why you expose all the members defined in IList or ISet or both?

How about defining an interface as below assuming these members are what your caller will need:

public interface IOrderedSet<T> : IEnumerable<T> where T : IEquatable<T>
{
    long Count { get; }

    void Add(T item);

    void AddRange(IEnumerable<T> items);

    bool Remove(T item);
}

As you can see the implementation of above will offer the caller LINQ capabilities. I've added the IEquatable constraint for a better control over items' "uniqueness", however, it's a minor detail for now.

Following is the implementation:

public class OrderedSet<T> : IOrderedSet<T> where T : IEquatable<T>
{
    private readonly HashSet<T> _lookup = new HashSet<T>();
    private readonly LinkedList<T> _elements = new LinkedList<T>();

    public long Count => _lookup.Count;

    public OrderedSet(IEnumerable<T> collection = null)
    {
        if (collection != null)
        {
            AddRange(collection);
        }
    }

    public void Add(T item)
    {
        if (_lookup.Contains(item)) return;

        _elements.AddLast(item);
        _lookup.Add(item);
    }

    public void AddRange(IEnumerable<T> items)
    {
        foreach(var item in items)
        {
            Add(item);
        }
    }

    public bool Remove(T item)
    {            
        if (_lookup.Contains(item))
        {
            _lookup.Remove(item);
            _elements.Remove(item);

            return true;
        }

        return false;
    }

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

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

The choice of the underlying collection depends on the use case which your contract should reflect. For instance if you need an item by an index than List is a better fit. However, LinkedList semantics makes more sense keeping the initial assumption around the contract in mind.

Here are some tests covering a few cases:

[TestFixture]
public class OrderedSetTests
{
    [Test]
    public void AddRange_InsertsItem()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };

        list.AddRange(items);

        Assert.AreEqual(7, list.Count);
        CollectionAssert.AreEqual(items, list);
    }

    [Test]
    public void AddRange_IgnoresDuplicateInput()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };
        var items2 = new List<int> { 1, 2, 3, 4, 5, 6, 7, 7, 6, 6, 3 };            

        list.AddRange(items2);

        CollectionAssert.AreEqual(items, list);
    }

    [Test]
    public void Remove_RemovesItemIfItemExists()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };
        list.AddRange(items);
        var removed = list.Remove(3);
        Assert.IsTrue(removed);
        removed = list.Remove(1);
        Assert.IsTrue(removed);

        Assert.AreEqual(5, list.Count);
        CollectionAssert.AreEqual(new[] { 2, 4, 5, 6, 7 }, list);
    }

    [Test]
    public void Remove_IgnoresItemIfItemDoesNotExist()
    {
        var list = new OrderedSet<int>();

        var items = new[] { 1, 2, 3, 4, 5, 6, 7 };
        list.AddRange(items);
        var removed = list.Remove(9);
        Assert.IsFalse(removed);
        removed = list.Remove(11);
        Assert.IsFalse(removed);

        Assert.AreEqual(7, list.Count);
        CollectionAssert.AreEqual(items, list);
    }
}