Обобщенные классы: синтаксис определения, примеры объявления и конкретизации

Шаблон класса (или параметризованный класс) по аналогии с шаблоном функции позволяет автоматизировать генерацию семейства схожих с точностью до используемых типов данных классов. Для определения шаблона классов используется синтаксис:

template <class тип_данных> class имя_класса {... };

template <typename тип_данных> class имя_класса {... };

Определим шаблон класса, описывающего поведение одномерного массива целых чисел:

template <typename T>

class array

{

unsigned int count;

T* mas;

public:

array(unsigned int n)

{ count=n;

mas=new T[n];

}

T maxEl()

{

T maxVal=mas[0];

for(int i=1;i<count;i++)

if(mas[i]>maxVal) maxVal=mas[i];

return maxVal;

}

void initMas(){…}

void sortMas(){…}

};

Из определения шаблона видно, что он параметризуется типом(-ами) для конкретизации определения класса. Тип данных, который необходимо использовать в реализации шаблона, становится обязательной частью объявления нового объекта:

array<int> iArr(6);

iArr.initMas();

cout<<iArr.maxEl();

Создавая экземпляр класса типа array<int>, компилятор предварительно создаст новое определение класса, в котором заменит всякое вхождение параметра шаблона T на его уточнение – тип int. Таким образом выстраивается цепочка – шаблон задает правила построения и формат конкретных классов, а класс служит образцом для создания объектов.

Если встретится определение класса типа array<double>, то это приведет к тому, что в программе будут объявлены уже два класса с набором компонентных данных и методов, заданных в шаблоне array – один с типом int, другой с double. Вообще-то процесс автоматического создания компилятором все новых и новых объявлений классов при использовании шаблонов с разными типами данных может привести к проблеме, называемой разбухание кода – действительно, для каждой конкретизации шаблона будут создаваться свои экземпляры методов и это может привести к большим накладным расходам памяти.

32. Библиотека STL С++: состав, типы контейнеров и итераторов. Примеры использования контейнеров

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

Библиотека STL языка С++.

Библиотека STL содержит компоненты шести основных видов: контейнеры, обобщенные алгоритмы и итераторы, функциональные объекты, адаптеры и аллокаторы [2].

Контейнеры (containers) – это объекты, предназначенные для хранения других элементов. Например, вектор, линейный список, множество.

Контейнеры различаются на контейнеры последовательностей и отсортированные ассоциативные контейнеры.

Контейнеры последовательности организованы в строго линейный набор элементов некоторого типа T. К подобным контейнерам относят:

- динамический массив vector<T>. Этот контейнер обеспечивает произвольный доступ к последовательности произвольной длины с константным временем вставки и удаления элементов в конец последовательности. Для работы с этим контейнером подключатся библиотека vector:

#include <vector>

- очередь deque<T>. Обеспечивает произвольный доступ к последовательности произвольной длины с константным временем вставки и удаления элементов с обеих концов последовательности. Заголовочный файл queue.

- линейный список list<T>. Обеспечивает линейное время доступа к элементам последовательности с константным временем вставки и удаления элемента в любое место последовательности. Заголовочный файл list.

Необходимо также отметить, что обычный массив С++ можно рассматривать как последовательной контейнер, поскольку итераторы и алгоритмы библиотеки могут работать так же, как с уже перечисленными контейнерами.

Отсортированные ассоциативные контейнеры позволяют осуществлять быстрый доступ к элементам коллекции по значению ключа. К контейнерам этого типа относят:

- множество set<Key>. Контейнер поддерживает уникальные ключи и позволяет получить быстрый доступ к ключу. Заголовочный файл set.

- множество с неуникальными ключами multiset<Key>. Контейнер поддерживает дублированные ключи для каждого элемента и позволяет получить быстрый доступ к ключу. Заголовочный файл multiset.

- ассоциативный список map<Key, T>. Контейнер поддерживает уникальные ключи для каждого элемента и позволяет получить быстрый доступ к элементу по ключу. Заголовочный файл map.

