Перечисления и коллекции в C#

Содержание

Платформа .NET содержит набор типов для хранения и управления коллекциями объектов: списки с изменяемыми размерами, связанные списки, отсортированные и неотсортированные словари, массивы.

Типы в .NET для коллекций можно разделить на три категории:

интерфейсы, определяющие стандартные протоколы коллекций
готовые к использованию классы коллекций (списки, словари)
базовые классы для написания коллекций

Все эти типы расположены в следующих пространствах имен:

System.Collections — необобщенные классы и интерфейсы коллкций
System.Collections.Specialized — строго типизированные необобщенные классы коллекций
System.Collections.Generic — обобщенные классы и интерфейсы коллекций
System.Collections.ObjectModel — прокси и базовые классы для специальных коллекций
System.Collections.Concurrent — коллекции, безопасные к потокам

Все коллекции являются перечислениями и реализуют (должны реализовывать) интерфейс IEnumerable или IEnumerable<T>.

Интерфейсы перечислений обеспечивают протокол для итерации по коллекции, но не предоставляют механизма для определения размера коллекции, доступа к члену по индексу, поиска или модификации коллекции. Для данного функционала определены интерфейсы ICollection, IList и IDictionary. Каждый из них имеет обобщенную и необобщенную версию (однако необобщенные используются редко).

Иерархия интерфейсов коллекций:

IEnumerable<T> и IEnumerable — минимальный уровень функциональности: только перечисление
ICollection<T> и ICollection — средний уровень функциональности, например, свойство Count
IList <T>, IDictionary <K,V> и их необобщенные аналоги — максимальный уровень функциональности

Перечисление (Enumeration)

Нумератор, или перечислитель (enumerator) — доступный только для чтения однонаправленный курсор (forward-only cursor — курсор, движущийся только вперёд, без возможности обратного перемещения) перебирающий последовательность (sequence) значений. Нумератор представляет собой объект, реализующий интерфейс System.Collections.IEnumerator или System.Collections.Generic.IEnumerator<T>.

Инструкция foreach перебирает, или выполняет итерацию (iterate) над перечислимыми (enumerable) объектами. Перечислимые объекты — это логическое представление последовательностей. Перечислимый объект — это не курсор, о котором говорилось выше, а объект, содержащий такой курсор, способный перемещаться по объекту и перебирать его. Перечислимый объект либо реализует интерфейс IEnumerable или IEnumerable<T>, либо содержит метод GetEnumerator, который возвращает нумератор (enumerator).

Интерфейсы IEnumerable и IEnumerator

Интерфейс IEnumerator определяет базовый низкоуровневый протокол, посредством которого производится проход по элементам (перечисление) последовательности в одонаправленной манере. Объявление этого интерфейса:

public interface IEnumerator
{
    bool MoveNext();
    object Current { get; }
    void Reset();
}

public interface IEnumerator

{

bool MoveNext();

object Current { get; }

void Reset();

}

Метод MoveNext передвигает текущий элемент, или курсор, на следующую позицию, возвращая false, если в последовательности больше не осталось элементов. Метод Current возвращает элемент в текущей позиции (приводя его от object к более специфичному типу). Перед извлечением первого элемента должен быть вызван метод MoveNext (это нужно для учета пустой коллекции). Метод Reset (если реализован) осуществляет перемещение к началу.

Коллекции обычно не реализуют перечислители, а предоставляют их через интерфейс IEnumerable:

public interface IEnumerable
{
    IEnumerator GetEnumerator();
}

public interface IEnumerable

{

IEnumerator GetEnumerator();

}

За счет определения единственного метода, возвращающего перечислитель, интерфейс IEnumerable обеспечивает гибкость в том, что логика итерации может быть предоставлена другому классу. Это также дает возможность нескольким потребителям выполнять перечисление последовательности одновременно, не влияя друг на друга.

Инструкция foreach предоставляет высокоуровневый и лаконичный способ перебрать перечислимый объект:

foreach (char c in "beer") Console.WriteLine (c);

1	foreach (char c in "beer") Console.WriteLine (c);

Тоже самое можно сделать более низкоуровневым способом без использования инструкции foreach:

using (var enumerator = "beer".GetEnumerator())
    while (enumerator.MoveNext())
    {
        var element = enumerator.Current;
        Console.WriteLine (element);
    }

using (var enumerator = "beer".GetEnumerator())

while (enumerator.MoveNext())

{

var element = enumerator.Current;

Console.WriteLine (element);

}

Если нумератор реализует интерфейс IDisposable, инструкция foreach действует также как инструкция using, автоматически уничтожая объект нумератора.

Интерфейсы IEnumerable<T> и IEnumerator<T>

Интерфейсы IEnumerator и IEnumerable почти всегда реализуются в сочетании со своими обобщенными версиями:

public interface IEnumerator<T> : IEnumerator, IDisposable
{
    T Current { get; }
}
public interface IEnumerable<T> : IEnumerable
{
    IEnumerator<T> GetEnumerator();
}

public interface IEnumerator<T> : IEnumerator, IDisposable

{

T Current { get; }

}

public interface IEnumerable<T> : IEnumerable

{

IEnumerator<T> GetEnumerator();

}

Инициализаторы коллекций (Collection Initializers)

Можно объявлять и заполнять перечислимые объекты в один шаг:

using System.Collections.Generic;
List<int> list = new List<int> {1, 2, 3};

1 2	using System.Collections.Generic; List<int> list = new List<int> {1, 2, 3};

Компилятор преобразует последнюю строку в следующие инструкции:

List<int> list = new List<int>();
list.Add (1); list.Add (2); list.Add (3);

1 2	List<int> list = new List<int>(); list.Add (1); list.Add (2); list.Add (3);

Для этого необходимо, чтобы перечислимый объект реализовывал интерфейс System.Collections.IEnumerable, а также у него должен быть метод Add.

Итераторы (Iterators)

Перед тем как использовать нумератор с помощью инструкции foreach его нужно создать и сделать это можно с помощью итератора. Итератор — это метод, свойство или индексатор, содержащий одну или более инструкции yield. Также итератор должен обязательно возвращать (иметь тип) один из четырех интерфейсов (иначе компилятор выдаст ошибку):

System.Collections.IEnumerable
System.Collections.IEnumerator
System.Collections.Generic.IEnumerable<T>
System.Collections.Generic.IEnumerator<T>

using System;
using System.Collections.Generic;
class Test
{
    static void Main()
    {
        foreach (int fib in Fibs(6))
            Console.Write (fib + " "); //выведет 1 1 2 3 5 8
    }
    static IEnumerable<int> Fibs(int fibCount) // итератор
    {
        for (int i = 0, prevFib = 1, curFib = 1; i < fibCount; i++)
        {
            yield return prevFib;
            int newFib = prevFib+curFib;
            prevFib = curFib;
            curFib = newFib;
        }
    }
}

using System;

using System.Collections.Generic;

class Test

