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?
IList
really is a very broad interface. It's often impractical to fulfill it's entire contract. Make a practical decision. API users likely want to use your class as an IList so give it to them and document where the abstraction leaks. \$\endgroup\$ – usr Jun 15 '16 at 20:45