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

Что такое обобщенное программирование? Парадигма программирования, заключающаяся в написании алгоритмов, которые можно применять к различным типам данных

Предпосылки использования Различные типы данных часто требуется обрабатывать при помощи одних и тех же алгоритмов Сортировка и поиск Контейнеры для произвольного типа элементов Программирование на основе стратегий

Шаблоны функций

Пример Требуется разработать семейство функций maximum(a, b), возвращающую значение наибольшего из аргументов a и b Аргументы a и b могут иметь произвольный тип int unsigned int double float

Простейший способ решения – перегрузка функций int maximum(int a, int b) { return (a > b) ? a : b; } unsigned int maximum(unsigned int a, unsigned int b) { return (a > b) ? a : b; } float maximum(float a, float b) { return (a > b) ? a : b; } double maximum(double a, double b) { return (a > b) ? a : b; }

Недостатки Тело функции приходится писать несколько раз Усложнение процесса внесения изменений в реализацию функций Ситуация усложняется, если различные экземпляры одной и той же функции разнесены по различным файлам или модулям

Решение – использование шаблонов функций Язык C++ имеет языковые средства, позволяющие определить функцию-шаблон, работающую с некоторыми абстрактными типами данных Термин «абстрактный» в данном случае не связан с наследованием, а обозначает некоторый тип данных Шаблон задает поведение целого семейства функций и может быть в дальнейшем использован с некоторыми конкретными типами данных Шаблонные функции широко используются для реализации алгоритмов в библиотеке STL

Ограничения Реализация (исходный код) шаблонной функции должна быть доступна из всех единиц компиляции, где она используется

Пример // объявляем шаблонную функцию maximum, принимающую // аргументы некоторого типа T template <class T> T maximum(T a, T b) { return (a > b) ? a : b; } int main() { int max1 = maximum(3, 5); float max2 = maximum(-3.7f, 0.35f) double max3 = maximum(1.2, 7.4); std::string max4 = maximum(std::string(“hello"), std::string(“world")); return 0; }

Шаблонные операторы

Шаблонные операторы Оператор – частный случай функции, и он также может быть шаблонным Пример – разработать для класса «Счетчик» шаблонные операторы << и >> для работы с классами стандартных потоков STL