{

static void Main()

{

foreach (int fib in Fibs(6))

Console.Write (fib + " "); //выведет 1 1 2 3 5 8

}

static IEnumerable<int> Fibs(int fibCount) // итератор

{

for (int i = 0, prevFib = 1, curFib = 1; i < fibCount; i++)

{

yield return prevFib;

int newFib = prevFib+curFib;

prevFib = curFib;

curFib = newFib;

}

Если инструкция return возвращает значение из метода и сразу же завершает метод, инструкция yield return действует иначе. Она возвращает очередной элемент перечислимого объекта. При этом метод не завершается сразу же: управление возвращается в точку вызова (обычно это итерация инструкции foreach), но метод-итератор не завершается, он остается в некотором застывшем состоянии до тех пор, пока в точке вызова не будет запрошен следующий элемент, после чего выполнение метода-итератора продолжается. Время жизни этого застывшего состояния итератора ограничивается нумератором — оно прекращается как только в точке вызова прекратиться перечисление.

Компилятор преобразует методы итераторы в частные классы реализующие интерфейс IEnumerable<T> и/или IEnumerator<T>. Логика в блоке итератора преобразуется и распределяется между методом MoveNext и свойством Current созданного компилятором класса нумератора. Это означает, что при вызове метода итератора на самом деле создается экземпляр созданного компилятором класса, а написанный нами код в действительности не выполняется. Наш код выполняется только, когда мы начинаем перебирать получившуюся последовательность, например, с помощью инструкции foreach.

Итераторы возвращающие интерфейс нумератора (т.е. фактически создающие нумератор) на практике используются редко. Они могут быть полезны при написании собственного класса коллекции. В этом случае сам класс коллекции реализует интерфейс IEnumerable<T> (т.е. создает перечислимый объект), а метод итератор получает название GetEnumerator и возвращает нумератор для коллекции.

Итераторы возвращающие интерфейс перечислимого объекта (т.е. фактически создающие такой объект) более просты в использовании и используются чаще. В этом случае нет необходимости создавать класс коллекции — компилятор это сделает за нас, создав частный класс реализующий интерфейс IEnumerable<T> (перечислимый объект) и класс реализующий IEnumerator<T> (нумератор для перечислимого объекта).

Итератор может содержать несколько инструкций yield:

static void Main()
{
    foreach (string s in Foo())
    Console.Write (s + " "); // One Two Three
}
static IEnumerable<string> Foo()
{
    yield return "One";
    yield return "Two";
    yield return "Three";
}

static void Main()

{

foreach (string s in Foo())

Console.Write (s + " "); // One Two Three

}

static IEnumerable<string> Foo()

{

yield return "One";

yield return "Two";

yield return "Three";

}

Логика в этом случае такая же — каждая инструкция yield возвращает очередной элемент последовательности.

Инструкция yield break указывает на необходимость завершить блок итератора досрочно и не возвращать больше ни одного элемента:

static IEnumerable<string> Foo (bool breakEarly)
{
    yield return "One";
    yield return "Two";
    if (breakEarly) yield break;
    yield return "Three";
}

static IEnumerable<string> Foo (bool breakEarly)

{

yield return "One";

yield return "Two";

if (breakEarly) yield break;

yield return "Three";

}

Инструкция return в блоке итератора недопустима, для выхода из блока итератора нужно использовать только yield break.

Итераторы могут преобразовывать одну последовательность в другую:

static IEnumerable<int> EvenNumbersOnly (IEnumerable<int> sequence)
{
    foreach (int x in sequence)
        if ((x % 2) == 0)
            yield return x;
}

static IEnumerable<int> EvenNumbersOnly (IEnumerable<int> sequence)

{

foreach (int x in sequence)

if ((x % 2) == 0)

yield return x;

}

Именно эта особенность используется для построения LINQ запросов.

Интерфейсы ICollection<T> и ICollection

ICollection<T> — стандартный интерфейс коллекции объектов с возможностью подсчета:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    int Count { get; } // Размер коллекции
    bool Contains (T item); // Содержится ли элемент в коллекции
    void CopyTo (T[] array, int arrayIndex); // Копировать коллекцию в массив
    bool IsReadOnly { get; } // Является ли коллекция предназначенной только для чтения
    void Add (T item); // Добавить элемент коллекции
    bool Remove (T item); // Удалить элемент коллекции
    void Clear (); // Очистить (удалить все элементы) коллекцию
}

public interface ICollection<T> : IEnumerable<T>, IEnumerable

{

int Count { get; } // Размер коллекции

bool Contains (T item); // Содержится ли элемент в коллекции

void CopyTo (T[] array, int arrayIndex); // Копировать коллекцию в массив

bool IsReadOnly { get; } // Является ли коллекция предназначенной только для чтения

void Add (T item); // Добавить элемент коллекции

bool Remove (T item); // Удалить элемент коллекции

void Clear (); // Очистить (удалить все элементы) коллекцию

}

При реализации коллекции предназначенной только для чтения, методы Add, Remove и Clear должны генерировать исключение NotSupportedException.

Необобщенный интерфейс ICollection также предоставляет возможность подсчета, но не содержит функционал для изменения коллекции (Add, Remove, Clear) и проверки членства элементов (Contains):

public interface ICollection : IEnumerable
{
    int Count { get; }
    bool IsSynchronized { get; }
    object SyncRoot { get; }
    void CopyTo (Array array, int index);
}

public interface ICollection : IEnumerable

{

int Count { get; }

bool IsSynchronized { get; }

object SyncRoot { get; }

void CopyTo (Array array, int index);

}

Необобщенный интерфейс также определяет свойства для содействия в синхронизации (из обобщенной версии они были исключены).

Интерфейсы IList<T>, IList и IReadOnlyList<T>

IList<T> — стандартный интерфейс коллекции поддерживающей индексацию по позиции. Помимо функционала, унаследованного от ICollection<T> и IEnumerable<T>, он предоставляет возможность чтения и записи элемента по позиции (через индексатор) и вставки/удаления по позиции:

public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
{
    T this [int index] { get; set; } // Индексатор
    int IndexOf (T item); // Линейный поиск в списке (возвращает -1 если элемент не найден)
    void Insert (int index, T item); // Вставка по позиции
    void RemoveAt (int index); // Удаление по позиции
}

public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable

{

T this [int index] { get; set; } // Индексатор

int IndexOf (T item); // Линейный поиск в списке (возвращает -1 если элемент не найден)

void Insert (int index, T item); // Вставка по позиции

void RemoveAt (int index); // Удаление по позиции

}

Необобщенный интерфейс IList имеет большее число членов, поскольку наследует меньшее их количество от ICollection:

public interface IList : ICollection, IEnumerable
{
    object this [int index] { get; set }
    bool IsFixedSize { get; }
    bool IsReadOnly { get; }
    int Add (object value);
    void Clear ();
    bool Contains (object value);
    int IndexOf (object value);
    void Insert (int index, object value);
    void Remove (object value);
    void RemoveAt (int index);
}

public interface IList : ICollection, IEnumerable

{

object this [int index] { get; set }

bool IsFixedSize { get; }

bool IsReadOnly { get; }

int Add (object value);

void Clear ();

bool Contains (object value);

int IndexOf (object value);

void Insert (int index, object value);

void Remove (object value);

void RemoveAt (int index);

}

Метод Add интерфейса IList возвращает индекс вновь добавленного элемента, тогда как метод Add интерфейса ICollection<T> возвращает viod.

Для реализации коллекций предназначенных только для чтения предусмотрен интерфейс IReadOnlyList<T>:

public interface IReadOnlyList<out T> : IEnumerable<T>, IEnumerable
{
    int Count { get; }
    T this [int index] { get; }
}

public interface IReadOnlyList<out T> : IEnumerable<T>, IEnumerable

{

int Count { get; }

T this [int index] { get; }

}

Класс Array

Класс Array является неявным базовым классом для всех одномерных и многомерных массивов. Когда объявляется массив с применением синтаксиса C#, среда CLR неявно создает подтип класса Array.

Класс Array реализует интерфейсы коллекций вплоть до IList<T> (в обеих формах — обобщенной и необобщенной). Однако интерфейс IList<T> реализован явно, чтобы закрыть методы Add и Remove, генерирующие исключение. При этом класс Array имеет статический метод Resize (правда он создает новый массив и копирует в него все элементы).

Массивы могут дублироваться с помощью метода Clone. Однако результатом будет поверхностная (неглубокая) копия, означающая копирование только памяти, в которой представлен сам массив. Если массив содержит элементы значимых типов, копируются сами значения, если же ссылочных типов — копируются только ссылки, давая в результате два массива, элементы которого ссылаются на одни и те же объекты. Чтобы создать глубокую копию, в которой объекты ссылочных типов дублируются, нужно пройти в цикле по массиву и клонировать каждый его элемент вручную. Эти же правила применяются и к остальным коллекциям.

Массив можно создать не только с помощью синтаксиса C#, но и динамически с помощью статического метода Array.CreateInstance. При этом можно указать тип элементов и ранг (количество измерений), а также создать массив с индексацией начинающейся не с нуля, за счет указания нижней границы:

Array a = Array.CreateInstance (typeof(string), 2);

1	Array a = Array.CreateInstance (typeof(string), 2);

Статические методы GetValue и SetValue позволяют получать доступ к элементам в динамически созданном массиве (также работают и с обычными массивами). Метод SetValue генерирует исключение, если элемент имеет тип несовместимый с массивом.

a.SetValue ("hi", 0); // эквивалент a[0] = "hi";
a.SetValue ("there", 1); // эквивалент a[1] = "there";
string s = (string) a.GetValue (0); // эквивалент s = a[0];

a.SetValue ("hi", 0); // эквивалент a[0] = "hi";

a.SetValue ("there", 1); // эквивалент a[1] = "there";

string s = (string) a.GetValue (0); // эквивалент s = a[0];

Динамически созданные массивы (индексируемые с нуля) можно привести к обычным массивам совпадающего или совместимого типа:

string[] cSharpArray = (string[]) a;
string s2 = cSharpArray [0];

1 2	string[] cSharpArray = (string[]) a; string s2 = cSharpArray [0];

Статический метод Clear выполняет очистку массива, при этом размер массива не изменяется, а его членам присваивается либо значение null (для ссылочных типов) либо значение по умолчанию для конкретного значимого типа (в противовес этому коллекция при использовании метода Clear сокращается до нуля).

С помощью статического метода Array.ForEach можно выполнить перечисление:

// Объявление метода:
public static void ForEach<T> (T[] array, Action<T> action);
// Пример:
Array.ForEach (new[] { 1, 2, 3 }, Console.WriteLine);

// Объявление метода:

public static void ForEach<T> (T[] array, Action<T> action);

// Пример:

Array.ForEach (new[] { 1, 2, 3 }, Console.WriteLine);

Запросить длину и ранг массива можно с помощью следующих методов и свойств:

public int GetLength (int dimension); // Длина для заданного измерения (0 для одномерного)
public long GetLongLength (int dimension);
public int Length { get; } // Длина массива (во всех измерениях для многомерных)
public long LongLength { get; }
public int GetLowerBound (int dimension); // Нижний предел указанного измерения
public int GetUpperBound (int dimension); // Верхний предел указанного измерения
public int Rank { get; } // Количество измерений в массиве

public int GetLength (int dimension); // Длина для заданного измерения (0 для одномерного)

public long GetLongLength (int dimension);

public int Length { get; } // Длина массива (во всех измерениях для многомерных)

public long LongLength { get; }

public int GetLowerBound (int dimension); // Нижний предел указанного измерения

public int GetUpperBound (int dimension); // Верхний предел указанного измерения

public int Rank { get; } // Количество измерений в массиве

Класс Array содержит ряд статических методов для поиска в массиве:

BinarySearch — поиск элемента в отсортированном массиве. Этот метод является наиболее быстрым, но работает только на отсортированном массиве. Он может принимать объект IComparer или IComparer<T> для сопоставления элементов с искомым.
IndexOf и LastIndex — поиск элемента в несортированном массиве. Методы выполняют перечисление массива и возвращают индекс первого (или последнего) элемента, совпавшего с заданным значением.
Find, FindLast, FindIndex, FindLastIndex, FindAll, Exists иTrueForAll — поиска элемента/элементов, удовлетворяющих заданному предикату, в несортированном массиве. Предикат — это просто делегат, принимающий объект и возвращающий true или false:

public delegate bool Predicate<T> (T object);

1	public delegate bool Predicate<T> (T object);

Примеры использования метода Find:

static void Main()
{
    string[] names = { "Rodney", "Jack", "Jill" };
    string match = Array.Find (names, ContainsA);
    Console.WriteLine (match); // Jack
}
static bool ContainsA (string name) { return name.Contains ("a"); }
// Тоже самое с использованием анонимного метода:
string[] names = { "Rodney", "Jack", "Jill" };
string match = Array.Find (names, delegate (string name)
    { return name.Contains ("a"); } );
// С использованием лямбда-выражений:
string[] names = { "Rodney", "Jack", "Jill" };
string match = Array.Find (names, n => n.Contains ("a"));

static void Main()

{

string[] names = { "Rodney", "Jack", "Jill" };

string match = Array.Find (names, ContainsA);

Console.WriteLine (match); // Jack

}

static bool ContainsA (string name) { return name.Contains ("a"); }

// Тоже самое с использованием анонимного метода:

string[] names = { "Rodney", "Jack", "Jill" };

string match = Array.Find (names, delegate (string name)

{ return name.Contains ("a"); } );

// С использованием лямбда-выражений:

string[] names = { "Rodney", "Jack", "Jill" };

string match = Array.Find (names, n => n.Contains ("a"));

Метод FindAll возвращает массив всех элементов, удовлетворяющих предикату (эквивалентен методу System.Linq.Enumerable.Where). Метод Existsвозвращает true, если член массива удовлетворяет заданному предикату (эквивалентен System.Linq.Enumerable.Any). Метод TrueForAll возвращаетtrue если все элементы удовлетворяют заданному предикату (эквивалентен System.Linq.Enumerable.All).

Ни один из методов поиска не генерирует исключение если элемент не найден, вместо этого методы возвращающие целочисленное значение возвращают -1, а методы возвращающие обобщенный тип — возвращают стандартное значение для этого типа (0для int, null для string).

С помощью методов Sort можно выполнять сортировку массива:

// Для сортировки одного массива:
public static void Sort<T> (T[] array);
public static void Sort (Array array);
// Для сортировки пары массивов:
public static void Sort<TKey,TValue> (TKey[] keys, TValue[] items);
public static void Sort (Array keys, Array items);

// Для сортировки одного массива:

public static void Sort<T> (T[] array);

public static void Sort (Array array);

// Для сортировки пары массивов:

public static void Sort<TKey,TValue> (TKey[] keys, TValue[] items);

public static void Sort (Array keys, Array items);

Каждый из методов дополнительно перегружен и может принимать такие аргументы:

int index // Индекс, с которого должна начаться сортировка
int length // Количество элементов для сортировки
IComparer<T> comparer // Объект для упорядочивания
Comparison<T> comparison // Делегат для упорядочивания

int index // Индекс, с которого должна начаться сортировка

int length // Количество элементов для сортировки

IComparer<T> comparer // Объект для упорядочивания

Comparison<T> comparison // Делегат для упорядочивания

Методы, принимающие пару массивов, упорядочивают элементы в каждом из них, но порядок сортировки определяется по первому массиву:

int[] numbers = { 3, 2, 1 };
string[] words = { "three", "two", "one" };
Array.Sort (numbers, words);
// numbers array is now { 1, 2, 3 }
// words array is now { "one", "two", "three" }

int[] numbers = { 3, 2, 1 };

string[] words = { "three", "two", "one" };

Array.Sort (numbers, words);

// numbers array is now { 1, 2, 3 }

// words array is now { "one", "two", "three" }

Метод Sort требует, чтобы элементы массива реализовывали интерфейс IComparable. Если элементы не сравнимы по сути, методу нужно передать либо объект, реализующий IComparer /IComparer<T>, либо делегат Comparison(public delegate int Comparison<T> (T x, T y);), которые и будут принимать решение об упорядочивании элементов:

int[] numbers = { 1, 2, 3, 4, 5 };
Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? −1 : 1);
// numbers array is now { 3, 5, 1, 2, 4 }

