Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0 - Списки и шаблоны
ОГЛАВЛЕНИЕ
Список хешей
public sealed class HashList<TKey, TValue> :
VisitableHashtable<TKey, IList<TValue>>
{
// методы
public void Add(TKey key, ICollection<TValue> values);
public void Add(TKey key, TValue value);
public IEnumerator<TValue> GetValueEnumerator();
public bool Remove(TValue item);
public bool Remove(TKey key, TValue item);
public void RemoveAll(TValue item);
// свойства
public int KeyCount { get; }
public int ValueCount { get; }
}
HashList (или мультисловарь) является HashTable, способной хранить множество значений для конкретного ключа. Он основан на стандартном классе словаря и выполняет те же функции, что и класс Dictionary<TKey, IList<TValue>>, с более приятным синтаксисом.
Отсортированный список
public class SortedList<T> : IVisitableCollection<T>, IList<T>
{
// методы
public override void Accept(IVisitor<T> visitor);
public override void Add(T item);
public override void Clear();
public override int CompareTo(object obj);
public override bool Contains(T item);
public override void CopyTo(T[] array, int arrayIndex);
public override IEnumerator<T> GetEnumerator();
public override bool Remove(T item);
public void RemoveAt(int index);
// ...
// свойства
public IComparer<T> Comparer { get; }
public T this[int i] { get; }
// ...
}
Класс SortedList<T> выполняет ту же функцию, что и стандартный класс SortedList<TKey, TValue> в каркасе .NET, не считая того что он убирает две тонкости, обнаруженные при работе с тем классом:
• Повторяющиеся элементы могут появляться в этом SortedList (они запрещены в стандартном классе).
• Элементы сортируются сами, и никакого ключа не надо (стандартный SortedList требует пары ключ-значение).
Список пропусков
public class SkipList<TKey, TValue> : IVisitableDictionary<TKey, TValue>
{
// методы
public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
public void Add(KeyValuePair<TKey, TValue> item);
public void Add(TKey key, TValue value);
public bool ContainsKey(TKey key);
public void CopyTo(KeyValuePair<TKey,
TValue>[] array, int arrayIndex);
public IEnumerator<KeyValuePair<TKey,
TValue>> GetEnumerator();
public bool Remove(TKey key);
public bool TryGetValue(TKey key, out TValue value);
// ...
// свойства
public IComparer<TKey> Comparer { get; }
public int CurrentListLevel { get; }
public TValue this[TKey key] { get; set; }
public ICollection<TKey> Keys { get; }
public int MaxListLevel { get; }
public double Probability { get; }
public ICollection<TValue> Values { get; }
// ...
}
SkipList – хитроумная структура данных, впервые предложенная Уильямом Пугом в 1990 г. Его оригинальная статья лежит тут. Суть SkipList в том, что элементы дублируются на разных уровнях связанных списков, уровень выбирается (почти) случайно. Он обеспечивает быстрый поиск элемента путем "перескоков" через несколько элементов списка, в отличие от нормального связанного списка, где сравнения были бы последовательными.
Списки пропусков обычно реализуются одним из двух способов, с использованием нескольких связанных списков, или матричной структуры (например, двумерный связанный список). SkipList реализован здесь в стиле матрицы. Он реализует интерфейс IDictionary<TKey, TValue> и поэтому может использоваться как стандартный класс Dictionary<TKey, TValue> в каркасе.
Несмотря на то, что производительность превосходная, дублирование элементов может привести к очень быстрому истощению памяти, особенно при большом максимальном числе уровней.
[Дополнительная информация о списках пропусков]
Расширенные стандартные структуры данных
В библиотеку включены версии некоторых из стандартных обобщенных структур данных .NET, расширенных до реализации интерфейса IVisitableCollection<T>. Они следующие:
• VisitableHashtable<Tkey, TValue>
• VisitableLinkedList<T>
• VisitableList<T>
• VisitableQueue<T>
• VisitableStack<T>
Реализованные шаблоны
Синглтон
public sealed class Singleton<T> where T: new()
{
// методы
private Singleton();
// свойства
public static T Instance { get; }
// поля
private static T instance;
}
Синглтон – шаблон, снижающий число экземпляров класса до одного. С появлением обобщений в C# 2.0 реализация обобщенного синглтона стала очень изящной. Другая (более-менее такая же) реализация шаблона синглтона есть в этой статье, но лучше инициализировать значение статически.
Шаблон «Посетитель»
public interface IVisitor<T>
{
// методы
void Visit(T obj);
// свойства
bool HasCompleted { get; }
}
Шаблон «Посетитель» реализуется всеми коллекциями, унаследованными от интерфейса IVisitableCollection<T>. Посетители, унаследованные от IVisitor<T>, могут использоваться для посещения всех видов коллекций, безразлично к внутренней структуре посещаемой структуры данных. Он предоставляет два метода:
• Посетить производит некоторое действие над объектом. Например, считающий посетитель применяется к структуре данных из целых чисел и производит операцию += в методе Visit.
• Свойство HasCompleted указывает, хочет ли посетитель продолжить посещение остальных объектов, содержащихся в коллекции. Это полезно для ищущих посетителей, которые могут прекратить посещение, найдя искомый объект.