Достоинства и недостатки шаблонов классов.

Достоинства:

· мощное средство обращения с различными типами данных, которое называются параметрическим полиморфизмом

· обеспечивает безопасное использование различных типов данных в отличие от макросов препроцессора

Недостатки:

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

· шаблоны по-разному работают с разными типами данных (следует использовать специализацию шаблонов)

 

Контейнерные классы

Контейнерные классы — это классы, предназначенные для хранения данных, организованных определенным образом. Примерами контейнеров могут служить массивы, линейные списки или стеки. Для каждого типа контейнера определены методы для работы с его элементами, не зависящие от конкретного типа данных, которые хранятся в контейнере, поэтому один и тот же вид контейнера можно использовать для хранения данных различных типов. Эта возможность реализована с помощью шаблонов классов, поэтому часть библиотеки C++, в которую входят контейнерные классы, а также алгоритмы и итераторы, называют стандартной библиотекой шаблонов (STL - Standard Template Library).

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

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

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

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

Пример 1

 class FixStack { /* спецификация класса подобъекта */};

 class BracketSyntax { {/* спецификация контейнерного класса */}

   public: FixStack stack; /* спецификация подобъекта */

   private:           /* спецификация приватных данных */

   public:            /* спецификация компонентных методов,

                             конструктора и деструктора */

};

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

Последовательные контейнеры обеспечивают хранение конечного количества однотипных величин в виде непрерывной последовательности. К ним относятся векторы (vector), двусторонние очереди (deque) и списки (list), а также так называемые адаптеры, то есть варианты, контейнеров — стеки (stack), очереди (queue) и очереди с приоритетами (priority queue).

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

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

Ассоциативные контейнеры обеспечивают быстрый доступ к данным по ключу. Эти контейнеры построены на основе сбалансированных деревьев. Существует пять типов ассоциативных контейнеров:

· словари (mар),

· словари с дубликатами (multimap),

· множества (set),

· множества с дубликатами (multiset)

· битовые множества (bitset).

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

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

 

Практически в любом контейнерном классе определены поля перечисленных ниже типов:

Поле	Пояснение
value type	Тип элемента контейнера
size type	Тип индексов, счетчиков элементов и т. д.
iterator	Итератор
const iterator	Константный итератор
reverse iterator	Обратный итератор
const_reverse iterator	Константный обратный итератор
reference	Ссылка на элемент
const_reference	Константная ссылка на элемент
key_type	Тип ключа (для ассоциативных контейнеров)
key compare	Тип критерия сравнения (для ассоциативных контейнеров)

 

 

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

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

Итераторы

Представим себе данные как некую абстрактную последовательность. Вне зависимости от способа ее организации и типа данных нам требуются средства поэлементного просмотра последовательности и доступа к каждому ее элементу. Итератор обеспечивает эти средства просмотра.

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

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

В стандартной библиотеке итераторы используются для работы с контейнерными классами, потоками и буферами потоков.

В итераторах используются понятия «текущий указываемый элемент» и «указать на следующий элемент». Доступ к текущему элементу последовательности выполняется аналогично указателям с помощью операций * и ->. Переход к следующему элементу - с помощью операции инкремента ++. Для всех итераторов определены также присваивание, проверка на равенство и неравенство. Данные могут быть организованы различным образом - например, в виде массива, списка, вектора или дерева. Для каждого вида последовательности требуется свой тип итератора, поддерживающий различные наборы операций. В соответствии с набором обеспечиваемых операций итераторы делятся на пять категорий. Приведенные в таблице операции обеспечиваются за постоянное время.

Пусть i и j — итераторы одного вида, х — переменная того же типа, что и элемент последовательности, п — целая величина. Тогда допустимы выражения:

1++ ++i i = j i == j i!= j

Категория итератора	Операции	Контейнеры
входной (input)	х = *i	все
выходной (output)	*i = х	все
прямой (forward)	х = *i, *i = x	все
двунаправленный (bidirectional)	x = *i, *i - x, --i, i--	все
произвольного доступа (random access)	x = *i, *i = x, --i, i--, i + n, i - n, i += n, i -= n i < j, i > J, i <= j, i >= J	все, кроме list