int[] numbers = { 1, 2, 3, 4, 5 };

Array.Sort (numbers, (x, y) => x % 2 == y % 2 ? 0 : x % 2 == 1 ? −1 : 1);

// numbers array is now { 3, 5, 1, 2, 4 }

Метод Reverse изменяет порядок всех или части элементов на противоположный:

public static void Reverse (Array array);
public static void Reverse (Array array, int index, int length);

1 2	public static void Reverse (Array array); public static void Reverse (Array array, int index, int length);

Класс Array содержит четыре метода для выполнения поверхностного копирования: Clone, CopyTo, Copy и ConstrainedCopy. Первые два являются экземплярными, последние — статическими.

Метод ConvertAll приводит все элементы массива к другому типу. Исходный массив не изменяется: метод создает и возвращает новый массив. Приведение осуществляется с помощью переданного методу делегата Converter:

public delegate TOutput Converter<TInput,TOutput> (TInput input)

1	public delegate TOutput Converter<TInput,TOutput> (TInput input)

Пример:

float[] reals = { 1.3f, 1.5f, 1.8f };
int[] wholes = Array.ConvertAll (reals, r => Convert.ToInt32 (r));
// wholes = { 1, 2, 2 }

float[] reals = { 1.3f, 1.5f, 1.8f };

