Обобщенное программирование. Введение в STL. Параллелизация вычислений. Лекция 6

1. ООП 2021 Лекция 6 Обобщенное программирование. Введение в STL. Параллелизация вычислений. [email protected]

1

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

ОП - Образец программирования, заключающаяся в таком описании
данных и алгоритмов, которое можно применять к различным типам
данных, не меняя само это описание.
В том или ином виде поддерживается разными языками
программирования. Возможности обобщённого программирования
впервые появились в виде дженериков (обобщённых функций) в 1970-х
годах в языках Клу и Ада, затем в виде параметрического полиморфизма в
ML и его потомках, а затем во многих объектно-ориентированных языках,
таких как C++, Python, Java, Object Pascal, D, Eiffel, языках для платформы
.NET и других.
2

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

Обобщенное программирование это создание кода, работающего с разными
типами, заданными в виде аргументе, причем эти типы должны
соответствовать специфическим синтаксическим и семантическим
требованиям. (Страуструп)
Например, элементы вектора должны иметь тип, который можно копировать
(с помощью копирующего конструктора и оператора присваивания).
Когда мы производим параметризацию класса, мы получаем шаблонный
класс (class template), который часто называют также параметризованным
типом (parameterized type) или параметризованным классом (parameterized
class).
Когда мы производим параметризацию функции, мы получаем шаблонную
функцию (function template), которую часто называют параметризованной
функцией (parameterized function), а иногда алгоритмом (algorithm). По этой
причине обобщенное программирование иногда называют алгоритмически
ориентированным программированием (algorithm-oriented programming); в этом
случае основное внимание при проектировании переносится на алгоритмы, а
не на используемые типы.
3

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

Данную форму обобщенного программирования, основанную на явных
шаблонных параметрах, часто называют параметрическим или
статическим полиморфизмом (parametric polymorphism). В
противоположность ей полиморфизм, возникаюпшй благодаря иерархии
классов и виртуальным функциям, называют динамическим полиморфизмом
(ad hoc polymorphism).
Причина, по которой оба стиля программирования называют
полиморфизмом (polymorphism), заключается в том, что каждый из них дает
программисту возможность создавать много версий одного и того же
понятия с помощью единого интерфейса.
4

5. Существует несколько различий между динамическим и статическим полиморфизмом . Наиболее очевидным является то, что выбор

вызываемой
функции при обобщенном программировании определяется компилятором во
время компиляции, а при динамическом полиморфизме он определяется во
время выполнения программы.
v.push_back(х); // записать х в вектор v
s.draw();
// нарисовать фигуру s
Для вызова v.push back(x) компилятор определит тип элементов в объекте v
и применит соответствующую функцию push_back(), а для вызова s.draw () он
неявно вызовет некую функцию draw () (с помощью таблицы виртуальных
функций).
Это дает динамическому полиморфизму свободу, которой лишено
обобщенное программирование, но в то же время это делает обычное
обобщенное программирование систематическим, понятным и эффективным.
5

6. Для чего же на самом деле используются шаблоны? Для получения непревзойденно гибких и высокопроизводительных программ.

Используйте шаблоны, когда производительность программы играет важную
роль (например, при интенсивных вычислениях в реальном времени).
Используйте шаблоны, когда гибкость сочетания информации, поступающей
от разных типов, играет важную роль (например, при работе с STL).
Шаблоны имеют много полезных свойств, таких как высокая гибкость и почти
оптимальная производительность, но, к сожалению, они не идеальны. Как
всегда, преимуществам сопутствуют недостатки.
Основным недостатком шаблонов является то, что гибкость и высокая
производительность достигаются за счет плохого разделения между
"внутренностью" шаблона (его определением) и его интерфейсом
(объявлением). Это проявляется в плохой диагностике ошибок, особенно
плохими являются сообщения об ошибках. Иногда эти сообщения об ошибках
в процессе компиляции выдаются намного позже, чем следовало бы.
6

7. #define ListNode(Type) \ class ListNode##Type { \ private: \ ListNode##Type* next; \ Type* data; \ public: \

Как было до шаблонов
#define ListNode(Type) \
class ListNode##Type { \
private: \
ListNode##Type* next; \
Type* data; \
public: \
ListNode##Type(Type* d, ListNode* n = NULL) : next(n), data(d) {} \
~ListNode() { delete next; } \
void* Data() { return data; } \
ListNode* Next() { return next; } \
};
7

