со стеками
Ограниченная универсальность
Хорошо, когда есть свобода. Еще лучше, когда свобода ограничена. Аналогичная ситуация имеет место и с универсальностью. Универсальность следует ограничивать. На типы универсального класса, являющиеся его параметрами, следует накладывать ограничения. Звучит парадоксально, но, наложив ограничения на типы, программист получает гораздо большую свободу в работе с объектами этих типов.
Если немного подумать, то это совершенно естественная ситуация. Когда имеет место неограниченная универсальность, над объектами типов можно выполнять только те операции, которые допускают все типы, — в C# это эквивалентно операциям, разрешенным над объектами типа object, прародителя всех типов. В нашем предыдущем примере, где речь шла о свопинге, над объектами выполнялась единственная операция присваивания. Поскольку присваивание внутри одного типа разрешено для всех типов, то неограниченная универсальность приемлема в такой ситуации. Но что произойдет, если попытаться выполнить сложение элементов, сравнение их или даже простую проверку элементов на равенство? Немедленно возникнет ошибка еще на этапе компиляции. Эти операции не разрешены для всех типов, поэтому в случае компиляции такого проекта ошибка могла бы возникнуть на этапе выполнения, когда вместо формального типа появился бы тип конкретный, не допускающий подобную операцию. Нельзя ради универсальности пожертвовать одним из важнейших механизмов C# и Framework.Net — безопасностью типов, поддерживаемой статическим контролем типов. Именно поэтому неограниченная универсальность существенно ограничена. Ее ограничивает статический контроль типов. Бывают, разумеется, ситуации, когда необходимо на типы наложить ограничения, позволяющие ослабить границы статического контроля. На практике универсальность почти всегда ограничивается, что, повторяю, дает большую свободу программисту.
В языке C# допускаются три вида ограничений, накладываемых на родовые параметры.
• Ограничение наследования. Это основный вид ограничений, указывающий, что тип T является наследником некоторого класса и ряда интерфейсов. Следовательно, над объектами типа T можно выполнять все операции, заданные базовым классом и интерфейсами. Эти операции статический контроль типов будет разрешать и обеспечивать для них интеллектуальную поддержку, показывая список разрешенных операций. Ограничение наследования позволяет выполнять над объектами больше операций, чем в случае неограниченной универсальности. Синтаксически ограничение выглядит так: where Т: BaseClass, I1…Ik.
• Ограничение конструктора. Это ограничение указывает, что тип T имеет конструктор без аргументов и, следовательно, позволяет создавать объекты типа T. Синтаксически ограничение выглядит так: where Т: new().
• Ограничение value /reference. Это ограничение указывает, к значимым или к ссылочным типам относится тип T. Для указания значимого типа задается слово struct, для ссылочных — class. Так что синтаксически этот тип ограничений выглядит так: where T: struct.
Возникает законный вопрос: насколько полна предлагаемая система ограничений? Конечно, речь идет о практической полноте, а не о математически строгих определениях. С позиций практики систему хотелось бы дополнить, в первую очередь, введением ограничений операций, указывающим допустимые знаки операций в выражениях над объектами соответствующего типа. Хотелось бы, например, указать, что к объектам типа т применима операция сложения + или операция сравнения <. Позже я покажу, как можно справиться с этой проблемой, но предлагаемое решение довольно сложно. Наличие ограничения операций намного элегантнее решало бы эту проблему.
Синтаксис ограничений
Уточним некоторые синтаксические правила записи ограничений. Если задан универсальный класс с типовыми параметрами T1,… Tn, то на каждый параметр могут быть наложены ограничения всех типов. Ограничения задаются предложением where, начинающимся соответствующим ключевым словом, после которого следует имя параметра, а затем через двоеточие — ограничения первого, второго или третьего типа, разделенных запятыми. Порядок их важен: если присутствует ограничение третьего типа, то оно записывается первым. Заметьте, предложения where для разных параметров отделяются лишь пробелами; как правило, они записываются на отдельных строчках. Предложения where записываются в конце заголовка класса после имени и списка его типовых параметров, после родительских классов и интерфейсов, если они заданы для универсального класса. Вот синтаксически корректные объявления классов с ограничением универсальности:
public class Father<T1, Т2>
{ }
public ckass Base
}
public void M1() { }
public void M2() { }
}
public class Child<T1,T2>:Father<T1,T2>
where T1:Base,IEnumerable<Tl>, new()
where T2:struct,IComparable<T2>
{ }
Класс child с ограниченной универсальностью к данным типа T1 имеет право применять методы M1 и M2 базового класса Base; так же, как и методы интерфейса iEnumerabie<T1>, он может создавать объекты типа T1, используя конструктор по умолчанию. Фактический тип, подставляемый вместо формального типа Т2, должен быть значимым, и объекты этого типа разрешается сравнивать между собой.
Список с возможностью поиска элементов по ключу
Ключевые идеи ограниченной универсальности, надеюсь, понятны. Давайте теперь рассмотрим пример построения подобного класса, где можно будет увидеть все детали. Возьмем классическую и саму по себе интересную задачу построения списка с курсором. Как и всякий контейнер данных, список следует сделать универсальным, допускающим хранение данных разного типа. С другой стороны, мы не хотим, чтобы в одном списке происходило смешение типов, — уж если там хранятся персоны, то чисел int в нем не должно быть. По этим причинам класс должен быть универсальным, имея в качестве параметра тип T, задающий тип хранимых данных. Мы потребуем также, чтобы данные хранились с их ключами. И поскольку не хочется заранее накладывать ограничения на тип ключей — они могут быть строковыми или числовыми, — то тип хранимых ключей будет еще одним параметром нашего класса. Поскольку мы хотим определить над списком операцию поиска по ключу, то нам придется выполнять проверку ключей на равенство, поэтому универсальность типа ключей должна быть ограниченной. Проще всего сделать этот тип наследником стандартного интерфейса IComparable.
Чтобы не затемнять ситуацию сложностью списка, рассмотрим достаточно простой односвязный список с курсором. Элементы этого списка будут принадлежать классу Node, два поля которого будут хранить ключ и сам элемент, а третье поле будет задавать указатель на следующий элемент списка. Очевидно, что этот класс должен быть универсальным классом. Вот как выглядит текст этого класса:
class Node<K, Т> where К: IComparable<K>
{
public Node()
{
next = null; key = default(K); item = default(T);
}
public К key;
public T item;
public Node<K, T> next;
}
Класс Node имеет два родовых параметра, задающих тип ключей и тип элементов. Ограничение на тип ключей позволяет выполнять их сравнение. В конструкторе класса поля инициализируются значениями по умолчанию соответствующего типа.
Рассмотрим теперь организацию односвязного списка. Начнем с того, как устроены его данные:
public class OneLinkList<K, Т> where К: IComparable<K>
{
Node<K, T> first, cursor;
}