int[] wholes = Array.ConvertAll (reals, r => Convert.ToInt32 (r));

// wholes = { 1, 2, 2 }

Статический метод Resize позволяет изменить размер массива. Пир этом исходный массив не изменяется: метод создает и возвращает новый массив.

Списки

Платформа .NET предоставляет базовый набор классов коллекций, реализующих интерфейсы, описанные выше. Далее рассматриваются списковые коллекции.

List<T> и ArrayList

Обобщенный класс List и необобщенный класс ArrayList представляют собой массивы объектов с возможностью динамического изменения размеров. ArrayList реализует IList, а List<T> реализует IList, IList<T> и IReadOnlyList<T>. В отличие от массивов все интерфейсы реализованы явно, а методы Add и Remove открыты и работают ожидаемым образом.

Класс List<T> до семи раз быстрее чем ArrayList, если T является значимым типом, т.к. List<T> не выполняет упаковку и распаковку элементов (boxing/unboxing).

Члены класса List<T>:

public class List<T> : IList<T>, IReadOnlyList<T>
{
    // Конструкторы
    public List ();
    public List (IEnumerable<T> collection);
    public List (int capacity);
    // Добавление и вставка
    public void Add (T item);
    public void AddRange (IEnumerable<T> collection);
    public void Insert (int index, T item);
    public void InsertRange (int index, IEnumerable<T> collection);
    // Удаление
    public bool Remove (T item);
    public void RemoveAt (int index);
    public void RemoveRange (int index, int count);
    public int RemoveAll (Predicate<T> match);
    // Индексация
    public T this [int index] { get; set; }
    public List<T> GetRange (int index, int count);
    public Enumerator<T> GetEnumerator();
    // Экспорт, копирование, преобразование
    public T[] ToArray ();
    public void CopyTo (T[] array);
    public void CopyTo (T[] array, int arrayIndex);
    public void CopyTo (int index, T[] array, int arrayIndex, int count);
    public ReadOnlyCollection<T> AsReadOnly ();
    public List<TOutput> ConvertAll<TOutput> (Converter <T,TOutput> converter);
    // Другие
    public void Reverse (); // Изменение порядка на противоположный
    public int Capacity { get;set; } // Принудительное расширение внутреннего массива
    public void TrimExcess (); // Обрезает внутренний массив до фактического размера
    public void Clear (); // Удаляет все элементы
}

public class List<T> : IList<T>, IReadOnlyList<T>