8. Шаблоны

Шаблон (template) — это класс или функция, параметризованные
набором типов и/или целыми числами.
template<class Т>
class vector {
public:
int size() const;
private:
int sz; T* p;
};
template <class T>
int vector<T>::size() const {
return sz;
}
В списке шаблонных аргументов ключевое слово class означает тип; его
эквивалентной альтернативой является ключевое слово typename.
Функция-член шаблонного класса по умолчанию является шаблонной
функцией с тем же списком шаблонных аргументов, что и у класса.
8

9. Шаблонные аргументы

Аргументы шаблонного класса указываются каждый раз, когда
используется его имя.
vector<int> v1; // OK
vector v2;
// ошибка: пропущен шаблонный аргумент
vector<int,2> v3;
// ошибка: слишком много шаблонных аргументов
vector<2> v4;
// ошибка: ожидается тип шаблонного аргумента
Аргументы шаблонной функции обычно выводятся из ее аргументов.
template< class Т>
T find(vector<T>& v, int i) {
return v[i];
}
vector<int> v1;
vector<double> v2;
int x1 = find (v1, 2) ; // здесь тип T – это int
int x2 = find(v2,2) ; // здесь тип T – это double
9

10. Конкретизация шаблонов

Вариант шаблона для конкретного набора шаблонных аргументов называется
специализацией. Процесс генерации специализаций на основе шаблона и
набора аргументов называется конкретизацией шаблона. Как правило, эту
задачу решает компилятор, но программист также может самостоятельно
определить отдельную специализацию. Обычно это делается, когда общий
шаблон для конкретного набора аргументов неприемлем.
template< class Т> struct Compare { // обобщенное сравнение
bool operator () (const Т& a, const Т& b) const {
return a<b;
}
};
template< > struct Compare < const char*> { // сравнение С-строк
bool operator()(const char* a, const char* b) const {
return strcmp(a,b)==0;
}
};
Compare<int> c2;
// общее сравнение
Compare<const char*> с; // сравнение С-строк
bool b1 = c2(1,2);
// общее сравнение
10
bool b2 = с ("asd", "dfg"); // сравнение С-строк

11. Шаблонные типы членов-классов

Шаблон может иметь как члены, являющиеся типами, так и члены, не
являющиеся типами (как данные-члены и функции-члены). Это значит, что
нельзя сказать, относится ли имя члена к типу или нет. По техническим
причинам, связанным с особенностями языка программирования,
компилятор должен знать это, поэтому мы ему должны каким-то образом
передать эту информацию. Для этого используется ключевое слово
typename.
template< class Т> struct Vec {
typedef Т valuetype; // имя члена класса
static int count;
// член - данное
};
template< class T> void my_func (Vec<T>& v){
int x = Vec<T>::count; // имена членов по умолчанию
// считаются не относящимися к типу
v.count = 7;
// более простой способ сослаться
// на член, не являющийся типом
typename Vec<T>:: valuetype хх = х; // здесь нужно слово typename
}
11

12. Библиотеки классов

-
Стандартная библиотека шаблонов STL
Boost библиотека шаблонов
SGI библиотека шаблонов
Arageli – математическая библиотека
POCO (или C++ Portable Components) – для сетевых приложений
12

13. Пример

Рассмотрим пример наиболее распространенного использования
целочисленного значения в качестве шаблонного аргумента: контейнер,
количество элементов которого известно уже на этапе компиляции.
template<class Т, int N> struct array {
T elem[N]; // хранит элементы в массиве - члене класса
// использует конструкторы по умолчанию, деструктор и присваивание
Т& operator[ ] (int n); // доступ: возвращает ссылку const Т& operator [ ] (int n) const;
T* data() { return elem; } // преобразование в Т* const
T* data() const { return elem; } // преобразование в Т* const
int size() const { return N; }
};
13

14. Мы можем использовать класс array примерно так: array<int,256> gb; // 256 целых чисел const int max = 1024; void some_func (int

