Лекция 23. Шаблоны (часть 3) презентация

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

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

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

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 можно использовать, если удаление очень дорого и оно нам не критично,

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;
};
Использование:
Stack si1; // стек на базе структуры данных по умолчанию (массива)
Stack > si2; // стек на базе списке. Обратите внимание на пробел между знаками >.

int:
const int* find1 ( const int* pool, int n, int x )
{
const int* p = pool;
for ( int i = 0; i {
if ( *p == x ) return p; // success
p++;
}
return 0; // fail
}
Пример использования:
int A[100];
// заполнить A
int* p = find1(A,100,5); // найти 5 в массиве

произвольному условию:
const int* find2 ( const int* pool, int n, bool (*cond)(int) )
{
const int* p = pool;
for ( int i = 0; 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

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

типы делятся на встроенные и определяемые пользователем
Указатель на функцию – это встроенный тип
Класс с оператором вызова функции – определяемый пользователем

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

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

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

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

Пусто. Мы ничего не можем сказать про неизвестный тип. */};

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; }
. . .
};

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