Класс «счетчик» class CCounter { public: explicit CCounter(unsigned maxValue, counter = 0) :m_maxValue(maxValue), m_counter(counter){} unsigned GetValue()const{return m_counter;} unsigned GetMaxValue()const{return m_maxValue;} CCounter& operator++() { ++m_counter; if (m_counter >= m_maxValue) { m_counter = 0; } return *this; } CCounter const operator++(int) // постфиксная форма инкремента { // создаем копию, выполняем предынкремент и возвращаем копию CCounter tmpCopy(*this); ++*this; return tmpCopy; } private: unsigned m_maxValue, m_counter; }; Конструктор может быть помечен как явный при помощи ключевого слова explicit , чтобы запретить возможность его неявного вызова в ситуациях, вроде следующих: CCounter counter(20, 5); counter = 10; эквивалентно: CCounter counter(20, 5); counter = CCounter(10, 0);

Перегрузка оператора вывода в поток для класса «Счетчик» // выводим информацию о счетчике в виде [counter/maxValue] // в произвольный поток вывода template <class T> std::basic_ostream<T>& operator<<( std::basic_ostream<T>& stream, CCounter const& counter) { stream << "[" << counter.GetValue() << "/« << counter.GetMaxValue() << "]"; return stream; }

Перегрузка оператора чтения из потока для класса «Счетчик» template <class T> std::basic_istream<T>& operator>>( std::basic_istream<T>& stream, CCounter & counter) { std::streamoff pos = stream.tellg(); unsigned maxValue = 0; unsigned currentValue = 0; if ( (stream.get() == '[') && (stream >> currentValue) && (stream.get() == '/') && (stream >> maxValue) && (stream.get() == ']') ) { counter = CCounter(maxValue, currentValue); return stream; } stream.seekg(pos); stream.setstate(std::ios_base::failbit | stream.rdstate()); return stream; }

Пример использования перегруженных операций ввода-вывода #include <iostream> #include “Counter.h” int main(int argc, char* argv[]) { CCounter c(10); // считывает данные о счетчике из стандартного ввода в формате: // [counter/maxValue] std::cin >> c; // выводит данные о счетчике в стандартный вывод в формате: // [counter/maxValue] std::cout << c; return 0; }

Шаблоны классов

Шаблоны классов Подобно шаблонам функций программисту может понадобиться иметь шаблоны классов Они задают способы построения отдельных классов, подобно тому, как класс задает способ построения отдельных объектов Шаблонные классы широко используются в библиотеках STL и BOOST, например, для реализации контейнеров и умных указателей Исходный код методов шаблонного класса также должен быть доступен из всех единиц компиляции, где он используется

Пример – простейший шаблон массивов произвольной длины template <class T> class CArray { public: CArray(){...} virtual ~CArray(){...} unsigned GetLength()const{...} void Push(T const& item){...} T& operator[](unsigned index){...} T const& operator[](unsigned index)const{...} void Resize(unsigned newSize){...} CArray(CArray const&){...} CArray operator=(CArray const&){...} private: T * m_pItems; unsigned m_size; };

Продолжение int main() { CArray<int> intArray; intArray.Push(3); intArray.Push(4); intArray[0] = 2; intArray.Resize(1); CArray<std::string> stringArray; stringArray.Push("Hello"); stringArray.Push("World"); stringArray[0] = ("Goodbye"); return 0; }

Параметры шаблонов, не являющиеся типами

Допустимые параметры шаблона, не являющиеся типами В качестве параметров шаблонов могут выступать не только типы данных, но и: Объекты интегрального или перечислимого типа Целые типы Перечислимые типы Тип bool Указатели на объект или указатель на функцию Ссылки на объект или ссылка на функцию Указатели на методы класса

Пример: класс массивов фиксированной длины template <typename T, size_t SIZE> class CSimpleArray { public: CSimpleArray(T const& value = T()) { for (size_t i = 0; i < SIZE; ++i) { m_items[i] = value; } } size_t GetSize()const{return SIZE;} T& operator[](size_t index) { if (index >= SIZE) throw std::range_error("Index is out of range"); return m_items[index]; } T const& operator[](size_t index)const { if (index >= SIZE) throw std::range_error("Index is out of range"); return m_items[index]; } private: T m_items[SIZE]; }; int main(int argc, char * argv[]) { CSimpleArray<std::string, 10> stringArray; try { stringArray[0] = "Hello"; // throws an exception stringArray[10] = "World"; } catch (std::range_error const& e) { std::cout << e.what(); } return 0; }

Примечания Разработанный класс CSimpleArray при всей своей простоте обладает рядом преимуществ перед обычным массивом При доступе к элементам массива осуществляется проверка индексов Наличие оператора присваивания и конструктора копирования Элементы массива всегда инициализированы значением конструктора по умолчанию для типа T Для встроенных типов происходит инициализация нулем

Специализация шаблонов

Специализация шаблона Наряду с общим шаблоном бывает необходима некоторая специализированная версия этого же шаблона При специализации на основе исходного первичного шаблона реализуется его специализированная версия для некоторых конкретных параметров Типы специализации Полная Конкретизированы все параметры первичного шаблона Частичная Конкретизирована только часть параметров

Пример – функция maximum // первичный шаблон функции нахождения максимума template <class T> T maximum(T a, T b) { return (a > b) ? a : b; } // специализация шаблонной функции maximum типом const char* template <> const char* maximum<const char*>(const char * s1, const char *s2) { return (strcmp(s1, s2) > 0) ? s1 : s2; } int main(int argc, char * argv[]) { std::cout << maximum(2, 3) << "\n"; // Output: 3 std::cout << maximum("world", "hello") << "\n"; // Output: world return 0; }

Совместное использование шаблонных классов и функций

Задача Разработать функцию, выполняющую пузырьковую сортировку шаблонных массивов CArray<T> Требования Произвольные критерии сравнения элементов массива Возможность выполнения сортировки по возрастанию и убыванию Возможность упорядочивания объектов по различным параметрам

Класс Comparator, задающий критерий сравнения элементов template <class T> class CComparator { public: bool LessThan(T const& a, T const& b)const { return a < b; } }; // специализация класс CComparator для сравнения указателей на char template <> class CComparator<const char *> { public: bool LessThan(const char * const& a, const char * const& b)const { return strcmp(a, b) < 0; } };

Передача операций как параметров функций Операцию сравнения (объект типа CComparator) будем передавать в качестве параметра в шаблонную функцию Sort Это даст возможность использования различных критериев сравнения элементов одного и того же массива Например, сортировать объекты по различным свойствам или менять порядок сортировки на противоположный

Функция Sort template <class T, class Comp> void sort(CArray<T> & arr, Comp const& comp) { unsigned n = arr.GetLength(); for (unsigned i = 0; i < n - 1; i++) { for (unsigned j = n - 1; i < j; j--) { if (comp.LessThan(arr[j], arr[j-1])) { T temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } }

Пример использования template <class T> class CComparator2 { public: bool LessThan(T const& a, T const& b) const { return a > b; } }; int main() { CArray<double> doubleArray; doubleArray.Push(3.8); doubleArray.Push(5.1); // сортируем массив по убыванию элементов sort(doubleArray, CComparator2<double>()); assert(doubleArray[0] == 5.1); assert(doubleArray[1] == 3.8); return 0; }

Шаблонные методы класса

Шаблонные методы класса В любом классе (в том числе и шаблонном) можно объявить метод-шаблон Пример: В классе CSimpleArray можно реализовать шаблонный оператор присваивания, позволяющий присваивать массивы разных типов и длины

Исходный код: template <typename T, size_t SIZE> class CSimpleArray { public: ... template <class T1, size_t SIZE1> CSimpleArray<T, SIZE> & operator=(const CSimpleArray<T1, SIZE1> & other) { if ((void*)this != (void*)&other) // защита от самоприсваивания { size_t const minSize = (SIZE < SIZE1) ? SIZE : SIZE1; for (size_t i = 0; i < minSize; ++i) { m_items[i] = static_cast<T const&>(other[i]); } // заполняем остаток массива (при его наличии) значениями по умолчанию for (size_t i = SIZE1; i < SIZE; ++i) { m_items[i] = T(); } } return *this; } ... } int main(int argc, char * argv[]) { CSimpleArray<double, 8> doubleArray; CSimpleArray<int, 5> intArray(7); doubleArray = intArray; return 0; }

Шаблоны и наследование

Использование шаблонов при наследовании Ограничений на использование шаблонов при наследовании нет: Шаблон унаследован от простого класса Простой класс унаследован от шаблона Шаблон унаследован от шаблона С помощью шаблонов можно создавать полные или частичные реализации некоторых интерфейсов В этом случае шаблонный параметр выступает в качестве родительского класса Сам шаблонный класс при этом используется как основа для создания конкретных классов

Наследование шаблона от простого класса Данный тип наследования позволяет решить проблему «разбухания» кода при инстанцировании шаблонов В этом случае в базовый класс выносится «тяжелая» реализация, которой «облегченный» таким образом шаблонный класс делегирует выполнение своих методов

Пример – стек указателей Указатели на разные типы данных хранятся в памяти одинаковым образом Исключение – указатели на члены класса Для каждого типа указателей, используемого в программе будет создана (инстанциирована) своя версия класса CStack Разбухание двоичного кода Решение проблемы – специализация шаблонов и наследование от полной специализации класса CStack для указателей типа void*

Иерархия классов

Исходный код // первичный шаблон template <typename T> class CStack { public: void Push(T const& t) {…} T GetTop()const{…} void Pop(){…} bool IsEmpty(){…} private: … }; // полная специализация шаблона // для указателей на void template <> class CStack<void*> { public: void Push(void * p){…} void * GetTop()const{…} void Pop(){} bool IsEmpty()const{} }; // частичная специализация шаблона для // произвольных указателей template <typename T> class CStack<T*> : private CStack<void*> { private: typedef CStack<void*> CBase; public: void Push(T * p) { CBase::Push(p); } T * GetTop()const { return static_cast<T*>(CBase::GetTop()); } void Pop() { CBase::Pop(); } bool IsEmpty()const { return CBase::IsEmpty(); } };

Наследование простых классов от шаблонов Задача – подсчет количества существующих экземпляров объектов некоторых классов Решение: Создать базовый шаблонный класс, конструкторы (по умолчанию и копирования) и деструктор которого осуществляют инкремент/декремент счетчика В качестве параметра шаблона будет выступать класс, для которого необходимо вести подсчет экземпляров Классы, для которых необходимо вести учет количества экземпляров публично наследуются от класса-счетчика

Иерархия классов

Исходный код template <class T> class CCountable { public: static size_t GetInstanceCount() { return m_counter; } protected: CCountable() { ++m_counter; } CCountable(CCountable const& other) { ++m_counter; } ~CCountable() { --m_counter; } private: static size_t m_counter; }; template<class T> size_t CCountable<T>::m_counter = 0; class CSomeClass : public CCountable<CSomeClass> { public: }; int main(int argc, char* argv[]) { CSomeClass someObject; std::cout << CSomeClass::GetInstanceCount() << "\n"; { CSomeClass someOtherObject; std::cout << CSomeClass::GetInstanceCount() << "\n"; } std::cout << CSomeClass::GetInstanceCount() << "\n"; return 0; } Output: 1 2 1

Пример 2 - иерархия фигур Свойства: Цвет Площадь

Реализация без шаблонов class Color {…}; class IShape { public: virtual Color GetColor()const=0 virtual void SetColor(Color const& c)=0; virtual double GetArea()const=0; }; class CCircle : public ICircle { public: … virtual Color GetColor()const { return m_color; } virtual Color SetColor(Color const& c) { m_color = c; } virtual GetArea()const { return PI * m_radius * m_radius; } private: Color m_color; double m_radius; }; class IRectangle : public IShape { … }; class ICircle : public IShape { … }; class CRectangle: public IRectangle { public: … virtual Color GetColor()const { return m_color; } virtual Color SetColor(Color const& c) { m_color = c; } virtual GetArea()const { return m_width * m_height; } private: Color m_color; double m_width, m_height; };

Устраняем дублирование кода Создаем абстрактный шаблонный класс CShapeImpl, реализующий виртуальные функции для установки и получения цвета В качестве параметра шаблона будет выступать базовый класс: template <class Base> class CShapeImpl : public Base {…}; Класс является абстрактным, т.к. класс не реализует метод вычисления площади Класс CCircle и CRectangle наследуются от CShapeImpl В качестве шаблонного параметра выступают интерфейсы IСircle и IRectangle соответственно: class CCircle : public CShapeImpl<ICircle> {…};

Обновленная иерархия

Обновленная реализация class Color {…}; class IShape { public: virtual Color GetColor()const=0 virtual void SetColor(Color const& c)=0; virtual double GetArea()const=0; }; template <class Base> class CShapeImpl : public Base { public: … virtual Color GetColor()const { return m_color; } virtual Color SetColor(Color const& c) { m_color = c; } private: Color m_color; }; class IRectangle : public IShape { … }; class ICircle : public Ishape { … }; class CRectangle: public CShapeImpl<IRectangle> { public: virtual GetArea()const { return m_width * m_height; } private: double m_width, m_height; }; class CCircle: public CShapeImpl<ICircle> { public: virtual GetArea()const { return PI * m_radius * m_radius; } private: double m_radius; };

Преимущества использования шаблонов Повторное использование кода Меньше ручной работы Обобщенные контейнеры и алгоритмы Умные указатели Возможность использования шаблонных реализаций интерфейсов при построении иерархий наследования

Недостатки использования шаблонов Раздувание бинарного кода При использовании шаблонных функций и классов компилятор генерирует код на этапе компиляции для всех использованных с данным шаблоном типов данных Увеличение времени компиляции Не все распространенные компиляторы поддерживают шаблоны в полной мере Код, содержащий шаблоны сложнее анализировать Сложность анализа сообщений компилятора об ошибках компиляции