Мы можем использовать класс array примерно так:
array<int,256> gb;
// 256 целых чисел
const int max = 1024;
void some_func (int n) {
array<char,max> loc;
array<char,n> oops; // ошибка: значение n компилятору неизвестно
// . . .
array<char,max> loc2 = loc; // создаем резервную копию
Ясно, что класс array очень простой — более простой и менее мощный, чем
класс vector, — так почему иногда следует использовать его, а не класс vector?
Один из ответов: "эффективность". Размер объекта класса array известен на
этапе компиляции, поэтому компилятор может выделить статическую память (для
глобальных объектов, таких как gb) или память в стеке (для локальных объектов,
таких как loc), а не свободную память. Проверяя выход за пределы диапазона,
мы сравниваем константы (например, размер N). Для большинства программ это
повышение эффективности незначительно, но если мы создаем важный
компонент системы, например драйвер сети, то даже небольшая разница
оказывается существенной. Что еще более важно, некоторые программы просто
не могут использовать свободную память. В таких программах массив array
имеет много преимуществ над классом vector без нарушения основного
ограничения (запрета на использование свободной памяти).14

15. Пример

array<double,6> ad = { 0.0, 1.1, 2.2, 3.3, 4.4, 5.5 };
double* р = ad;
// ошибка: нет неявного преобразования в указатель
double* q = ad.data(); // OK: явное преобразование
template<class С> void printout(const C& c) {
for (int i = 0; i<c.size(); ++i) cout << с[i] <<‘\n’;
}
Эту функцию printout () можно вызвать как в классе array, так и в классе vector.
printout(ad); // вызов из класса array
vector<int> vi; // • •
printout(vi); // вызов из класса vector
Это простой пример обобщенного программирования, демонстрирующий доступ
к данным. Он работает благодаря тому, что как для класса array, так и для класса
vector используется один и тот же интерфейс (функции size () и операция
индексирования).
15

16. Вывод шаблонных аргументов

Создавая объект конкретного класса на основе шаблонного класса, мы
указываем шаблонные аргументы.
array<char, 1024> buf; // для массива buf параметр Т - char, а N == 1024
array<double, 10> D2; // для массива D2 параметр Т - double, а N == 10
Для шаблонной функции компилятор обычно выводит шаблонные аргументы
из аргументов функций.
template<class Т, int N> void fill (array<T,N>& b, const T& val) {
for (int i = 0; i<N; ++i) b[i] = val;
}
void f() {
fill(buf, 'x'); // для функции fill() параметр T - char, a N == 1024,
fill( D2, 0.0 ); // для функции fill() параметр Т - double, а N == 10,
// потому что аргументом является объект D2
}
С формальной точки зрения вызов fill (buf, 'х') является сокращенной формой
записи fill<char, 1024 > (buf, 'х'), a fill(b2,0)— сокращение вызова fill<double, 10 >
(D2,0), но, к счастью, мы не всегда обязаны быть такими конкретными.
16
Компилятор сам извлекает эту информацию за нас.

17. Обобщение класса

Пусть есть класс :
class MyVector{
private:
double* m_data;
Int m_size;
public:
void allocate (int a){ m_size=a; m_date = new double[a]; }
void push_back( double x ){ m_data[m_size -1] = x;}
void reserve () ; // …..
// конструкторы, деструкторы и прочие функции
};
Нам нужно этот вектор для типа double обобщить на другие типы.
Мы должны проверить определения имеющихся в классе функций на
возможность их использования с неопределенным типом T.
17
То есть, мы должны предположить, что отношения, связанные
с типом double
станут работать и с произвольным типом T.

18. 1) Как запрограммировать класс MyVector<x>, если тип х не имеет значения по умолчанию? 2) Как гарантировать, что элементы

1) Как запрограммировать класс MyVector<x>, если тип х не имеет
значения по умолчанию?
2) Как гарантировать, что элементы вектора будут уничтожены в конце
работы с ним?
Должны ли мы вообще решать эти проблемы? Мы могли бы заявить: "Не
создавайте векторы для типов, не имеющих значений по умолчанию" или "Не
используйте векторы для типов, деструкторы которых могут вызвать
проблемы". Для конструкции, предназначенной для общего использования,
такие ограничения довольно обременительны и создают впечатление, что
разработчик не осмыслил задачи или не подумал о других людях.
Для того чтобы сделать обобщение MyVector, мы должны устранить две
указанные выше проблемы.
Мы можем работать с типами, не имеющими значений по умолчанию,
предоставив пользователю возможность задавать это значение
самостоятельно:
template <class Т> void MyVector <T>:: resize (int newsize, T def = T() );
Иначе говоря, используйте в качестве значения по умолчанию объект,
созданный конструктором Т(), если пользователь не указал иначе.
(Страуструп)
18

