Лекция 17 (лекции (2002)), страница 2

Соответствующим фактическим параметром может быть любой фиксированный тип данных.

delta H range L..R;

Н – шаг.

1. Подпрограммы. Фактическим параметром может быть подпрограмма, которая полностью удовлетворяет прототипу.

2. Объекты данных. Например

X: T;

где Т – это известный тип данных. Соответствующим фактическим параметром может быть только константное выражение.

В результате мы получаем достаточно мощный механизм статической параметризации, который допускает достаточно эффективную реализацию. В первом издании одной из книг, посвященной объектно-ориентированному проектированию, в качестве примера приводился язык Ада 83. Ада не совсем объектно-ориентированный язык, но в нем есть понятие родовых абстракций. С помощью статической параметризации можно написать некоторые вещи в объектно-ориентированном стиле.

В Аде 83 подпрограмма не является объектом данных потому, что создатели сочли достаточным сделать подпрограмму родовым параметром. Поэтому, чтобы написать функцию, которая может считать произвольный интеграл, у нее должен быть параметр - подынтегральная функция. Такого рода функции в языке Ада нужно писать с помощью родового механизма, передавая подынтегральную функцию, как родовой параметр соответствующей процедуры. Это единственная возможность передавать процедуру как параметр в языке Ада.

Писать родовые абстракции – не самое приятное занятие.

C++.

Язык С++ представляет несколько другой образец статической параметризации. В языке С++ соответствующий механизм называется шаблоны (templates). В языке С++ объектами статической параметризации являются классы и функции. Синтаксис очень простой как и в Аде

template<список аргументов>

спецификация класса или функции;

Различия в видах параметров. В языке С++ применяется только 3 вида параметров (раньше их было 2, третий тип параметров добавился для удобства):

1. Тип.

2. Функция.

3. Объект данных.

В Аде 4 различных типовых параметра (произвольный тип с операцией присваивания, дискретный тип, два вида плавающих типа).

Пример со стеком омжет выглядеть так:

template<class T, int size>

class Stack{

T body[size];

int top;

public:

Stack();

T Pop();

void Push(T & x);

…

}

size – параметр – объект данных. Конкретизировать ее можно следующим образом:

Stack<int, 256> S;

Имя шаблона класса<фактические параметры> имя;

Не смотря на то, что написано class T фактическим параметром может являться любой тип данных.

Stack<int, 64> S1;

Stack<int, 128* 2> S2;

Переменные S и S2 являются переменными одного и того же типа. В С++ описание соответствующих абстракций и их использование существенно проще.

void Sort(T arr[], int n);

Информация о длине массива передается динамически. Соответствующий родовой шаблон

template<class T>

void Sort(T arr[], int n);

Проектирование шаблонов на первый взгляд выглядит значительно проще, чем в языке Ада. Параметризуем классом. В С++ все индексы целочисленные. Следовательно, их параметризовать не надо. Для такого прототипа родовой функции мы сразу можем написать алгоритм. В теле соответствующей функции будет нечто типа

if (arr[i]<arr[j]) …

В прототипе нет никакой информации о Т кроме того, что Т – имя типа. Это касается и абстракции Stack. Как компилятор может сгенерировать соответствующий код ничего не зная о типе Т? В случае Ады разработчик компилятора может принять решение чтобы обязательным параметром такого родового модуля является размер соответствующего типа. Где-то есть переменная, в которой находится размер этого типа, и компилятор, когда будет генерировать, например операцию присваивания, будет эту информацию использовать. В случае языка С++, априори предсказать какая именно информация потребуется о классе Т совершенно невозможно. Для стека, единственная операция, которую мы выполняем с типом Т – это операция копирования. У типа Т должна быть операция присваивания и соответствующий конструктор копирования. Для процедуры Sort о классе Т нужно знать не только как его копировать, но и как сравнивать элементы. Ада скронструирована так, что контекст конкретизации никак не зависит от контекста определения. Это с одной стороны хорошо потому, что позволяет, во-первых, эффективно работать с родовыми сегментами, во-вторых, позволяет достаточно эффективную реализацию. В языке С++ определения гибкое. Там трансляция, т.е. генерация кода для родового сегмента, должна явным образом зависеть от контекста конкретизации.

class X{

private:

X & operator =(X &);

X(X &);

};

В классе Х объявлены как приватные функции оператор присваивания и конструктор копирования. Объект этого класса нельзя присваивать объектам другого класса. Конкретизация

Stack<X, 64> a;

