NEWOBJ.ru → Введение в ООП с примерами на C# →

3.6. Обобщенное программирование

§ 44. Постановка задачи. Объектно-ориентированное и обобщенное (generic) программирование – независимые темы. Объектно-ориентированный язык может поддерживать, а может и не поддерживать механизмы обобщенного программирования. И наоборот, язык может поддерживать механизмы обобщенного программирования, но не быть объектно-ориентированным. Тем не менее, в современных объектно-ориентированных языках механизмы обобщенного программирования поддерживаются и, главное, широко применяются. Кроме того, обобщенное программирование в некотором смысле является развитием идеи иерархических типов данных. Поэтому мы обзорно рассмотрим эту тему в объеме, достаточном для применения обобщенных типов и понимания основных принципов их реализации.

Рассмотрим следующую задачу: необходимо создать односвязный список целых чисел int.

Каждый элемент односвязного списка хранит некоторое значение типа int и ссылку на следующий элемент. Нам потребуется два класса: элемент списка ItemInt и сам список ListInt.


// Элемент списка.
class ItemInt
{
  // Значение.
  public int Value;
  // Следующий элемент списка. Для последнего элемента Next == null.
  public ItemInt Next;
}
// Список.
class ListInt
{
  // Первый элемент списка. Для пустого списка first == null.
  private ItemInt first;
  // Последний элемент списка.
  private ItemInt last;
  // Добавление значения в конец списка.
  public void Add (int value)
  {
    if (first == null)
    {
      first = new ItemInt ();
      last = first;
    }
    else
    {
      last.Next = new ItemInt();
      last = last.Next;
    }
    last.Value = value;
  }
}

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


ListInt list = new ListInt();
list.Add(5);
list.Add(6);
list.Add(7);

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

Теперь расширим задачу: пусть нам потребовались такие же списки для хранения других типов данных, а именно: long, string, Point.

Если мы сделаем классы списков, аналогичные классу ListInt, то их код будет практически одинаковым, отличаясь только типом значения элемента списка. В приведенном выше фрагменте это две строки: поле Value класса ItemInt и тип аргумента value метода Add. Когда мы заменим тип int в этих строках на другой нужный нам тип, мы без каких-либо других изменений кода получим другой класс списка: ListLong, ListString и ListPoint. Однако, когда понадобится, например, добавить метод или исправить обнаруженную ошибку, то мы столкнемся с серьезной проблемой: изменения нужно будет синхронно вносить в несколько классов. К тому же разработчик может забыть или даже не знать, что есть другие классы, которые необходимо менять синхронно. Вообще, ситуация, когда фрагменты кода программы дублируются в нескольких местах – всегда источник ошибок и признак проблемы архитектуры57.

Как по-другому, не создавая копий кода, решить задачу создания нескольких классов, отличающихся только типом некоторого поля?

Если все интересующие нас типы полей наследуются от одного и того же базового класса, то мы могли бы использовать полиморфизм. Например, положим, есть классы Polygon, Circle и Square и все они наследуются от базового класса Shape. Тогда мы могли бы использовать класс ListShape для объектов любого из производных по отношению к Shape типов. Так, при передаче в метод Add переменной типа Polygon она будет неявно преобразовываться к типу Shape и сохраняться в элемент списка:


class ItemShape
{
  public Shape Value;
  public ItemShape Next; 
}
class ListShape
{
  public void Add (Shape value)
  {
  /* ,,, */
 }
}
Polygon p = new Polygon();
ListShape list = new ListShape();
list.Add (p); // тут неявное преобразование типа: list.Add ( (Shape)p );

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

Во-вторых, список ListShape может хранить элементы разных производных классов, то есть мы не можем гарантировать, что все элементы списка будут типа Polygon. Также мы вынуждены при чтении элементов использовать явное преобразование типа.


Polygon s1 = new Polygon();
Circle s2 = new Circle();
Square s3 = new Square();
list.Add (s1);
list.Add (s2);
list.Add (s3);
// Нет гарантии, что запрашиваемый элемент именно типа Polygon.
Polygon p = (Polygon) list.Get (0);

Таким образом, контроль однотипности элементов перекладывается на пользователя класса.