19. Пример

MyVector <double> v;
v.resize(100) ; // добавляем 100 копий объекта double(),
v.resize(200, 0.0); // добавляем 100 копий числа 0.0
v.resize(300, 1.0); // добавляем 100 копий числа 1.0
struct No_default {
No_default(int) ; // единственный конструктор класса No_default
// . . .
};
MyVector <No_default> v2(10); // ошибка: попытка создать 10 No_default()
MyVector <No_default> v3;
v3.resize(100, No_default(2)); // добавляем 100 копий объектов No_default(2)
v3.resize(200);
// ошибка: попытка создать 100 No_default ()
19

20. Проблему, связанную с деструктором, устранить труднее. Это связано с тем, что в структуре данных часть данных может быть

проинициализирована, а часть — нет. До сих пор мы старались избегать
неинициализированных данных и ошибок, которые ими порождаются.
Во-первых, мы должны найти способ для получения неинициализированной
памяти и манипулирования ею. К счастью, стандартная библиотека содержит
класс allocator, распределяющий неинициализированную память. Слегка
упрощенный вариант :
template<class Т> class allocator {
public:
// . . .
Т* allocate(int n); // выделяет память для n объектов типа Т
void deallocate(Т* р, int п); // освобождает память, занятую n
// объектами типа Т, начиная с адреса р
void construct (Т* р, const Т& v);
// создает объект типа Т
// со значением v по адресу р
void destroy(Т* р);
// уничтожает объект Т по адресу р
};
20

21. Класс allocator — то, что нужно для реализации функции MyVector <T>:: reserve (). Начнем с того, что включим в класс vector

Класс allocator — то, что нужно для реализации функции
MyVector <T>:: reserve (). Начнем с того, что включим в класс vector
параметр класса allocator.
template< class Т, class А = allocator<T> > class MyVector {
A alloc; // используем объект класса allocator для работы
// с памятью, выделяемой для элементов
// . . .
}
Кроме распределителя памяти, используемого вместо оператора new,
остальная часть описания класса MyVector может не отличаться от прежнего.
Как пользователи класса MyVector , мы можем игнорировать распределители
памяти, пока сами не захотим, чтобы класс MyVector управлял памятью,
выделенной для его элементов, нестандартным образом. Как разработчики
класса MyVector и как студенты, пытающиеся понять фундаментальные
проблемы и освоить основные технологии программирования, мы должны
понимать, как вектор работает с неинициализированной памятью, и
предоставить пользователям правильно сконструированные объекты.
(Страуструп)
21

22. Единственный код, который следует изменить, — это функции-члены класса MyVector , непосредственно работающие с памятью,

например
функция vector<T>::reserve ().
template< class Т, class А>
void MyVector <T,A>:: reserve (int newalloc) {
if (newalloc<=space) return; // размер не уменьшается
T* p = alloc.allocate (newalloc) ; // выделяем новую память
for (int i=0; i<sz; ++i) alloc.construct(&p[i],elem[i]); // копируем
for (int i=0; i<sz; ++i) alloc.destroy (&elem[i]) ; // уничтожаем
alloc.deallocate (elem, space) ; // освобождаем старую память
elem = p;
space = newalloc;
}
Мы перемещаем элемент в новый участок памяти, создавая копию в
неинициализированной памяти, а затем уничтожая оригинал. Здесь нельзя
использовать присваивание, потому что для таких типов, как string,
присваивание подразумевает, что целевая область памяти уже
проинициализирована. (Страуструп)
22

23. Имея функции reserve(), MyVector<T,A>::push_back(), можно написать следующее: template<class Т, class А> void