не пройдет, поскольку иначе нарушится правило надежности. А главное требование к статической параметризации – надежность. При реализации класса Stack потребуются оператор присваивания и конструктор копирования. Получается, что генерация кода может произойти только в контексте конкретизации. Во-первых, тогда компилятор уже обладает информацией о типе для того, чтобы сгенерировать, во-вторых, компилятор обладает достаточной информацией, чтобы проверить (надежность – это прежде всего проверка). Только в момент конкретизации компилятор может сказать, что эта она не верна потому, что приватная функции присваивания. Аналогично

typedef int a[56];

typedef a b[128];

Sort(b, 128);

b – массив из 128 элементов, каждый из которых представляет собой массив из 56 элементов. Компилятор выдаст сообщение об ошибке потому, что для типа данных а нет операции сравнения и операции присваивания. Компилятор, когда встречает шаблон, максимум что может сделать - провести лексический анализ. Весь основной семантический анализ и генерация кода откладываются до конкретизации. Этим разработчики языка С++ платят за гибкость. Вкупе с другими не очень приятными особенностями языка С++ этот механизм становится очень тяжелым. Шаблоны классов мы конкретизируем явно. Можно написать

typedef Stack<int, 1024> IntStack;

Явной конкретизации шаблонов функций как таковой не было в первоначальной спецификации шаблонов, котороя была принята к 91 г.. Можно написать

int arr[1024];

Sort(int, 1024);

Т.е. обращение к родовой функции одновременно является и конкретизацией. Здесь применяется тот же самый механизм, что и для обычных функций – механизм перекрытия операций. Компилятор видит, что это шаблон, отождествляет Т <= int. Каждая родовая функция соответствует одноименным конкретизированным функциям (компилятор генерирует одноименные функции). Если мы обратимся с массивом char он сгенерирует новую функцию Sort, и т.д. Имена у всех одинаковые, т.е. используя правила перекрытия компилятор будет разбираться, какую Sort нужно выбрать в данном конкретном случае. С одной стороны это очень удобно. Вы даже не задумываетесь о механизме конкретизации соответствующего шаблона, но с точки зрения реализации возникает куча всякого рода проблем. Во-первых, пусть

Stack<int, 256> S;

…

Stack<int, 128 * 2> S1;

Компилятор не должен второй раз генерировать функции-члены класса Stack, поскольку речь идет об одном и том же типе данных. Т.е. компилятор должен держать таблицу сгенерированных функций, чтобы повторно не генерировать функции для одного и того же типа данных. Это первая проблема. Вспомним также о механизме раздельной трансляции в языке С++. Раздельная трансляция в языке С++ является независимой. Если в другом модуле где-то есть

Stack<int, 256> X;

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

X.Push(1);

- вызов неопределенной функции Push, компановщик выдает ошибку, после чего транслятор генерирует код, снова запускает компановщик. И так до тех пор пока не избавимся от всех ошибок подобного рода.

Еще одна проблема, которая возникла сразу же. По старому варианту не было возможности писать функции типа

template<class T>

T f(void);

потому, что информация о конкретизации должна была выводиться исключительно из списка формальных параметров. Если списка формальных параметров нет, никакой информации о конкретизации мы почерпнуть не можем. Механизм, который частично преодолевает подобного рода проблемы в стандарте языка С++ - механизм явной конкретизации (как для функций, так и для классов). Если в предыдущих случаях компилятор решал генерировать код или нет, то по новому синтаксису можно писать так

template< > class Stack<int, 256>;

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

template< > void Sort<arr>(int a[], int n);

Здесь генерируется код. При таком режиме программист сам управляет моментом, когда генерировать соответствующие функции, что в результате существенно уменьшает общее время на трансляцию. Если поставить такую строку в двух местах, то, в зависимости от реализации, компилятор может выдать ошибку. Проблемы на этом не кончаются. Шаблоны в языке С++ должны описываться несколько в другом стиле, чем обычные модули. Пусть есть некоторый сервис. Его интерфейс мы называем заголовочным файлом (name.h),а реализацию – С++-файлом (name.cpp). Клиентские модули могут содержать

#include<name.h>

Если в name.h и name.cpp содержаться шаблоны (неважно функции это или классы), информации интерфейса (template<…>…) явно не достаточно. Для того, чтобы использовать (конкретизировать) соответствующий класс, нам необходимо знать текст реализации. Поэтому получается, что в случае шаблонов необходимо реализацию (т.е. текст всех соответствующих функций) переносить в заголовочный файл. Это не выгодно разработчикам коммерческих библиотек. И это неизбежно, поскольку никакого другого механизма нет. Единственное, что может изменить ситуацию – ввод механизм раздельной зависимой трансляции. Но этот механизм никак не стандартизован. Поэтому, реально для того, чтобы у нас была используемая библиотека шаблонов классов, мы должны полностью ее поставлять (полностью open source). С определенной точки зрения это не очень хорошо. Большинство библиотек шаблонов либо поставляются разработчиками в исходных текстах (например, MFC), либо поставляют по open source. Это следствие механизма трансляции в языке С++ и проблем, связанных с тем, что компилятор может сгенерировать код только с учетом контекста конкретизации. В современном С++ появился механизм явной спецификации параметров. Если для классов механизм явной спецификации параметров поддерживался изначально, то для функций появился дополнительный синтаксис. Мы можем написать

