Лекция 23. Шаблоны (часть 3) Красс Александр СПбГУ ИТМО, 2008

Темы Частичная специализация Неполная специализация Шаблонные члены класса Шаблоны как параметры шаблона Функциональные объекты Traits

Частичная специализация Нам уже знакома полная специализация: template class vector { … }; template<> class vector { …}; Частичная специализация производится для подтипа: template class vector { }; // специализация вектора для указателей. vector может проходить по своему содержимому и вызывать delete для каждого элемента. STL такой специализации нет.

Частичная специализация (2) А для чего еще можно выполнять частичную специализацию? const TКонстантные типы T*Указатели T&Ссылки T[integer-const]Массивы Type(*)(T)Указатель на функцию с параметром типа T T(*)()Указатель на функцию, возвращающую T T(*)(T)Указатель на функцию с параметром типа T и возвращающую T

Неполная специализация Неполная специализация позволяет нам указать часть параметров шаблона. template class Map {…}; Вариант Map для случая, когда ключ задается целым: template class Map {…}; Неполная специализация не нужна для шаблонных функций, т.к. там можно обойтись перегрузкой.

Шаблонные члены класса Иногда имеет смысл делать шаблонными не весь класс, а отдельные методы. Рассмотрим шаблонный класс Array: template class Array { … }; Array это динамический массив в стиле C++. Когда ему нужно перераспределить память, он вызывает оператор new, а когда удалить, оператор delete. Очевидно, что для разных случаев нужны разные стратегии управления памятью. (Пояснить?)

Шаблонные члены класса (2) Вынесем стратегию управления памятью в отдельный класс: class StdMemoryMgr { public: template static T* alloc(int n) { return new T[n]; } template static void free(T *p) { delete[] p; } }; Реализуя разные версии этого класса, мы поддерживаем разные стратегии управления памятью. Например, вот так: class NoFreeMemoryMgr { public: template static T* alloc(int n) { return new T[n]; } template static void free(T *p) {} }; Класс NoFreeMemoryMgr можно использовать, если удаление очень дорого и оно нам не критично,

Шаблонные члены класса (3) Теперь наш класс Array будет иметь следующий вид: template class Array { … }; Выделение памяти в классе будет производиться так: T* buf = Allocator::alloc (size); Освобождение памяти так: Allocator::free (buf);

Шаблоны как параметры шаблона Аргументами шаблона могут быть не только простые типы, но и типы основанные на шаблонах К примеру, рассмотрим структуру данных стек. У него есть следующие операции: –Push – помещаем элемент в стек –Pop – удаляем элемент из стека –Size – количество элементов в стеке Стек может быть реализован или на базе списка или на базе массива. Если мы автора класса Stack, мы не можем за пользователя решать, какую структуру нам использовать. Вынесем структуру в параметр шаблона template > class Stack { void Push(const Type &v) { impl.push_back (v); } void Size() const { impl.size(); } … private: Container impl; }; Использование: 1. Stack si1; // стек на базе структуры данных по умолчанию (массива) 2. Stack > si2 ; // стек на базе списке. Обратите внимание на пробел между знаками >.

Функциональные объекты Рассмотрим функцию find1, которая ищет указанное число в массиве типа int: const int* find1 ( const int* pool, int n, int x ) { const int* p = pool; for ( int i = 0; i<n; i++ ) { if ( *p == x ) return p; // success p++; } return 0; // fail } Пример использования: int A[100]; // заполнить A int* p = find1(A,100,5); // найти 5 в массиве

Функциональные объекты (2) Обобщим нашу функцию find, добавив возможность поиска элемента по произвольному условию: const int* find2 ( const int* pool, int n, bool (*cond)(int) ) { const int* p = pool; for ( int i = 0; i<n; i++ ) { if ( cond(*p) ) return p; // success p++; } return 0; // fail } Пример использования: int A[100]; bool cond_e5 ( int x ) { return x==5; } int* p = find2(A,100,cond_e5); // найти элемент массива такой, что cond_e5(A[i]) равен true Другой пример такого дизайна функция qsort из стандартной библиотеки: void qsort ( void* base, // first element size_t num, // number of elements size_t width, // element size int (*compare)(const void*, const void*) ); // comparing function

Функциональные объекты (3) В итоге для реализации обобщенного поведения некоторой функции нам надо передать в нее callback, который и будет выполнять настройку поведения этой функции Этот подход имеет и достоинства и недостатки: –Механизм очень гибкий –Низкая скорость из-за лишних вызовов функций. (Функции по указателю нельзя встроить) Хорошо бы сохранить гибкость callback и увеличить скорость. Воспользуемся помощью классов и шаблонов.

Функциональные объекты (4) Тип с определенным оператором вызова функции называется функциональным типом. Функциональные типы делятся на встроенные и определяемые пользователем –Указатель на функцию – это встроенный тип –Класс с оператором вызова функции – определяемый пользователем

Функциональные объекты (5) После замены указателей на функциональные объекты и приведения функции к шаблонному виду получим: template T* find3 ( T* pool, int n, Comparator comp ) { T* p = pool; for ( int i = 0; i<n; i++ ) { if ( comp(*p) ) return p; // success p++; } return 0; // fail } Новая версия имеет следующие преимущества: –Ищет в массиве любого типа –Ищет по любому критерию –Она быстрее, чем find2, если оператор вызова функции встраивается.

Функциональные объекты (6) Теперь мы можем использовать find3 следующим образом: 1. Определим предикат поиска: template class less { public: bool operator()(T x) const { return x < N; } }; 2. Используем: int *p = find3(A, 100, less ()); 3. В STL есть аналогичная функция std::find и набор аналогичных предикатов на все случаи жизни.

Traits Предположим, нам надо написать набор математических функций, работающих с разными типами данных: float, double, long double, плюс типы, определяемые пользователем. При реализации этих функций нам хотелось бы знать о свойствах этих типов: –Максимальное и минимальное значение –Точность –И пр. Реализация этих функций должна быть максимально обобщенной. Следовательно, используем шаблоны:

Traits (2) Все эти величины для стандартных типов определены в файле float.h: /* Smallest value such that 1.0+xxx_EPSILON != 1.0 */ #define DBL_EPSILON e-016 #define FLT_EPSILON e-07F #define LDBL_EPSILON e-019L /* max value */ #define DBL_MAX e+308 #define FLT_MAX e+38F #define LDBL_MAX e+4932L Но как организовать доступ к этим величинам из наших функций, в зависимости от типа аргументов? template bool IsZero(T val) { return abs(val) < 10 * eps; } // eps – своя для каждого типа. Решение заключается в использовании Traits-ов

Traits (3) 1. Определим обобщенный trait для всех типов: template class float_attrs { /* Пусто. Мы ничего не можем сказать про неизвестный тип. */}; template class float_attrs // для double { public: typedef double float_type; static inline float_type epsilon() { return DBL_EPSILON; }... }; 2. Теперь определим специализацию этого класса для различных типов: template struct float_attrs // для float { public: typedef float float_type; static inline float_type epsilon() { return FLT_EPSILON; }... };

Traits (4) Функция IsZero: template bool IsZero(T val) { return abs(val) ::epsilon(); } Использование: IsZero(1.f); // используем float_attrs float_attrs это и есть трейд с, хранящий атрибуты чисел с плавающей запятой. Другое применение traits-ов это реализация стратегий, изменяющих поведение объекта.

20 Спасибо за внимание Вопросы?