Имея функции reserve(), MyVector<T,A>::push_back(), можно написать
следующее:
template<class Т, class А>
void MyVector<T,A>::push_back (const T& val) {
if (space==0) reserve(8);
// начинаем с памяти для 8 элементов
else if (sz==space) reserve(2*space); // выделяем больше памяти
alloc.construct( &elem[sz], val );
// добавляем в конец значение val
++sz;
// увеличиваем размер
}
Аналогично можно написать функцию MyVector<T,А>::resize () :
template<class T, class А>
void MyVector<T,A>: : resize (int newsize, T val = T() ) {
reserve(newsize);
for (int i=sz; i< newsize; ++ i) alloc.construct( & elem[i], val );
// создаем
for (int i = newsize; i<sz; ++i) alloc.destroy( & elem[i] );
// уничтожаем
sz = newsize;
}
Обратите внимание на то, что, поскольку некоторые типы не имеют
конструкторов по умолчанию, мы снова предоставили возможность
задавать
23
начальное значение для новых элементов. (Страуструп)

24. Разумно сочетайте статический и динамический полиморфизм

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

25. Динамический полиморфизм позволяет значению иметь несколько типов посредством открытого наследования. Например, Derived*p можно

рассматривать как указатель не только на Derived, но и на объект любого типа
Base, который прямо или косвенно является базовым для Derived .
Динамический полиморфизм известен также как включающий
полиморфизм, поскольку множество, моделируемое Base, включает
специализации, моделируемые Derived.
Благодаря своим характеристикам динамический полиморфизм в С++
наилучшим образом подходит для решения следующих задач:
- Единообразная работа, основанная на отношении
надмножество/подмножество. Работа с различными классами,
удовлетворяющими отношению надмножество/подмножество
(базовый/производный), может выполняться единообразно.
- Статическая проверка типов. В С++ все типы проверяются статически.
- Динамическое связывание и раздельная компиляция. Код, который
использует иерархию классов, может компилироваться отдельно от этой
иерархии. Это становится возможным благодаря косвенности, обеспечиваемой
указателями (как на объекты, так и на функции).
- Бинарная согласованность. Модули могут компоноваться как статически,
так и динамически, до тех пор, пока схемы виртуальных таблиц подчиняются
одним и тем же правилам.
25

26. Статический полиморфизм посредством шаблонов также позволяет значению иметь несколько типов. Внутри шаблона tempiate< class т>

Статический полиморфизм посредством шаблонов также позволяет
значению иметь несколько типов. Внутри шаблона
tempiate< class т> void f( т t ) { /* ... */ }
t может иметь любой тип, который можно подставить в f для получения
компилируемого кода. Это называется "неявным интерфейсом" в
противоположность явному интерфейсу базового класса. Таким образом
достигается та же цель полиморфизма написание кода, который работает с
разными типами но совершенно иным путем.
Статический полиморфизм наилучшим образом подходит для решения
следующих задач:
- Единообразная работа, основанная на синтаксическом и семантическом
интерфейсе. Работа с типами, которые подчиняются синтаксическому и
семантическому интерфейсу, может выполняться единообразно. Интерфейсы в
данном случае представляют синтаксическую сущность и не основаны на
сигнатурах, так что допустима подстановка любого типа, который удовлетворяет
данному синтаксису. Например, пусть дана инструкция int i = p->f(5) ;. Если р
указатель на класс Base, эта инструкция вызывает определенную функцию
интерфейса, вероятно, virtual int f(int). Но если р имеет обобщенный тип, то этот
вызов может быть связан со множеством различных вещей, включая, например,
вызов перегруженного оператора operator->, который возвращает тип, в котором
определена функция X f (double), где X тип, который может быть преобразован
в int.
- Статическая проверка типов. Все типы проверяются статически.
- Статическое связывание (мешает раздельной компиляции). Все типы
связываются статически.
- Эффективность. Вычисления во время компиляции и статическое
26 недоступных при
связывание позволяют достичь оптимизации и эффективности,
динамическом связывании. (метапрограммирование)

27. Согласно книге - Krzysztof Czarnecki and Ulr;ch W. Eisenecker, Generative Programming - Methods, Tools, and Applications'. Ad('

m-Wesley, Boston, MA, 2000.
(Вандевурд, Д., Джосаттис, Н. М., Грегор, Д. - Шаблоны C++. Справочник
разработчика, 2-е изд, 2018)
- Обобщенное программирование - это поддисциплина информатики,
которая имеет дело с поиском абстрактных представлений эффективных
алгоритмов, структур данных и других понятий программного обеспечения,
вместе с организацией их систематики...
В контексте С++ обобщенное программирование иногда определяется как
программирование с шаблонами (programming with templates), а объектноориентированное программирование рассматривается как программирование с
виртуальными функциями (programming with virtual functions). В этом смысле
почти любое использование шаблонов в С++ можно рассматривать как пример
обобщенного программирования.
27

