Is there an implementation of IList <T> where Contains (T) is an O (1) operation?

Question

I am wondering if there is an implementation IList<T>that is supported by a hash, for example HashSet<T>, but offers indexed access?

To be clear, I'm not interested in how to implement it, just wondering if anyone knows if it's already available.

Answer 1

You can implement it IList<T>yourself and save two support collections - a List<T>and a HashSet<T>. Basically, for Visual Studio to provide an “exception exception” implementation for everything in IList<T>, then for each method, find out if you want to proxy it in a list or in a set.

Of course, you have to be careful with duplicates, etc. (define behavior Add(x), Add(x), Remove(x), Contains(x)- you can be on the list but not in the set) but it would not be too difficult.

Answer 2

There is a new class in .NET 4 SortedSet<T>where Contains()- O (1), see this MSDN page

Answer 3

- , .

, , , . , , . , O (1), O (1). , , , .

: Set ( Map) List, , , , .

Answer 4

KeyedCollection<TKey, TItem> , , .

Answer 5

You can have any number of indexes (hashed or otherwise) in double-connected nodes (double-bound, so you can remove O (1)).

Answer 6

In .Net 3.5 it is not. But it is very easy to implement:

public class Set<T> : KeyedCollection<T,T>
{
    public Set()
    {}

    public Set(IEnumerable<T> collection)
    {
        foreach (T elem in collection)
        {
            Add(elem);
        }
    }

    protected override T GetKeyForItem(T item)
    {
        return item;
    }
}

Answer 7

HashSet <T> implements ICollection<T>, if used. Available from 3.5.