Существует ли реализация IList <T>, где Contains (T) является операцией O (1)?

Question

Мне интересно, есть ли реализация IList<T>, которая поддерживается хешем вроде HashSet<T>, но предлагает индексированный доступ?

Чтобы было ясно, меня не интересует, как его реализовать, просто интересно, знает ли кто-нибудь, есть ли он уже в наличии.

Answer 1

Вы можете реализовать IList<T> самостоятельно и сохранить две резервные коллекции - List<T> и a HashSet<T>. По сути, заставить Visual Studio обеспечить реализацию «выбросить исключение» для всего в IList<T>, а затем для каждого метода определить, хотите ли вы передать его в список или набор.

Конечно, вы должны быть осторожны с дубликатами и т. Д. (Определите поведение Add(x), Add(x), Remove(x), Contains(x) - вы можете оказаться в списке, но не в наборе) но это не будет слишком сложно.

Answer 2

Быстрый ответ - нет, он еще не доступен.

Реализовать это, конечно, легко, как вы понимаете. Причина, по которой он обычно не применяется, заключается в следующем. Если вы можете сделать содержит в O (1), то вы можете сделать поиск по индексу в O (1). Но, конечно, поиск по индексу не уникален, если у вас есть повторяющиеся элементы.

Поскольку в сущности вам нужны две структуры данных, Набор (или Карта) и Список, и нет более эффективного способа сделать это, чем это, авторы стандартной библиотеки оставляют вас объединять структурируй себя.

Answer 3

В .NET 4 есть новый класс SortedSet<T>, где Contains() - это O (1), см. эту страницу MSDN

Answer 4

HashSet реализует ICollection<T>, если это используется. Доступно с 3.5 года.

Answer 5

В .Net 3.5 его нет, но его очень легко реализовать:

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 6

Вы можете иметь любое количество (хэшированных или других) индексов в узлах двусвязных списков (двусвязных, поэтому вы можете удалить O (1)).

Answer 7

KeyedCollection<TKey, TItem> обеспечивает этот тип функциональности, хотя вы должны извлечь его и предоставить ему функцию для извлечения ключа из хэшированного элемента.