Как видно из таблицы, прямой итератор поддерживает все операции входных и выходных итераторов и может использоваться везде, где требуются входные или выходные итераторы. Двунаправленный итератор поддерживает все операции прямого, а также декремент, и может использоваться везде, где требуется прямой итератор. Итератор произвольного доступа поддерживает все операции двунаправленного, а кроме того, переход к произвольному элементу последовательности и сравнение итераторов.

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

Итераторные классы и функции описаны в заголовочном файле <iterator>. При использовании стандартных контейнеров этот файл подключается автоматически.

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

 

Метод	Пояснение
iterator beginO, const iterator beginO const	Указывают на первый элемент
iterator end(), const iterator end() const	Указывают на элемент, следующий за последним
reverse iterator rbeginO, const reversejterator rbeginO const	Указывают на первый элемент в обратной последовательности
reverse iterator rendO, const reverse iterator rendO const	Указывают на элемент, следующий за последним, в обратной последовательности

 

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

Во всех контейнерах определены методы, позволяющие получить сведения о размере контейнеров:

Метод	Пояснение
size()	Число элементов
max_size()	Максимальный размер контейнера (порядка миллиарда элементов)
empty()	Булева функция, показывающая, пуст ли контейнер

 

Другие поля и методы контейнеров мы рассмотрим по мере необходимости. STL определяется в 13 заголовочных файлах:

· algorithm

· deque

· functional

· iterator

· list

· map

· memory

· numeric

· queue

· set

· stack

· utility

· vector

 

Последовательные контейнеры

Векторы (vector), двусторонние очереди (deque) и списки (list) поддерживают разные наборы операций, среди которых есть совпадающие операции. Они могут быть реализованы с разной эффективностью:

Операция	Метод	vector	deque	list
Вставка в начало	push_front	-	+	+
Удаление из начала	pop front	-	+	+
Вставка в конец	push_back	+	+	+

 

Операция	Метод	vector	deque	list
Удаление из конца	pop back	+	+	+
Вставка в произвольное место	insert	(+)	(+)	+
Удаление из произвольного места	erase	(+)	(+)	+
Произвольный доступ к элементу	[ ]. at	+	+	-

 

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

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

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

Двусторонняя очередь эффективно реализует произвольный доступ к элементам, добавление в оба конца и удаление из обоих концов.

Список эффективно реализует вставку и удаление элементов в произвольное место, но не имеет произвольного доступа к своим элементам.

Пример 2

Пример работы с вектором. В файле находится произвольное количество целых чисел. Программа считывает их в вектор и выводит на экран в том же порядке.

#include <fstream> #iinclude <vector> using namespace std: int main(){

ifstream in ("inpnum.txt");

vector<int> v; int x; while (in» x, lin.eofO)

v.push_back(x);

for (vector<int>::iterator i = v.begin(); i!= v.end(); ++i)

cout «*i «" ";

Поскольку файл содержит целые числа, используется соответствующая специализация шаблона vector - vector<int>. Для создания вектора v используется конструктор по умолчанию. Организуется цикл до конца файла, в котором из него считывается очередное целое число. С помощью метода push_back оно заносится в вектор, размер которого увеличивается автоматически1.

Примечание 1

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

Для прохода по всему вектору вводится переменная i как итератор соответствующего типа (напомню, что операция:: обозначает доступ к области видимо-сти, то есть здесь объявляется переменная i типа «итератор для конкретной специализации шаблона»). С помощью этого итератора осуществляется доступ ко всем по порядку элементам контейнера, начиная с первого. Метод beginO возвращает указатель на первый элемент, метод end() — на элемент, следующий за последним. Реализация гарантирует, что этот указатель определен.

Сравнивать текущее значение с граничным следует именно с помощью операции!=, так как операции < или <= могут быть для данного типа не определены. Операция инкремента (i++) реализована так, чтобы после нее итератор указывал на следующий элемент контейнера в порядке обхода. Доступ к элементу вектора выполняется с помощью операции разадресации, как для обычных указателей.

В данном примере вместо вектора можно было использовать любой последовательный контейнер путем простой замены слова vector на deque или list. При этом изменилось бы внутреннее представление данных и набор доступных операций, а в поведении программы никаких изменений не произошло бы.

Однако если вместо цикла for вставить фрагмент

for (int i = 0; i<v.size(); i++) cout << v[i] << " ";

в котором использована операция доступа по индексу [ ], программа не будет работать для контейнера типа list, поскольку в нем эта операция не определена.