- ассоциативный список c неуникальными ключами multimap<Key, T>. Контейнер поддерживает неуникальные ключи для каждого элемента и позволяет получить быстрый доступ к элементу по ключу. Заголовочный файл multimap.

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

Обобщенные алгоритмы (algorithms) выполняют операции над содержимым контейнера. Алгоритмы предоставляют независимый от типа контейнера функционал для решения стандартных задач обработки данных: инициализации, сортировки, поиска, замены, объединения. Алгоритмы делятся на:

- неизменяющие алгоритмы над последовательностями, которые не модифицируют содержимое контейнеров. Подобными алгоритмами являются, например, алгоритм поиска элемента find, подсчета количества элементов в последовательности count, алгоритм перебора всех элементов контейнера for_each.

- изменяющие алгоритмы над последовательностями, модифицирующие содержимое контейнеров. К алгоритмам этого типа относятся: алгоритма копирования элементов из одного диапазона в другой copy и copy_backward, удаления элементов remove, сдвига содержимого диапазона rotate, обращения порядка следования элементов reverse и др.

- алгоритмы, связанные с сортировкой, название которых само говорит о принципе их функциональной общности: они обеспечивают алгоритмы сортировки (sort, stable_sort, partial_sort), слияния (merge), бинарного поиска (binary_search, lower_bound, upper_bound) и операции над множествами (includes, set_union, set_differences), требующие упорядоченности обрабатываемых данных.

- обобщенные числовые алгоритмы, подсчитывающие некоторые частные алгебраические значения на основе значений контейнеров (accumulate, partial_sum, adjasent_difference, inner_product).

В своей работе обобщенные алгоритмы зачастую опираются на итераторы, которые служат ограничителями диапазона обрабатываемых данных в контейнерах, указывают на место вставки или удаления элемента и т.п.

Итераторы (iterators) – это объекты, которые позволяют применить по отношению к разнотипным контейнерам концепцию указателей С++. Они позволяют получить доступ к содержимому контейнера примерно так же, как указатели используются для доступа к элементам массива. Итераторы играют роль посредников между контейнерами и обобщенными алгоритмами.

По аналогии с указателями, контейнер можно привязать к определенной позиции контейнера (к начальной, к конечной, к элементу с заданными характеристиками и т.п.). Итераторы поддерживают разыменование (операция *), инкремент, декремент. Типом итератора объявляется тип iterator, который определен в различных контейнерах.

STL поддерживает пять типов итераторов:

1. Входные итераторы (input_iterator) поддерживают операции равенства, разыменования и инкремента.

==,!=, *it, ++it, it++, *it++

Перечисленные свойства итератора гарантируют возможность чтения данных с его помощью, но не дают возможность изменять значения связанных с итератором значений.

Специальным случаем итератора ввода является istream_iterator.

2. Выходные итераторы (output_iterator) поддерживают операции разыменования, допустимые только с левой стороны присваивания, и инкремента.

++it, it++, *it=t, *it++=t

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

Специальным случаем итератора вывода является ostream_iterator.

3. Однонаправленные итераторы (forward_iterator) поддерживают все операции итераторов ввода/вывода и, кроме того, позволяют без ограничения применять присваивание.

==,!=, =, *it, ++it, it++, *it++

Однонаправленные итераторы позволяют перемещаться по коллекции лишь в одном направлении.

4. Двунаправленные итераторы (biderectional_iterator) обладают всеми свойствами forward-итераторов, а также имеют дополнительную операцию декремента (--it, it--, *it--), что позволяет им проходить контейнер в обоих направлениях.

5. Итераторы произвольного доступа (random_access_iterator) обладают всеми свойствами двунаправленных итераторов, а также поддерживают операции сравнения и адресной арифметики, то есть непосредственный доступ по индексу.

it+=n, it+n, *(it+n), it-=n, it-n, it1-it2, it1<it2, it1<=it2, it1>it2, it1>=it2

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

В STL также поддерживаются обратные итераторы (reverse iterators). Обратными итераторами могут быть либо двунаправленные итераторы, либо итераторы произвольного доступа, но проходящие последовательность в обратном направлении.