{

// Конструкторы

public List ();

public List (IEnumerable<T> collection);

public List (int capacity);

// Добавление и вставка

public void Add (T item);

public void AddRange (IEnumerable<T> collection);

public void Insert (int index, T item);

public void InsertRange (int index, IEnumerable<T> collection);

// Удаление

public bool Remove (T item);

public void RemoveAt (int index);

public void RemoveRange (int index, int count);

public int RemoveAll (Predicate<T> match);

// Индексация

public T this [int index] { get; set; }

public List<T> GetRange (int index, int count);

public Enumerator<T> GetEnumerator();

// Экспорт, копирование, преобразование

public T[] ToArray ();

public void CopyTo (T[] array);

public void CopyTo (T[] array, int arrayIndex);

public void CopyTo (int index, T[] array, int arrayIndex, int count);

public ReadOnlyCollection<T> AsReadOnly ();

public List<TOutput> ConvertAll<TOutput> (Converter <T,TOutput> converter);

// Другие

public void Reverse (); // Изменение порядка на противоположный

public int Capacity { get;set; } // Принудительное расширение внутреннего массива

public void TrimExcess (); // Обрезает внутренний массив до фактического размера

public void Clear (); // Удаляет все элементы

}

Помимо этих метод класс List<T> содержит экземплярные методы поиска и сортировки, аналогичные статическим методам класса Array. Пример использования методов:

List<string> words = new List<string>();
words.Add ("melon"); // Вставка элемента в конец списка
words.Add ("avocado");
words.AddRange (new[] { "banana", "plum" } ); // Вставка нескольких элементов
words.Insert (0, "lemon"); // Вставка в начало списка
words.InsertRange (0, new[] { "peach", "nashi" }); // Вставка нескольких элементов в начало списка
words.Remove ("melon"); // Удаление элемента
words.RemoveAt (3); // Удаление 4-го элемента
words.RemoveRange (0, 2); // Удаление первых двух элементов
words.RemoveAll (s => s.StartsWith ("n")); // Удаление всех строк, начинающихся с "n"
Console.WriteLine (words [0]); // первое слово
Console.WriteLine (words [words.Count - 1]); // последнее слово
foreach (string s in words) Console.WriteLine (s); // все слова
List<string> subset = words.GetRange (1, 2); // со второго по третье слово
string[] wordsArray = words.ToArray(); // новый массив
// Копирование первых двух элементов в конец существующего массива:
string[] existing = new string [1000];
words.CopyTo (0, existing, 998, 2);
// Преобразование
List<string> upperCastWords = words.ConvertAll (s => s.ToUpper());
List<int> lengths = words.ConvertAll (s => s.Length);

List<string> words = new List<string>();

words.Add ("melon"); // Вставка элемента в конец списка

words.Add ("avocado");

words.AddRange (new[] { "banana", "plum" } ); // Вставка нескольких элементов

words.Insert (0, "lemon"); // Вставка в начало списка

words.InsertRange (0, new[] { "peach", "nashi" }); // Вставка нескольких элементов в начало списка

words.Remove ("melon"); // Удаление элемента

words.RemoveAt (3); // Удаление 4-го элемента

words.RemoveRange (0, 2); // Удаление первых двух элементов

words.RemoveAll (s => s.StartsWith ("n")); // Удаление всех строк, начинающихся с "n"

Console.WriteLine (words [0]); // первое слово

Console.WriteLine (words [words.Count - 1]); // последнее слово

foreach (string s in words) Console.WriteLine (s); // все слова

List<string> subset = words.GetRange (1, 2); // со второго по третье слово

string[] wordsArray = words.ToArray(); // новый массив

// Копирование первых двух элементов в конец существующего массива:

string[] existing = new string [1000];

words.CopyTo (0, existing, 998, 2);

// Преобразование

List<string> upperCastWords = words.ConvertAll (s => s.ToUpper());

List<int> lengths = words.ConvertAll (s => s.Length);

LinkedList<T>

Класс LinkedList<T> представляет обобщенный двусвязный список. Двусвязный список — это цепочка узлов, в которой каждый узел ссылается на предыдущий узел, следующий узел и действительный элемент. Его главное преимущество в том, что элемент может быть эффективно вставлен в любое место списка, т.к. это требует только создания нового узла и обновления нескольких ссылок. Однако поиск выполняется медленно, путем прямого перебора, т.к. двоичный поиск не возможен и отсутствует механизм индексации.

Класс LinkedList<T> реализует IEnumerable<T> и ICollection<T> (и их необобщенные варианты), но не IList<T>, поскольку доступ по индексу не поддерживается.

Узлы списка реализованы классом LinkedListNode<T>:

public sealed class LinkedListNode<T>
{
    public LinkedList<T> List { get; }
    public LinkedListNode<T> Next { get; }
    public LinkedListNode<T> Previous { get; }
    public T Value { get; set; }
}

public sealed class LinkedListNode<T>

{

public LinkedList<T> List { get; }

public LinkedListNode<T> Next { get; }

public LinkedListNode<T> Previous { get; }

public T Value { get; set; }

}

Члены класса LinkedList<T>:

