collection without duplicates but with order, with fast containment check and adding/removing

Question

I am looking for a collection that has fast containment check and adding/removing methods (like HashSet<T>, approaching O(1) if T is implemented well), but that also has an order. That does not mean indexed access - it merely means that if I iterate over it, the order of elements is the same as the order in which I added them.

Is there something like that in C#? Does HashSet<T> even do the trick? (I couldn't find that info on MSDN, I checked HashSet<T> and HashSet<T>.GetEnumerator.)

If not, I was thinking of implementing it with a class that contains an internal HashSet<T> and an internal LinkedList<T>. The HashSet<T> would expose the adding, removing and containment check while the LinkedList<T> would expose the enumerator.

Your proposed implementation would have O(n) removal of items, not O(1). — Servy, Oct 06 '17 at 15:28
[OrderedDictionary](https://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx) is an option. — Blorgbeard, Oct 06 '17 at 15:30
Also related: https://stackoverflow.com/questions/1552225/hashset-that-preserves-ordering — Blorgbeard, Oct 06 '17 at 15:32

Tiago Sousa · Accepted Answer · 2017-10-06T15:53:28.460

0

It seems that you are looking for the OrderedDictionary.

The only downside is that it doesn't support generics, but you can easily make a wrapper around it or just cast the values to the type you need.

EDIT: as @Blorgbeard refered to in the comments, you can find an implementation of an "OrderedSet" in another answer that meets your exact requirements (and implements this exactly with a LinkedList<T> and HashSet<T>), that might be useful to you.

Here is their implementation (credits go to the original author, not me)

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);
    }
}

edited Oct 06 '17 at 15:53

answered Oct 06 '17 at 15:30

Tiago Sousa

953
5
14

That will have O(n) adding and removing. – Servy Oct 06 '17 at 15:34
@Servy Do you have any proof of your claim? You are only right for when you remove by key. For the others operations, it is O(1). – Tiago Sousa Oct 06 '17 at 15:39
For adding an item it requires searching through an array list for the index of the keypair, which is an O(n) operation. You can look at the source code to see for yourself. Do you have any proof for your claim that it's O(1)? – Servy Oct 06 '17 at 15:41
Add looks like O(1) (amortized) to me. Here's the source: https://referencesource.microsoft.com/#System/compmod/system/collections/specialized/ordereddictionary.cs,205 – Blorgbeard Oct 06 '17 at 15:41
I don't know what source code you are looking, but both `Add(object key, object value)` and `Insert(int index, object key, object value)` are O(1). As for removal, only removal by Key requires a search through the internal ArrayList to find the index of that key. I am using [Microsoft/referencesource](https://github.com/Microsoft/referencesource/blob/master/System/compmod/system/collections/specialized/ordereddictionary.cs) @ github to assert this. – Tiago Sousa Oct 06 '17 at 15:45
Sorry, I meant to say setting a value, not adding a new value. – Servy Oct 06 '17 at 15:45
@TiagoSousa Inserting into an arraylist is O(n), not O(1). – Servy Oct 06 '17 at 15:46
@Servy afaik, this only applies to when the operation exceeds the inner array capacity (where a new array needs to be allocated) or when insert is done in the middle of the array, which is not the case with the simple `Add(key, value)` or `Add(key)`, which is what the OP intended. I did mess up tho, and copied the `Insert` method, and not the other `Add` method. I cant seem to be able to edit my previous comment :/ – Tiago Sousa Oct 06 '17 at 16:01
@TiagoSousa Setting a value requires a linear search through the arraylist to find the index to set the value of that index. – Servy Oct 06 '17 at 16:03
1

And if you think another answer answers the question, you should be voting to close as a duplicate. Just repeating another answer verbatim isn't appropriate. – Servy Oct 06 '17 at 16:04
@Servy the other question does not mention OrderedDictionary, but it does seem like it is a dup, yes – Tiago Sousa Oct 06 '17 at 16:06

collection without duplicates but with order, with fast containment check and adding/removing

1 Answers1