Функциональные объекты библиотеки STL предоставляют собой определенные в виде классов сущности, которые могут быть применены для получения некоторого значения либо для изменения состояния вычисления. Функциональный объект определяется как экземпляр класса, для которого перегружена операция operator(), что позволяет использовать синтаксис вызова функции для объекта:

class isEven //класс для поиска четных чисел

{

public:

bool operator()(int n)

{

return n%2==0;

}

};

int main()

{

vector<int> x(5), y(5);

vector <int>::iterator stop, it;

for(i=0;i<5;i++)

x[i]=i;

isEven ie;

//удаляем все четные элементы вектора

stop=remove_if(x.begin(), x.end(), ie);

//просматриваем оставшиеся элементы вектора

it=x.begin();

for(;it!=stop;it++)

cout<<*it;

}

33. Обобщенные алгоритмы библиотеки STL С++: классификация алгоритмов, примеры использования.

Обобщенные алгоритмы (algorithms) выполняют операции над содержимым контейнера. Алгоритмы предоставляют независимый от типа контейнера функционал для решения стандартных задач обработки данных: инициализации, сортировки, поиска, замены, объединения. Алгоритмы делятся на:

- неизменяющие алгоритмы над последовательностями, которые не модифицируют содержимое контейнеров. Подобными алгоритмами являются, например, алгоритм поиска элемента find, подсчета количества элементов в последовательности count, алгоритм перебора всех элементов контейнера for_each.

- изменяющие алгоритмы над последовательностями, модифицирующие содержимое контейнеров. К алгоритмам этого типа относятся: алгоритма копирования элементов из одного диапазона в другой copy и copy_backward, удаления элементов remove, сдвига содержимого диапазона rotate, обращения порядка следования элементов reverse и др.

- алгоритмы, связанные с сортировкой, название которых само говорит о принципе их функциональной общности: они обеспечивают алгоритмы сортировки (sort, stable_sort, partial_sort), слияния (merge), бинарного поиска (binary_search, lower_bound, upper_bound) и операции над множествами (includes, set_union, set_differences), требующие упорядоченности обрабатываемых данных.

- обобщенные числовые алгоритмы, подсчитывающие некоторые частные алгебраические значения на основе значений контейнеров (accumulate, partial_sum, adjasent_difference, inner_product).

В своей работе обобщенные алгоритмы зачастую опираются на итераторы, которые служат ограничителями диапазона обрабатываемых данных в контейнерах, указывают на место вставки или удаления элемента и т.п.

Применение обобщенных алгоритмов к содержимому контейнеров STL: меняем порядок следования элементов списка на обратный алгоритмом reverse и удаляли дублирующиеся элементы алгоритмом unique.

Контейнер-список на основе объектов класса book

list <book> lb;

list <book>::iterator lit,lit1;

lb.insert(lb.begin(),book("Марк Твен","Приключения Тома Сойера",300));

lb.insert(lb.begin(),book("Гоголь","Мертвые души",200));

lb.insert(lb.begin(),book("Тургенев","Отцы и дети",500));

lb.insert(lb.begin(),book("Гоголь","Мертвые души",200));

lb.insert(lb.begin(),book("Гоголь","Мертвые души",300));

lit=lb.begin();

//Меняем порядок следования элементов списка на обратный

reverse(lb.begin(),lb.end());

lb.sort(); //сортируем список

//Удаляем дублирующиеся записи (обобщенный алгоритм)

lit1=unique(lb.begin(),lb.end());

lit=lb.begin();

//Просматривем список

for(;lit!=lit1;lit++)

cout<<(*lit); //обращение lit[i] недопустимо

Массив целых чисел можно отсортировать с использованием обобщенного алгоритма sort:

const int N=1000;

int arr[N];

generate(&a[0], &a[N], rand);

sort(&a[0], &a[N]);

Дополнительно пример демонстрирует использование обобщенного алгоритма generate, который для заданного диапазона генерирует значения элементов, используя заданный функциональный объект (в приведенном примере – функцию генерации случайного числа rand).