28. Наиболее значительный вклад в этой области принадлежит стандартной библиотеке шаблонов (Standard Template Library STL), которая

позже была
адаптирована и включена в стандартную библиотеку С++.
STL является каркасом, который предоставляет большое количество
полезных операций, называемых алгоритмами, для ряда линейных структур
данных для хранения коллекции объектов (контейнеров).
И алгоритмы и контейнеры являются шаблонами; однако ключевой момент
состоит в том, что алгоритмы не являются функциями-членами контейнеров.
Они написаны обобщенным способом, так что их можно использовать с любым
контейнером (и линейной коллекцией элементов).
Для обеспечения такого использования проектировщики STL определили
абстрактное понятие итераторов, которые могут быть предоставлены для
любого вида линейной коллекции.
По существу, аспекты функционирования контейнера, специфические для
данной коллекции, оказались переложенными на функциональность итераторов.
Вследствие этого операция наподобие вычисления максимального значения
в последовательности может быть выполнена без знания того, каким образом в
этой последовательности хранятся значения.
28

29. template<typename Iterator> Iterator max_element ( Iterator beg, // Начало коллекции Iterator end) // Конец коллекции { //

template<typename Iterator>
Iterator max_element ( Iterator beg, // Начало коллекции
Iterator end) // Конец коллекции
{
// Используются определенные операции итератора
// для обхода всех элементов коллекции с целью
// поиска элемента с максимальным значением и
// возврата его позиции посредством итератора
}
template<typename Т, ...>
class vector {
public:
using iterator = ... ; // Зависящий от реализации итератор для векторов
iterator begin() ; // Итератор начала коллекции
iterator end() ; // Итератор конца коллекции
};
template<typename Т, ...>
class list {
public:
using iterator = ...; // Зависящий от реализации итератор для списков
iterator begin)) ; // Итератор начала коллекции
iterator end() ; // Итератор конца коллекции
29
};

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

в качестве аргументов (здесь опущен частный случай пустой
коллекции):
30

31. #include<iostream> #include"MyClass.hpp" #include<algorithm> #include<list> #include <vector> template<typename T> void