Ранее мы уже рассматривали класс object, от которого в C# неявно наследуются все другие классы и в который упаковываются значимые типы. Используя этот класс, мы можем обойти ограничение, связанное с необходимостью наличия общего класса. Рассмотрим следующий код:


// Элемент списка.
class Item
{
  public object Value;
  public Item Next;
}
// ... class ListObject { private Item first; // ...
long v1 = 1;
long v2 = 2;
ListObject list = new List();
list.Add(v1);
list.Add(v2);
long v = (long) list.Get(1);

Однако такое решение, во-первых, не снимает проблему отсутствия контроля однотипности объектов списка, а, во-вторых, расточительно для хранения списка значимых типов из-за необходимости упаковки и распаковки. Например, проанализируйте следующий рисунок, где сверху показан объект ListObject, хранящий три числа 1, 2, 3, упакованные в тип object, а снизу – объект ListInt, хранящий те же данные, но без упаковки, как значения.

Подводя итог, можно сформулировать, что, не вводя дополнительных механизмов в язык программирования, других универсальных решений разобранной задачи нет: или дублирование кода, или использование базового типа с отсутствием контроля однотипности и издержках упаковки и распаковки для значимых типов.

§ 45. Обобщенные классы. Каких именно возможностей языка не хватает для решения рассмотренных в предыдущем параграфе проблем? Не хватает возможности объявить «недоопределенный» класс, в котором не заданы некоторые типы, с возможность «доопределять» его, то есть указывать конкретные значения этих типов при использовании. Такой «недоопределенный» класс называется обобщенным классом, а процесс «доопределения» – конкретизацией.

Обобщенный класс (generic) – класс, в объявлении которого не заданы конкретные типы для некоторых из используемых им переменных. Конкретизация (reification) – создание класса путем задания в обобщенном классе конкретных типов вместо неопределенных типов-параметров.

Например, рассмотренный в предыдущем параграфе класс элемента списка Item можно объявить следующим образом:


class Item<T>
{
  public T Value;
  public Item<T> Next;
}

Угловые скобки после имени класса Item обозначают, что класс – обобщенный. В угловых скобках указывается имя типа-параметра. В коде класса мы используем это имя вместо конкретного типа, применяя такой же синтаксис, как если бы оно было именем класса: например, public T Value вместо public int Value. Чтобы конкретизировать этот обобщенный класс, то есть получить «доопределенную» его версию с конкретным типом вместо T, необходимо указать требуемый тип при использовании имени класса:


Item<int> item = new Item<int>();

Здесь объект item будет содержать поле Value типа int.

Мы можем использовать тип-параметр, как значение другого типа-параметра для другого обобщенного класса, используемого внутри нашего класса. Так, в примере выше, мы пишем public Item<T> Next и при объявлении типа Item<int> поле Next будет иметь тип Item<int>. Таким образом, упрощенно говоря, выполняется подстановка: везде в коде класса имя типа-параметра T заменяется именем конкретного типа.

Однако, в действительности, компилятор не просто заменяет одну строку в коде на другую. Продемонстрируем это, определив на основе класса Item<T> класс списка List<T>:


