5

I'm looking for .Net class, which will basically:

  • Ensure that items are unique in it(like an HashSet)
  • Ensure that when we enumerate, we get items in the same order than we inserted them(Like a List)

Is there an existing .Net class that does this?

I'm aware of the HashSet(which doesn't guarantee the order), the SortedSet(which order on the content), but they don't match my need. I don't have any other needs(like a Stack or a Queue).

My current alternative is to have a List<> and use the Contains(...) before Adding and Removing data.

J4N
  • 19,480
  • 39
  • 187
  • 340
  • Hvae you tried `Dictionary`, particulary at `SortedDictionary`? It would kind of a hack, but will fulfill your needs – Vsevolod Goloviznin Dec 05 '14 at 08:27
  • @VsevolodGoloviznin Yes but I don't really have any key to specify(and I'm not sure that a `Dictionary` guarantee any order on enumeration. – J4N Dec 05 '14 at 08:28
  • you will insert keys (that will be your values from the list) and value can be anything random. Oh, I mean not `SortedDictionary` but `OrderedDictionary` – Vsevolod Goloviznin Dec 05 '14 at 08:41

2 Answers2

5

You are right. HashSet do not preserve the insertion order.

Stackoverflow: HashSet that preserves ordering by achitaka-san It uses the Dictionary to look up items and the LinkedList to preserve order. All three insertion, removal and lookup work still in O(1).

public class OrderedSet<T> : ICollection<T>
{
    private readonly IDictionary<T, LinkedListNode<T>> m_Dictionary;
    private readonly LinkedList<T> m_LinkedList;

    public OrderedSet()
        : this(EqualityComparer<T>.Default)
    {
    }

    public OrderedSet(IEqualityComparer<T> comparer)
    {
        m_Dictionary = new Dictionary<T, LinkedListNode<T>>(comparer);
        m_LinkedList = new LinkedList<T>();
    }

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

    public virtual bool IsReadOnly
    {
        get { return m_Dictionary.IsReadOnly; }
    }

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

    public bool Add(T item)
    {
        if (m_Dictionary.ContainsKey(item)) return false;
        LinkedListNode<T> node = m_LinkedList.AddLast(item);
        m_Dictionary.Add(item, node);
        return true;
    }

    public void Clear()
    {
        m_LinkedList.Clear();
        m_Dictionary.Clear();
    }

    public bool Remove(T item)
    {
        LinkedListNode<T> node;
        bool found = m_Dictionary.TryGetValue(item, out node);
        if (!found) return false;
        m_Dictionary.Remove(item);
        m_LinkedList.Remove(node);
        return true;
    }

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

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

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

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

Another implementation:

@Codeproject: HashSet that Preserves Insertion Order or .NET Implementation of LinkedHashSet

csauve
  • 5,904
  • 9
  • 40
  • 50
SteMa
  • 421
  • 6
  • 13
  • Yeah, I can imagine a lot of custom implementation to have this kind of behavior, my question was more to know if there is an existing official collection that could make this. – J4N Dec 05 '14 at 08:34
  • I do not know any official implementation. – SteMa Dec 05 '14 at 08:35
3

You can use an OrderedDictionary, documentation can be found here

You will use your values from your current List as keys in the dictionary and you can leave value as some randomness. 

OrderedDictionary myOrderedDictionary = new OrderedDictionary();
myOrderedDictionary.Add(1, "smth");
myOrderedDictionary.Add(2, "smth");

foreach (DictionaryEntry v in myOrderedDictionary)
{
    int youValue = (int)v.Key;
}

The only downfall here is that this dictionary doesn't use generics and you have to cast from object yourself.

Vsevolod Goloviznin
  • 12,074
  • 1
  • 49
  • 50