#include<iostream>
#include"MyClass.hpp"
#include<algorithm>
#include<list>
#include <vector>
template<typename T>
void printMax(T & coll) {
// Вычисление позиции максимального значения
auto pos = std::max_element (coll.begin(), coll.end() );
// Вывод значения максимального элемента coll (если таковой имеется):
if (pos != coll.end() ) {
std::cout << *pos << '\n';
}
else {
std::coat << "empty" << '\n';
}
}
int main() {
std::vector< MyClass> c1;
std::list< MyClass> c2;
printMax(c1);
31
printMax(c2);

32. Параметризируя свои операции в терминах итераторов, STL избегает резкого увеличения количества определений операций. Вместо

того чтобы
реализовать каждую операцию для каждого контейнера, нужно реализовать
алгоритм всего лишь один раз, после чего его можно будет использовать для
каждого контейнера.
Обобщенная связка (generic glue) это итераторы, которые обеспечиваются
контейнерами и используются алгоритмами. Этот метод работоспособен,
поскольку итераторы имеют определенный интерфейс, который обеспечивается
контейнерами и используется алгоритмами. Этот интерфейс обычно называется
концептом, что обозначает набор ограничений, которым должен удовлетворять
шаблон, чтобы вписаться в соответствующую схему.
В принципе, функциональность наподобие STL-подобной может быть
реализована и с использованием динамического полиморфизма. Однако на
практике она имела бы ограниченное применение, поскольку концепция
итераторов слишком "легковесная" по сравнению с механизмом вызова
виртуальной функции. Добавление уровня интерфейса на основе виртуальных
функций, скорее всего, замедлит наши операции на порядок (а то и больше).
Обобщенное программирование практично именно потому, что оно
основано на статическом полиморфизме, который выполняет разрешение
интерфейсов во время компиляции.
32

33. Вариативные шаблоны

Начиная с C++11, параметрам шаблонов можно сопоставлять переменное
количество аргументов шаблона. Это дает возможность использовать шаблоны
в местах, где требуется передать произвольное количество аргументов
произвольных типов. Типичное приложение этой возможности передача
произвольного количества параметров различных типов в класс. Еще одно
применение предоставить обобщенный код для обработки любого количества
параметров произвольных типов.
Параметры шаблона могут быть определены таким образом, чтобы
принимать неограниченное количество аргументов шаблона. Такие шаблоны
называются вариативными (variadic templates).
Например, можно использовать приведенный ниже код для вызова функции
print () для переменного количества аргументов разных типов:
33

34. #include <iostream> void print() { } template< typename T, typename... Types> void print( T firstArg, Types... args) {

#include <iostream>
void print() { }
template< typename T, typename... Types>
void print( T firstArg, Types... args) {
std::cout << firstArg << '\n'; // Печать первого аргумента
print(args...);
// Вызов print для остальных аргументов
}
Если передаются один или несколько аргументов, используется шаблон
функции, который, указывая отдельно первый аргумент, позволяет выводить в
консоль первый аргумент, перед тем как рекурсивно применить print () для
остальных аргументов. Остальные аргументы, представленные именем args,
являются пакетом параметров функции (function parameter pack):
void print (T firstArg, Types... args)
Types указывается в пакете параметров шаблона (template parameter pack):
template< typename T, typename... Types>
Для завершения рекурсии предоставляется нешаблонная перегрузка print (),
которая вызывается при пустом пакете параметров. Например, вызов
std::string s("world");
print(7.5, "hello", s);
приведет к следующему выводу в консоль:
7.5
Hello
world
34

35. Первый вызов расширяется до print<double, char const*, std::string> (7.5, "hello", s); где • firstArg имеет значение 7.5, так

Первый вызов расширяется до
print<double, char const*, std::string> (7.5, "hello", s);
где
• firstArg имеет значение 7.5, так что тип Т представляет собой double, а
• args является вариативным аргументом шаблона, который содержит
значения "hello" типа char const* и "world" типа std: : string.
После вывода 7.5 в качестве firstArg вновь вызывается print () для
оставшихся аргументов. Этот вызов расширяется до
print<char const*, std::string> ("hello", s);
где
• firstArg имеет значение "hello", так что тип Т представляет собой char
const*, а
• args является вариативным аргументом шаблона, который содержит
значение типа std:: string.
После вывода в консоль "hello" в качестве firstArg вновь вызывается
print () для оставшихся аргументов. Этот вызов расширяется до
print<std::string> (s);
где
• firstArg имеет значение "world", так что тип Т представляет собой
std: : string, а
• args является пустым вариативным аргументом шаблона, который не
содержит значений.
Таким образом, после вывода в консоль "world" в качестве firstArg вновь
35нешаблонной
вызывается print () — без аргументов, что приводит к вызову
перегрузки print (), не выполняющей никаких действий.

36. Можно и по другому. #include <iostream> template< typename T> void print(T arg) { std::cout << arg << '\n'; // Вывод

Можно и по другому.
#include <iostream>
template< typename T>
void print(T arg)
{
std::cout << arg << '\n'; // Вывод переданного аргумента
}
templateCtypename T, typename... Types>
void print(T firstArg, Types... args)
{
print(firstArg); // Вызов print() для первого аргумента
print(args...); // Вызов print() для прочих аргументов
}
Если два шаблона функций отличаются только завершающим пакетом
параметров, шаблон функции без такого пакета является предпочтительным.
36

37. Параллелизация вычислений

37

38. #include <windows.h> #include <ppl.h> #include <iostream> #include <random> using namespace concurrency; using namespace std;

Пример
#include <windows.h>
#include <ppl.h>
#include <iostream>
#include <random>
using namespace concurrency;
using namespace std;
// Вызывает предоставленную рабочую функцию
// и возвращает количество миллисекунд, которое затрачивает эта функция
template <class Function>
__int64 time_call( Function&& f) {
__int64 begin = GetTickCount();
f();
return GetTickCount() - begin;
}
38

39. // Создает квадратную матрицу с заданным количеством строк и столбцов. double** create_matrix(size_t size){ double** m = new

double*[size];
for (size_t i = 0; i < size; ++i)
{
m[i] = new double[size];
}
return m;
}
// Освобождает память, выделенную для данной квадратной матрицы.
void destroy_matrix ( double** m, size_t size)
{
for (size_t i = 0; i < size; ++i)
{
delete[ ] m[i];
}
delete m;
}
39