Sort<int>(int, 256);

Основное отличие от случая явной конкретизации в том, что в этой точке будет сгенерирован код или нет – на усмотрение компилятора (на усмотрение реализации). Классический пример с родовой функцией сортировки в языке С++ связан с другой абстракцией. Мы пишем свой шаблонный класс

template<class T>

class vector{…};

Тогда обобщенная функция сортировки выглядит так

template<class T> void Sort(Vector<T> &V);

Есть понятие инициализации шаблонов по умолчанию. Например класс String в стандартной библиотеке выглядит так

template<class ch, class traits = char_traits<ch>, Allocator = Alloc<ch>> class basic_string{…};

Класс ch – класс символов. char_traites –это набор функций, которые должен поддерживать любой символьный класс. Это очень напоминает ситуацию с языком Ада, когда всю информацию о типе (в том числе операции) мы должны специфицировать явным образом в определении. В STL указано, что, во-первых, char_traits содержит исключительно набор функций, который можно выполнять с любым символом (например, любые символы можно сравнивать между собой). char_traits<ch> – значение по умолчанию traits. Если нас не удовлетворяет стандартная реализация char_traits (например, нас не удовлетворяет функция сравнения) мы можем в качестве traits указать свой класс char_traits.

template<class T> class char_traits{…};

Allocator – распределитель памяти. Если нас не удовлетворяет стандартный распределитель памяти, мы можем написать свой, оптимизировав его для конкретной задачи. Alloc – стандартный шаблонный класс. В результате можно просто написать

typedef basic_string<wchar_t> UniString;

Специализируем явным образом. Нас утраивают все параметры по умолчанию. С++ с этой точки зрения дает очень большую гибкость. Хитрые алгоритмы реализации позволяют еще встраивать так называемый inline код. В библиотеке STL понятие алгоритма – мы задаем контейнер и некоторую функцию, и алгоритм эту функцию равномерно применяет к классу. Один из вариантов – использовать вместо функции специальный класс, у которого перекрыта операция ( ). В результате, для того, чтобы написать свою функцию, переопределяем этот стандартный класс, эту функцию, которую мы хотим применить, переопределяем как оператор

operator ( ) {…};

и соответствующий класс делаем параметром алгоритма. Эта ситуация хороша тем, что функция передается не как указатель, а как некоторая inline функция (встраиваемая). В результате эффективность подобного рода алгоритма становится значительно больше (на уровне применения макроподстановки). Именно это богатство механизма шаблонов является причиной того, что современные реализации библиотек шаблонов на С++, по эффективности сравнимы с очень хорошими оптимизирующими компиляторами такими как с ФОРТРАНА, с С. За это нужно платить тем, что каждая мало-мальски богатая библиотека шаблонов должна приспосабливаться к конкретной реализации. Не существует, и не может существовать единого текста STL (стандартная библиотека шаблонов) потому, что STL настолько сложна, использует настолько хитрые свойства компилятора С++, что не существует двух компиляторов, которые бы одинаково компилировали эту библиотеку. Известно, что до сих пор в реализациях фирмы Microsoft некоторые вещи, которые присутствуют в канонической реализации STL не могут компилироваться. Поэтому существует специальная реализация STL для компиляторов Microsoft. Для каждой реализации компилятора необходима своя реализация (своя переделка) STL. И такая ситуация, к сожалению, практически со всеми мощными библиотеками шаблонов. Почему Страуструп и говорил, что его самой главной ошибкой при написании языка С++ было то, что создание шаблонов он отложил. Шаблоны появились в языке только в 91 г. Но не смотря на эту проблему механизм шаблонов является очень мощным. Настоящая библиотека шаблонов – достаточно сложная вещь, к тому же плохо переносимая (эта ситуация может измениться в течение ближайших 5 лет). Использовать библиотеки шаблонов безусловно надо. Рекомендуется изучить STL, Blits, Boost, Loki (они все - open source библиотеки). Один из создателей последней версии компилятора Visual С++ сказал: "у нас удовлетворение стандарту лучше, чем в прошлой версии, но до сих пор только 98%. Соответствие стандарту на 98% значит, что есть какой-то набор тестов, при их пропуске только 2% строчек выдали ошибку при компиляции. Мы хотели не столько удовлетворить стандарту, сколько, чтобы компилировалась STL."