// Список.
class List<T> where T : new()
{
  // Первый элемент списка. Для пустого списка first == null.
  private Item<T> first;
  // Последний элемент списка.
  private Item<T> last;
  // Добавление значения в конец списка.
  public void Add (T value)
  {
    if (first == null)
    {
      first = new Item<T> ();
      last = first;
    }
    else
    {
      last.Next = new Item<T> ();
      last = last.Next;
    }
    last.Value = value;
  }

Обратим внимание на запись where T : new(). Это ограничение на тип-параметр T, указывающее, что подставляемый вместо T конкретный тип должен иметь конструктор по умолчанию. Если бы мы не задали это ограничение, то компилятор выдал бы ошибки на строках создания новых объектов: new Item<T>().

Также можно наложить ограничение, что тип должен быть всегда значимым или всегда ссылочным, что тип должен наследовать другой указанный тип или интерфейс. Мы не будем подробно рассматривать эти возможности, но отметим, что наличие таких ограничений отличает конкретизацию от простой подстановки: компилятор не просто заменяет одну строку («T») на другую («int»), а выполняет определенные проверки допустимости такой подстановки, обеспечивая гарантированную синтаксическую корректность кода для любых типов, удовлетворяющих заданным ограничениям. Это верно для C#, однако в общем случае реализация зависит от языка программирования.

Обобщенным может быть не только класс, но и отдельный метод и некоторые другие элементы языка. Кроме того, мы можем использовать более одного параметра-типа.


class Class 
{
  public void Method1<T> (T x) { /* ... */ }
  // Для метода Method2 T обозначает другой тип, чем T для метода Method1,
      //  так как это параметры уровня метода, а не класса.
  public T2 Method2<T, T2> (T x) { /* ... */ }
}

Также отметим, что обобщенные классы полностью поддерживают все механизмы наследования. Например, проанализируйте следующий код:


class ClassA<T> { /* … */ }
// Тип-параметр базового класс должен указываться при наследовании, в данном случае, для базового класса будет использоваться тот же тип-параметр, что и для производного.
class ClassB<T> : ClassA<T> { /* … */ }
// Здесь для базового класса явно указан конкретный тип.
class ClassC : ClassB<int> { /* … */ }

Имя типа-параметра может быть любым допустимым в C# именем переменной, например, мы могли бы написать: TItem, V. При этом в C# существует соглашение по именованию имен-параметров:, начинать с буквы T, например, TKey, TItem, TValue, также часто используют однобуквенные обозначения, например, T, K, V.

«Обобщенный класс» – наиболее устоявшийся и распространённый термин. Однако также используются другие термины: обобщение (буквальный перевод с англ., также жаргон: «дженерик»); шаблон (template – в C++, обратим внимание, что, возможно, встречавшийся читателю термин «шаблон проектирования» обозначает совершенно другое и на англ. для него используется слово pattern); универсальный шаблон; универсальный класс (в текущих версиях официальной русскоязычной документации C# используется именно этот термин, хотя в литературе по C# большее распространение имеет термин «обобщенный класс», который точнее по смыслу и по переводу). Конкретизацию (reification) также называют инстанциированием (англ. «создание экземпляра» – глагол от существительного instance, «экземпляр»), или параметризацией, или конструированием типа. Обобщенный тип, в котором заданы конкретные значения всех его параметров-типов, также называется закрытым (closed), иначе, если есть параметры-типы, для которых не заданы значения, – открытым (open).

В заключение обратим внимание на аналогию конкретизации с полиморфизмом: аналогично тому, как переменная базового типа в разные моменты выполнения программы может обозначать экземпляры разных производных типов, код обобщенного класса может использоваться для разных классов. Строго говоря, в теории языков программирования, полиморфизм, рассмотренный в главе 3.5 и являющийся одним из ключевых элементов ООП, называется «полиморфизмом подтипов», а обобщенные класс – «параметризуемым полиморфизмом». «Параметризуемым» в том смысле, что при объявлении переменной этого класса указывается параметр класса – тип. В обоих случаях (полиморфизм и обобщенные классы), речь идет о разновидности иерархического отношения «частное» – «общее»: везде, где можно использовать «общее», можно использовать «частное», что позволяет писать код только с «общим», подставляя «частное» при необходимости58.

Мы коротко рассмотрели понятие обобщенного класса. Этого должно быть достаточно для первого знакомства, так как на практике использование обобщенных классов и методов, как правило, интуитивно понятно. В следующих параграфах мы рассмотрим несколько примеров часто используемых обобщенных классов, а далее приведем ключевые особенности реализации обобщений в разных языках программирования. Для более глубокого, исчерпывающего, знакомства с темой обобщенного программирования на C# порекомендуем книгу [Скит 20].

§ 46. Примеры использования обобщенных классов. Зададимся вопросом: насколько часто возникают задачи, для которых необходимы средства обобщенного программирования? Ведь если такие задачи редки, то незачем усложнять язык программирования специальными возможностями, рассмотренными в предыдущем параграфе.

Список объектов некоторого типа – типичный пример повсеместно используемой структуры данных, поведение которой не зависит от типа хранимых данных. То есть именно такой структуры данных, для которой целесообразно использование обобщенных классов. К таким структурам данных относятся списки, очереди, стеки, словари, множества, деревья, а также алгоритмы, слабо зависящие от типа данных: сортировка (требует только поддержку метода сравнения), выборка по условию и другие. Эти структуры данных и алгоритмы повсеместно используются в практике программирования. С другой стороны, как правило, они предоставляются встроенными библиотеками языка, поэтому программист не так часто сам создает такие классы хотя, конечно, все зависит от специфики решаемых задач.

Рассмотрим коротко два часто применяемых обобщенных класса в C#: список List<T> и словарь Dictionary<K, V>. Эти классы размещены в пространстве имен System.Collections.Generics. Список представляет собой структуру данных для хранения списка значений с возможностью добавления в конец или в указанную позицию, удаления, перебора, получения значения по индексу и некоторых других.

Dictionary<K, V> – словарь – структура данных, позволяющая быстро находить объект-значение по значению объекта-ключа. Словарь состоит из множества пар ключ-значение. Добавление пары ключ-значение выполняется методом void Add (K key, V, Value). Ключи должны быть уникальны и при попытке добавление пары ключ-значение с ключом, уже добавленным в словарь ранее, возникнет исключение. Получение значения по ключу выполняется или оператором индексации [K key] или методом bool TryGetValue (K key, out V value). Оператор индексации используется, когда мы точно знаем, что значение в словаре есть, иначе возникнет исключение. Метод TryGetValue используется, когда уверенности в наличие ключа в словаре нет. Обратим внимание, что пары ключ-значение никак не упорядочены, соответственно, мы не можем получить их по индексу.

Рассмотрим использование классов List<T> и Dictionary<K, V> на примере следующей задачи: дан произвольный текст, нужно создать список индексов (позиций в тексте) для каждой из встречающихся букв. То есть нужно построить словарь, ключом которого будет буква char, а значением – список индексов List<int>.


// Анализируемый текст.
string text = “ABC”;
// Искомый словарь.
Dictionary<char, List<int>> dict = new Dictionary<char, List<int>>();
// Перебираем все символы текста подряд.
for (int i = 0; i < text.Length; i++)
{
  char c = text[i];
  List<int> list;
  // Проверяем, встречался ли уже ранее в тексте очередной символ…
  if (!dict.TryGetValue (c, out list))
  {
    // ... если не встречался, то создаем для него объект-список (пока пустой) и добавляем его в словарь.
    list = new List<int>();
    dict.Add (c, list);
  }
  // Здесь или, если объект встречался,
  // list – список содержащий предыдущие позиции, который возвратил метод TryGetValue,
  // или, если объект еще не встречался, созданный и добавленный в словарь выше пустой список.
  // В обоих случаях мы имеем созданный и добавленный в словарь список,
  // в который остается добавить очередной индекс.
  list.Add(i);
}
// Выводим сведения по букве A
List<int> listA = dict[‘A’];
Console.WriteLine (“Количество: ” + listA.Count);
// индексы
for (int i = 0; i < listA.Count; i++)
{
  Console.WriteLine (listA[i]);
}

Обобщенные классы структур данных используются повсеместно, вы чаще встретите класс List<int>, чем массив int[]. Назовем еще несколько обобщенных классов структур данных из стандартной библиотеки C#: HashSet<T>, стек Stack<T>, очередь Queue<T>.

§ 47. Реализация. Реализация механизмов обобщенного программирования может существенно различаться в разных языках.

В C# конкретизация происходит на этапе выполнения при первом обращении к классу. Например, при первом обращении в коде к классу List<int> среда исполнения .NET Framework создает (компилирует) новый класс, как если бы программист реализовал класс ListInt. Рассмотрим следующий пример:


class A<T>
{
  public static int X = 0;
}
A<int>.X = 1;
A<long>.X = 2;
Console.WriteLine (A<int>.X);  // вывод: 1
Console.WriteLine (A<long>.X); // вывод: 2

При первом обращении к типу A<int> создается (компилируется) новый класс и в его статическое поле X присваивается значение 1. Далее, при обращении к типу A<long> создается другой класс и в его статическое поле X присваивается значение 2. При повторном же обращении к этим типам в последних двух строках используются уже созданные классы и, соответственно, выводятся присвоенные ранее значения статических полей.

Таким образом, в плане производительности при использовании обобщенного типа нет дополнительных издержек. Поддержка обобщенных классов в C# появилась во второй версии языка в 2005 г., через 3 года после первого выпуска.

В Java поддержка обобщенных классов была добавлена в версии 5 в 2004 г., спустя 8 лет после первого выпуска языка. В Java конкретизации как таковой не выполняется. Вместо этого при компиляции программы происходит стирание типов (type erasure) – замена типов-параметров обобщенного класса на тип Object и добавление неявного преобразования и контроля для обеспечения строгой типизации. То есть на уровне компиляции реализуется рассмотренный в предыдущем параграфе вариант с полиморфизмом на основе типа object. Так, класс List<Point> компилятор заменяет на класс List, использующий тип Object и добавляет преобразование от Object к Point при чтении значений и обратно – при записи. Соответственно, мы не можем использовать в качестве параметров значимые типы.

Отметим в заключение, что несмотря на существенные различия сама концепция обобщенного класса (интерфейса, метода) вполне стабильна. Так, концептуально List<Point> в C#, Java и C++ (и других языках – дело не в синтаксисе) идентичны, а отличия, как правило, лежат в плоскости вопросов дополнительных издержек и ограничений на используемые типы и операции.

Вопросы и задания

  1. Дайте определения следующим терминам, а также сопоставьте русские и английские термины: обобщенный класс, обобщение, шаблон, конкретизация, инстанциирование, параметризация, открытый класс, закрытый класс, generic, reification.

  2. Является ли поддержка обобщений необходимым элементом объектно-ориентированных языков программирования? Какие из известных вам языков поддерживают механизмы обобщенного программирования?

  3. В C# до версии 3 не было поддержки обобщенных классов. Так, вместо List<T> предлагался класс ArrayList, представляющий собой список объектов типа Object. Для обратной совместимости этот класс и сейчас включен в .NET Framework. Объясните почему его не следует никогда использовать?

  4. Напишите программу, демонстрирующую различие в производительности операций чтения и записи последовательности случайных чисел типа int в список List<int> и ArrayList.

  5. Изучите другие, не рассмотренные в тексте, методы, свойства и конструкторы классов List<T> и Dictionary<K, V>.

  6. Познакомьтесь со следующими обобщенными классами из пространства имен System.Collections.Generics: HashSet<T>, Stack<T>, Queue<T>.

  7. Заменим в рассмотренном в § 46 примере тип char на пользовательский тип Letter, например, для хранения какой-либо вспомогательной информации о букве:


class Letter { public char C; }
// ...
Dictionary<Letter, List<int>> dict = new Dictionary <Letter, List<int>>();
// ...
Letter c = new Letter();
c.C = text[i];
//...

Объясните, почему приведенный код не будет работать корректно?

  1. * Каким образом следует модифицировать код класса Letter, чтобы исправить проблему, обозначенную в предыдущем вопросе?

  2. В некоторых языках программирования есть препроцессор – приложение, выполняемое перед запуском компилятора и некоторым образом преобразующее код, согласно специальным инструкциям, называемым директивами препроцессора. Так, в C++ мы можем задать необходимость замены указанной последовательности символов в коде на другую:


#define TABLE_SIZE 100
int table1[TABLE_SIZE];

Компилятор на вход получит следующий код:


int table1[100];

Объясните, почему использование препроцессора не позволит решить задачу с обобщенными классами?

  1. * Имеет ли смысл ограничение на параметр обобщенного класса where T : new() для значимых типов?

  2. Что выведет следующий код:


class Class<T> { public static int Value; }
void Main() { Class<int>.Value++; Console.WriteLine ( Console<float>.Value ); }

  1. ** Изучите тип данных Nullable<T>.

Примечания:

  1. 57.  Если, конечно, это не случайное совпадение (accidental duplication) фрагментов разного по смыслу кода, которые не обязательно должны меняться синхронно.

    ↩︎

  2. 58.  Отметим также третий (наиболее нестрогий) способ определения обобщенного класса (первый способ – через идею «доопределния», второй – через идею полиморфизма): обобщенный класс – это класс класса, или метакласс. И аналогично тому, как объект – экземпляр класса, класс – экземпляр метакласса. Такая идея была реализована в некоторых ранних языках, но сегодня проявляется только через механизмы обобщенного программирования или статических полей.

    ↩︎

О сайте, об авторе, контакты, оставить отзыв.

Телеграм-канал: newobjx.

© Тимофей Усов, 2019—2020.