40. // Инициализирует заданную квадратную матрицу со значениями, // которые генерируются данной заданной функцией генератора.

template <class Generator>
double** initialize_matrix(double** m, size_t size, Generator& gen)
{
for (size_t i = 0; i < size; ++i)
{
for (size_t j = 0; j < size; ++j)
{
m[i][j] = static_cast<double>(gen());
}
}
return m;
}
40

41. // Вычисляет произведение двух квадратных матриц. void matrix_multiply ( double** m1, double** m2, double** result, size_t

size)
{
for (size_t i = 0; i < size; i++)
{
for (size_t j = 0; j < size; j++)
{
double temp = 0;
for (int k = 0; k < size; k++)
{
temp += m1[i][k] * m2[k][j];
}
result[i][j] = temp;
}
}
}
41

42. template <typename _Index_type, typename _Function> void parallel_for(_Index_type _First, _Index_type _Last, const _Function&

template <typename _Index_type, typename _Function>
void parallel_for(_Index_type _First, _Index_type _Last, const _Function& _Func,
const auto_partitioner& _Part = auto_partitioner()) {
parallel_for(_First, _Last, _Index_type(1), _Func, _Part);
}
// Вычисляет произведение двух квадратных матриц параллельно.
void parallel_matrix_multiply ( double** m1, double** m2, double** result, size_t size)
{
parallel_for (size_t(0), size,
[&](size_t i) {
for (size_t j = 0; j < size; j++)
{
double temp = 0;
for (int k = 0; k < size; k++)
{
temp += m1[i][k] * m2[k][j];
}
result[i][j] = temp;
}
}
42
);
}

43. int main() { const size_t size = 1000; // Создает генератор случайных чисел. mt19937 gen (42); // Создает и инициализирует

входные и результирующую матрицы
double** m1 = initialize_matrix (create_matrix(size), size, gen);
double** m2 = initialize_matrix (create_matrix(size), size, gen);
double** result = create_matrix (size);
// печатает на консоли время, затраченное на многократное умножение матриц.
wcout << L"serial: " << time_call (
[&] { matrix_multiply (m1, m2, result, size); } // это лямбда-выражение (3-4 сем.)
) << endl;
43

44. // печатает время многократного параллельного умножение матриц wcout << L"parallel: " << time_call ( [&] {

// печатает время многократного параллельного умножение матриц
wcout << L"parallel: " << time_call (
[&] { parallel_matrix_multiply (m1, m2, result, size ); }
) << endl;
// Освобождается память, выделенная для матриц.
destroy_matrix(m1, size);
destroy_matrix(m2, size);
destroy_matrix(result, size);
}
44

45. Домашнее задание на неделю

Проект 30.
Создать абстрактный базовый класс именем своей фамилии,
записанной латиницей.
Создать 2 производных друг от друга класса (а первый – от базового)
с именами измененного имени базового класса с суффиксами типа
«_1» и «_2». Распределить их по соответствующим файловым
модулям: описания класса – в хидере, определение – в с++.
Наполнить каждый класс по одному автоматическому и динамическому
члену-данных любого типа.
Создать также отдельно от иерархии класс базы данных DB, в котором
разместить член-данных типа vector<Ivanov*>.
Написать функцию create, внутри которой создать по два объекта каждого
типа, и положить их в объект типа DB, который передавать в функцию
параметром.
В функции main создать объект DB db1. Вызвать функцию create.
Затем реализовать следующий код:
DB db2=db1;
db1=db2;
45
Проконтролировать память.

46. Контрольная работа 6

Пусть имеются два класса Base (свое имя) и Derived (своя фамилия),
связанных полиморфно – их создавать не надо, нужно будет только
использовать. Эти классы уже наполнены всем необходимым.
Пусть также имеется другая полиморфная иерархия из классов – One, Two и
Three, наследуемых друг от друга.
Внутри класса One помещается член-данных типа vector <Base*> , а в
классе Three – член-данных типа vector <Base*> *.
Все остальное в этих классах есть, кроме копирующих конструкторов.
Задача:
Реализовать копирующие конструкторы для классов One, Two и Three.
46