// Методы для добавления узла:
public void AddFirst (LinkedListNode<T> node);
public LinkedListNode<T> AddFirst (T value);
public void AddLast (LinkedListNode<T> node);
public LinkedListNode<T> AddLast (T value);
public void AddAfter (LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddAfter (LinkedListNode<T> node, T value);
public void AddBefore (LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddBefore (LinkedListNode<T> node, T value);
// Методы для удаления узла:
public void Clear ();
public void RemoveFirst ();
public void RemoveLast ();
public bool Remove (T value);
public void Remove (LinkedListNode<T> node);
// Свойства:
public int Count { get; } // Количество узлов
public LinkedListNode<T> First { get; } // Ссылка на первый узел
public LinkedListNode<T> Last { get; } // Ссылка на последний узел
// Методы поиска:
public bool Contains (T value);
public LinkedListNode<T> Find (T value);
public LinkedListNode<T> FindLast (T value);
// Копирование в массив
public void CopyTo (T[] array, int index);
// Нумератор
public Enumerator<T> GetEnumerator ();

// Методы для добавления узла:

public void AddFirst (LinkedListNode<T> node);

public LinkedListNode<T> AddFirst (T value);

public void AddLast (LinkedListNode<T> node);

public LinkedListNode<T> AddLast (T value);

public void AddAfter (LinkedListNode<T> node, LinkedListNode<T> newNode);

public LinkedListNode<T> AddAfter (LinkedListNode<T> node, T value);

public void AddBefore (LinkedListNode<T> node, LinkedListNode<T> newNode);

public LinkedListNode<T> AddBefore (LinkedListNode<T> node, T value);

// Методы для удаления узла:

public void Clear ();

public void RemoveFirst ();

public void RemoveLast ();

public bool Remove (T value);

public void Remove (LinkedListNode<T> node);

// Свойства:

public int Count { get; } // Количество узлов

public LinkedListNode<T> First { get; } // Ссылка на первый узел

public LinkedListNode<T> Last { get; } // Ссылка на последний узел

// Методы поиска:

public bool Contains (T value);

public LinkedListNode<T> Find (T value);

public LinkedListNode<T> FindLast (T value);

// Копирование в массив

public void CopyTo (T[] array, int index);

// Нумератор

public Enumerator<T> GetEnumerator ();

Пример использования:

var tune = new LinkedList<string>();
tune.AddFirst ("do"); // do
tune.AddLast ("so"); // do - so
tune.AddAfter (tune.First, "re"); // do - re- so
tune.AddAfter (tune.First.Next, "mi"); // do - re - mi- so
tune.AddBefore (tune.Last, "fa"); // do - re - mi - fa- so
tune.RemoveFirst(); // re - mi - fa - so
tune.RemoveLast(); // re - mi - fa
LinkedListNode<string> miNode = tune.Find ("mi");
tune.Remove (miNode); // re - fa
tune.AddFirst (miNode); // mi- re - fa
foreach (string s in tune) Console.WriteLine (s);

var tune = new LinkedList<string>();

tune.AddFirst ("do"); // do

tune.AddLast ("so"); // do - so

tune.AddAfter (tune.First, "re"); // do - re- so

tune.AddAfter (tune.First.Next, "mi"); // do - re - mi- so

tune.AddBefore (tune.Last, "fa"); // do - re - mi - fa- so

tune.RemoveFirst(); // re - mi - fa - so

tune.RemoveLast(); // re - mi - fa

LinkedListNode<string> miNode = tune.Find ("mi");

tune.Remove (miNode); // re - fa

tune.AddFirst (miNode); // mi- re - fa

foreach (string s in tune) Console.WriteLine (s);

Queue<T> и Queue

Queue<T> и Queue — это очереди — структуры данных FIFO (first-in first-out — первым зашел, первым вышел). Очереди являются перечислимыми, но не реализуют интерфейсы IList<T>/IList, т.к. доступ к элементам по индексу не поддерживается. Основное преимущество — скорость добавления (в конец очереди) и извлечения (с начала очереди) элементов из очереди.

public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable
{
    // Конструкторы:
    public Queue ();
    public Queue (IEnumerable<T> collection); // Копирует существующие элементы
    public Queue (int capacity); // Сокращает количество изменений размера
    // Специфические для очереди методы:
    public void Enqueue (T item); // Добавляет элемент в конец очереди
    public T Dequeue (); // Извлекает и удаляет элемент из начала очереди
    public T Peek (); // Возвращает элемент из начала очереди без его удаления
    // Остальные:
    public void Clear ();
    public bool Contains (T item);
    public void CopyTo (T[] array, int arrayIndex);
    public int Count { get; }
    public Enumerator<T> GetEnumerator ();
    public T[] ToArray ();
    public void TrimExcess ();
}

public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable

{

// Конструкторы:

public Queue ();

public Queue (IEnumerable<T> collection); // Копирует существующие элементы

public Queue (int capacity); // Сокращает количество изменений размера

// Специфические для очереди методы:

public void Enqueue (T item); // Добавляет элемент в конец очереди

public T Dequeue (); // Извлекает и удаляет элемент из начала очереди

public T Peek (); // Возвращает элемент из начала очереди без его удаления

// Остальные:

public void Clear ();

public bool Contains (T item);

public void CopyTo (T[] array, int arrayIndex);

public int Count { get; }

public Enumerator<T> GetEnumerator ();

public T[] ToArray ();

public void TrimExcess ();

}

Пример использования:

var q = new Queue<int>();
q.Enqueue (10);
q.Enqueue (20);
int[] data = q.ToArray(); // Экспорт в массив
Console.WriteLine (q.Count); // "2"
Console.WriteLine (q.Peek()); // "10"
Console.WriteLine (q.Dequeue()); // "10"
Console.WriteLine (q.Dequeue()); // "20"
Console.WriteLine (q.Dequeue()); // выбросит исключение т.к. очередь пуста

var q = new Queue<int>();

q.Enqueue (10);

q.Enqueue (20);

int[] data = q.ToArray(); // Экспорт в массив

Console.WriteLine (q.Count); // "2"

Console.WriteLine (q.Peek()); // "10"

Console.WriteLine (q.Dequeue()); // "10"

Console.WriteLine (q.Dequeue()); // "20"

Console.WriteLine (q.Dequeue()); // выбросит исключение т.к. очередь пуста

Stack<T> и Stack

Stack<T> и Stack — это стэки — структуры данных LIFO (last-in first-out — последним пришел, первым вышел).

public class Stack<T> : IEnumerable<T>, ICollection, IEnumerable
{
    // Конструкторы:
    public Stack ();
    public Stack (IEnumerable<T> collection);
    public Stack (int capacity);
    // Специфические для стека методы:
    public void Push (T item); // Добавляет элемент на верхушку стэка
    public T Pop (); // Извлекает и удаляет элемент из верхушки стэка
    public T Peek (); // Возвращает элемент из верхушки стэка без его удаления
    // Остальные:
    public void Clear ();
    public bool Contains (T item);
    public void CopyTo (T[] array, int arrayIndex);
    public int Count { get; }
    public Enumerator<T> GetEnumerator ();
    public T[] ToArray ();
    public void TrimExcess ();
}

public class Stack<T> : IEnumerable<T>, ICollection, IEnumerable

{

// Конструкторы:

public Stack ();

public Stack (IEnumerable<T> collection);

public Stack (int capacity);

// Специфические для стека методы:

public void Push (T item); // Добавляет элемент на верхушку стэка

public T Pop (); // Извлекает и удаляет элемент из верхушки стэка

public T Peek (); // Возвращает элемент из верхушки стэка без его удаления

// Остальные:

public void Clear ();

public bool Contains (T item);

public void CopyTo (T[] array, int arrayIndex);

public int Count { get; }

public Enumerator<T> GetEnumerator ();

public T[] ToArray ();

public void TrimExcess ();

}

Пример использования:

var s = new Stack<int>();
s.Push (1); // Содержимое стэка - 1
s.Push (2); // Содержимое стэка - 1,2
s.Push (3); // Содержимое стэка - 1,2,3
Console.WriteLine (s.Count); // Выводит 3
Console.WriteLine (s.Peek()); // Выводит 3, содержимое стэка - 1,2,3
Console.WriteLine (s.Pop()); // Выводит 3, содержимое стэка - 1,2
Console.WriteLine (s.Pop()); // Выводит 2, содержимое стэка - 1
Console.WriteLine (s.Pop()); // Выводит 1, стэк пуст
Console.WriteLine (s.Pop()); // генерирует исключение

var s = new Stack<int>();

s.Push (1); // Содержимое стэка - 1

s.Push (2); // Содержимое стэка - 1,2

s.Push (3); // Содержимое стэка - 1,2,3

Console.WriteLine (s.Count); // Выводит 3

Console.WriteLine (s.Peek()); // Выводит 3, содержимое стэка - 1,2,3

Console.WriteLine (s.Pop()); // Выводит 3, содержимое стэка - 1,2

Console.WriteLine (s.Pop()); // Выводит 2, содержимое стэка - 1

Console.WriteLine (s.Pop()); // Выводит 1, стэк пуст

Console.WriteLine (s.Pop()); // генерирует исключение

BitArray

Класс BitArray — это динамически изменяющая размеры коллекция компактных значений bool. С точки зрения затрат памяти она более эффективна, чем массив или список значений bool, т.к. каждое значение занимает только один бит.

Класс поддерживает доступ по индексу, а также содержит четыре метода для выполнения побитовых операций: And, Or, Xor и Not (все кроме последнего принимают другой экземпляр BitArray).

var bits = new BitArray(2);
bits[1] = true;
bits.Xor (bits);
Console.WriteLine (bits[1]);

var bits = new BitArray(2);

bits[1] = true;

bits.Xor (bits);

Console.WriteLine (bits[1]);

HashSet<T> и SortedSet<T>

HashSet<T> и SortedSet<T> — обобщенные коллекции, обладающие следующими особенностями:

их методs Contains выполняются быстро с использованием основанного на хэшировании поиска
они не хранят дублированный элементы и молча игнорируют запросы на добавление дубликатов
доступ к элементам по позиции не возможен

SortedSet<T> хранит элементы упорядоченными, HashSet<T> — нет. HashSet<T> реализована с помощью хэш-таблицы, в которой хранятся только ключи, а SortedSet<T> реализована посредством красно-черного дерева.

Обе коллекции реализуют интерфейс ICollection<T> и помимо стандартных членов этого интерфейса включают следующие методы:

public int RemoveWhere (Predicate<T> match) // Удаление на основе предиката
public void UnionWith (IEnumerable<T> other); // Добавляет элементы множества в коллекцию (исключая дубликаты)
// Удаление подмножества из коллекции:
public void IntersectWith (IEnumerable<T> other); // Удаляет элементы, которые не присутствую сразу в обоих наборах
public void ExceptWith (IEnumerable<T> other); // Удаляет переданные элементы из коллекции
public void SymmetricExceptWith (IEnumerable<T> other); // Удаляет все элементы, за исключением уникальных в одном или другом наборе
// Методы, не изменяющие исходный набор:
public bool IsSubsetOf (IEnumerable<T> other);
public bool IsProperSubsetOf (IEnumerable<T> other);
public bool IsSupersetOf (IEnumerable<T> other);
public bool IsProperSupersetOf (IEnumerable<T> other);
public bool Overlaps (IEnumerable<T> other);
public bool SetEquals (IEnumerable<T> other);

public int RemoveWhere (Predicate<T> match) // Удаление на основе предиката

public void UnionWith (IEnumerable<T> other); // Добавляет элементы множества в коллекцию (исключая дубликаты)

// Удаление подмножества из коллекции:

public void IntersectWith (IEnumerable<T> other); // Удаляет элементы, которые не присутствую сразу в обоих наборах

public void ExceptWith (IEnumerable<T> other); // Удаляет переданные элементы из коллекции

public void SymmetricExceptWith (IEnumerable<T> other); // Удаляет все элементы, за исключением уникальных в одном или другом наборе

// Методы, не изменяющие исходный набор:

public bool IsSubsetOf (IEnumerable<T> other);

public bool IsProperSubsetOf (IEnumerable<T> other);

public bool IsSupersetOf (IEnumerable<T> other);

public bool IsProperSupersetOf (IEnumerable<T> other);

public bool Overlaps (IEnumerable<T> other);

public bool SetEquals (IEnumerable<T> other);

SortedSet<T> дополнительно включает следующие члены:

public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)
public IEnumerable<T> Reverse ()
public T Min { get; }
public T Max { get; }

public virtual SortedSet<T> GetViewBetween (T lowerValue, T upperValue)

public IEnumerable<T> Reverse ()

public T Min { get; }

public T Max { get; }

Словари

Словарь — это коллекция, в которой каждый элемент является парой ключ-значение. В .NET для словарей предусмотрено два интерфейса IDictionary и IDictionary <TKey, TValue>, а также ряд готовых классов (несортированные: Dictionary <K,V>, Hashtable, ListDictionary, OrderedDictionary; сортированный: SortedDictionary <K,V>, SortedList <K,V>, SortedList). Различаются они по функционалу и по скорости извлечения значение.

Интерфейс IDictionary<TKey,TValue> и IDictionary

Интерфейс IDictionary<TKey,TValue> определяет стандартный протокол для всех коллекций основанных на парах ключ-значение. Он расширяет ICollection<T>, добавляя методы и свойства для доступа к элементам с помощью ключей произвольных типов:

public interface IDictionary <TKey, TValue> :
    ICollection <KeyValuePair <TKey, TValue>>, IEnumerable
{
    bool ContainsKey (TKey key);
    bool TryGetValue (TKey key, out TValue value);
    void Add (TKey key, TValue value);
    bool Remove (TKey key);
    TValue this [TKey key] { get; set; } // Индексатор по ключу
    ICollection <TKey> Keys { get; } // Возвращает только ключи
    ICollection <TValue> Values { get; } // Возвращает только значения
}

public interface IDictionary <TKey, TValue> :

ICollection <KeyValuePair <TKey, TValue>>, IEnumerable

{

bool ContainsKey (TKey key);

bool TryGetValue (TKey key, out TValue value);

void Add (TKey key, TValue value);

bool Remove (TKey key);

TValue this [TKey key] { get; set; } // Индексатор по ключу

ICollection <TKey> Keys { get; } // Возвращает только ключи

ICollection <TValue> Values { get; } // Возвращает только значения

}

Добавить элемент в словарь можно либо с помощью метода Add, либо по индексу (с помощью индексатора). В последнем случае если ключ в словаре отсутствует элемент будет добавлен, в противном случае обновлен. Дублированные ключи запрещены, поэтому вызов Add дважды с тем же ключом приведет к генерации исключения.

Для извлечения элементов из словаря используется либо индексатор, либо метод TryGetValue. Если ключ не существует, индексатор генерирует исключение, а метод TryGetValue вернет false. С помощью метода ContainsKey можно проверить наличие элемента в словаре (по ключу).

Перечисление словаря возвращает последовательность структур KeyValuePair:

public struct KeyValuePair <TKey, TValue>
{
    public TKey Key { get; }
    public TValue Value { get; }
}

public struct KeyValuePair <TKey, TValue>

{

public TKey Key { get; }

public TValue Value { get; }

}

Существует также интерфейс IReadOnlyDictionary<TKey,TValue> для словарей предназначенных только для чтения.

Необобщенный интерфейс IDictionary в принципе схож с обобщенным аналогом, за исключением двух отличий:

извлечение несуществующего ключа через индексатор дает null, а не генерирует исключение
членство проверяется с помощью Contains, а не ContainsKey

Перечисление по необобщенному IDictionary возвращает последовательность структур DictionaryEntry:

public struct DictionaryEntry
{
    public object Key { get; set; }
    public object Value { get; set; }
}

public struct DictionaryEntry

{

public object Key { get; set; }

public object Value { get; set; }

}

Dictionary<TKey,TValue> и Hashtable

Обобщенный класс Dictionary<TKey,TValue> использует хэш-таблицу для хранения данных, в связи с чем является быстрым и эффективным. Необобщенная версия Dictionary<TKey,TValue> называется Hashtable. Dictionary<TKey,TValue> реализует обобщенный и необобщенный интерфейсы IDictionary.

Пример использования Dictionary<TKey,TValue>:

var d = new Dictionary<string, int>();
d.Add("One", 1);
d["Two"] = 2; // Добавляет значение в словарь
d["Two"] = 22; // Обновляет значение
d["Three"] = 3;
Console.WriteLine (d["Two"]); // "22"
Console.WriteLine (d.ContainsKey ("One")); // true (быстрая операция)
Console.WriteLine (d.ContainsValue (3)); // true (медленная операция)
int val = 0;
if (!d.TryGetValue ("onE", out val))
    Console.WriteLine ("No val"); // "No val"
// Три способа перечисления словаря:
foreach (KeyValuePair<string, int> kv in d)
    Console.WriteLine (kv.Key + "; " + kv.Value);
foreach (string s in d.Keys) Console.Write (s);
    Console.WriteLine();
foreach (int i in d.Values) 
    Console.Write (i);

var d = new Dictionary<string, int>();

d.Add("One", 1);

d["Two"] = 2; // Добавляет значение в словарь

d["Two"] = 22; // Обновляет значение

d["Three"] = 3;

Console.WriteLine (d["Two"]); // "22"

Console.WriteLine (d.ContainsKey ("One")); // true (быстрая операция)

Console.WriteLine (d.ContainsValue (3)); // true (медленная операция)

int val = 0;

if (!d.TryGetValue ("onE", out val))

Console.WriteLine ("No val"); // "No val"

// Три способа перечисления словаря:

foreach (KeyValuePair<string, int> kv in d)

Console.WriteLine (kv.Key + "; " + kv.Value);

foreach (string s in d.Keys) Console.Write (s);

Console.WriteLine();

foreach (int i in d.Values)

Console.Write (i);

Лежащая в основе словаря хэш-таблица преобразует ключ каждого элемента в целочисленный хэш-код — псевдоуникальное значение — а затем преобразует хэш-код в хэш-ключ. Этот хэш-ключ и применяется для определения, какое значение к нему относится. Словарь может работать с ключами любого типа благодаря средствам определения эквивалентности ключей и получения хэш-кодов. По умолчанию эквивалентность определяется с помощью метода object.Equals ключа, а псевдоуникальный хэш-код получается через метод GetHashCode. Поведение по умолчанию можно изменить либо переопределив указанные методы, либо передав конструктору словаря объект IEqualityComparer.

Элементы Dictionary и Hashtable не отсортированы, порядок, в котором они добавляются не сохраняется. Дублированные ключи не разрешены.

OrderedDictionary

Класс OrderedDictionary — это необобщенный словарь, который сохраняет элементы в том же самом порядке, в котором они добавлялись. Он не является отсортированным словарем. Получать доступ к элементам можно и по индексу, и по ключу.

Класс OrderedDictionary представляет собой комбинацию Hashtable и ArrayList: он обладает все функциональность Hashtable, а также функциями вроде RemoveAt и целочисленным индексатором.

Обобщенной версии этого класса не существует.

ListDictionary и HybridDictionary

Класс ListDictionary использует односвязный список для хранения данных. Он не является сортированным массивом, но сохраняет исходный порядок элементов. ListDictionary работает исключительно медленно для больших списков, но эффективен для очень маленьких списков (до 10 элементов).

Класс HybridDictionary — это ListDictionary, который автоматически преобразуется в Hashtable при достижении определенного размера, решая проблему низкой производительности ListDictionary. Он позволяет получить низкое потребление памяти для маленьких словарей и высокую производительность для больших. Однако процесс перехода от ListDictionary к Hashtable является весьма затратным по производительности.

Отсортированные словари

.NET предусматривает два класса отсортированных словарей: SortedDictionary<TKey,TValue> и SortedList<TKey,TValue>. Их содержимое всегда сортируется по ключу.

Класс SortedDictionary использует структуру красно-черно дерева, в силу чего работает одинаково хорошо и при вставке, и при удалении элементов. Класс SortedList внутренне реализован с помощью пары упорядоченных массивов, что обеспечивает быстрое извлечение, но низкую производительность вставки.

Класс SortedDictionary намного быстрее, чем SortedList при вставке элементов, но последний обладает возможность доступа к элементам по индексу. Дублированные ключи в обоих классах недопустимы.

Настраиваемые коллекции

Collection<T> и CollectionBase

Обобщенный класс Collection<T> и необобщенный CollectionBase позволяют управлять тем, что происходит при добавлении или удалении элемента.

Класс Collection<T> является оболочкой для List<T> и определяет четыре дополнительных виртуальных метода и частное свойство:

public class Collection<T> :
    IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
{
    protected virtual void ClearItems ();
    protected virtual void InsertItem (int index, T item);
    protected virtual void RemoveItem (int index);
    protected virtual void SetItem (int index, T item);
    protected IList<T> Items { get; }
}

public class Collection<T> :

IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable

{

protected virtual void ClearItems ();

protected virtual void InsertItem (int index, T item);

protected virtual void RemoveItem (int index);

protected virtual void SetItem (int index, T item);

protected IList<T> Items { get; }

}

Необобщенный класс CollectionBase менее удобен в использовании. Он включает методы OnInsert, OnInsertComplete, OnSet, OnSetComplete, OnRemove,OnRemoveComplete,
OnClear и OnClearComplete, выполняющие тот же функционал.

KeyedCollection<TKey,TItem> и DictionaryBase

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

Дополнительные методы класса KeyedCollection<TKey,TItem>:

public abstract class KeyedCollection <TKey, TItem> : Collection <TItem>
{
    protected abstract TKey GetKeyForItem (TItem item); // Возвращает ключ
    protected void ChangeItemKey (TItem item, TKey newKey); // Изменяет ключ
    public TItem this [TKey key] { get; } // Индексный доступ по ключу
    protected IDictionary<TKey, TItem> Dictionary { get; } // Внутренний словарь
}

public abstract class KeyedCollection <TKey, TItem> : Collection <TItem>

{

protected abstract TKey GetKeyForItem (TItem item); // Возвращает ключ

protected void ChangeItemKey (TItem item, TKey newKey); // Изменяет ключ

public TItem this [TKey key] { get; } // Индексный доступ по ключу

protected IDictionary<TKey, TItem> Dictionary { get; } // Внутренний словарь

}

Класс DictionaryBase является необобщенной версиейKeyedCollection<TKey,TItem> и менее удобен в использовании.

ReadOnlyCollection<T>

Класс ReadOnlyCollection<T> является оболочкой для коллекции, делая ее доступной только для чтения. Конструктор класса принимает входную коллекцию и устанавливает на нее ссылку. Он не создает копии коллекции, поэтому если коллекция будет изменена из-вне, эти изменения будут видны через оболочку ReadOnlyCollection<T>.