Опорный конспект

Тема 23

СТАНДАРТНАЯ БИБЛИОТЕКА ШАБЛОНОВ (STL)

Опытные С++ программисты никогда не начинают проект «с нуля» [6]. Как правило, они используют код из различных источников, например, из стандартной библиотеки шаблонов, библиотек с открытым исходным кодом, оригинальных разработок своей компании и собственных наработок.

Самой важной для С++ программиста является стандартная библиотека С++. Эта библиотека включена в стандарт С++, поэтому ее должен содержать любой компилятор. Стандартная библиотека состоит из отдельных компонентов, одним из которых является стандартная библиотека шаблонов (STL).

Три основных компонента составляют структуру STL:

1.итераторы - специальные указатели, позволяющие алгоритмам перемещаться по данным контейнера;

2.алгоритмы - вычислительные процедуры;

3.контейнеры - блоки хранения данных, управления ими и размещения;

Итераторы

Итератор - это некий обобщенный указатель. Обычные указатели языка C++ являются частным случаем итераторов, позволяющих работать с различными структурами данных и типами универсальным способом. Любой алгоритм (универсальная вычислительная процедура), принимая в качестве параметров итераторы, при их обработке не задумывается о типе данных, на которые передаваемые итераторы ссылаются.

Итераторы бывают пяти видов:

входные (input);

выходные (output);

однонаправленные (forward);

двунаправленные (bidirectional);

произвольного доступа (random access).

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

183

1.vector - массив с произвольным доступом, чаще всего применяемый в тех случаях, когда надо последовательно добавлять данные в конец цепочки;

2.list - похож на вектор, но эффективен при добавлении и удалении

данных в любое место цепочки;

3.deque - контейнер, удобный для вставки данных в начало или конец;

4.set - набор уникальных элементов, отсортированных в определен-

ном порядке;

5.multiset - то же, что и set, но может содержать повторяющиеся копии;

6.map - обеспечивает доступ к значениям по ключам;

7.multimap - то же, что и map, но допускающий повторяющиеся ключи;

8.stack - данные добавляются в одном порядке, а вынимаются в об-

ратном;

9.queue - данные добавляются и вынимаются в том же порядке;

10.priority queue - то же, что и queue, но может сортиро-

вать данные по приоритету.

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

Задача. Создать массив из 10 случайных целых чисел. Отсортировать массив.

#include <iostream> #include <vector> #include <algorithm> #include <ctime> using namespace std; int main(){

vector <int> k; // Объявляем вектор из целых. srand(time(0));

// Добавляем элементы в конец вектора. for(int i=0; i<10;i++)

k.push_back(rand()%100);

vector <int>::iterator p; //объявляем итератор для вектора

Рис. 23.1. Использование шаблона вектора

185

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

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

Задача. Создать массив битов и проиллюстрировать работу битовых операций.

#include <iostream> #include <bitset> using namespace std; int main(){

bitset<3> b0; b0[0] = true; b0[1] = false; b0[2] = true; cout<< b0 <<"\n";

bitset<3> b1(string("001")); cout<< b1 <<"\n";

// Побитовые операции. cout<<"*****\n";

bitset<3> res = b0 & b1; // Побитовое "и" cout << res << "\n"; //false, false, true res = b0 | b1; // Побитовое "или"

cout << res << "\n"; //true, false, true res = b0 ^ b1; // Исключающее "или" cout << res << "\n"; //true, false, false cout<<"*****\n";

// Число установленных битов (т. е. равных true) cout << b0.count() << "\n";

cout << b0.size() << "\n"; // Общее число элементов b0.flip(); // Обращение битов на противоположные cout << b0 << "\n";

b1 = b1<<1; // Сдвиг битов влево cout << b1 << "\n";

b1 = b1.reset(); // Обнуление всех битов cout << b1 << "\n";

return 0;

}

Рис. 23.2. Работа с массивом битов

101

001

*****

186

001

101

100

*****

2

3

010

010

000

Рис. 23.3. Результат работы программы на рис. 23.2

На рис. 23.4 – 23.9 представлена программа [13], которая реализует механизм работы фабрики объектов. Класс ShapeFactory «умеет» создавать различные объекты, производные от объекта Shape. Во всех показанных до этого программах тип создаваемого объекта был известен на момент компиляции. Тип объекта нельзя было передать в качестве параметра (например, в командной строке). Но бывают случаи, когда невозможно заранее знать тип объекта, который нужен будет пользователю. То есть тип создаваемого объекта становится известен в момент выполнения. Для таких целей очень бы пригодились «виртуальные конструкторы». Но язык С++ не поддерживает механизм виртуальных конструкторов. Для реализации такого поведения нужно разрабатывать специальные классы, которые называют «фабриками объектов». Создание такого класса на С++ представляет собой сложную задачу.

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

#include <iostream> #include <map> using namespace std;

class Shape

{

public:

virtual double Area()const = 0; virtual double Perimeter()const = 0;

};

Рис. 23.4. Код базового класса Shape

class Circle:public Shape{ double x,y,rad;

187

public:

Circle(double x1=10, double y1 = 15, double r =

20):x(x1), y(y1),rad(r){}

virtual double Area()const{return 3.14*rad*rad;} virtual double Perimeter()const {return 2*3.14*rad;}};

//функция CreateCircle, вызывающая конструктор класса, описана как внешняя

Shape* CreateCircle(){return new Circle;} const int CIRCLE=2;

Рис. 23.5. Код производного класса Circle и функция создания объекта Cirlce

class Quadre:public Shape{ double x,y,a;

public:

Quadre(double x1=10, double y1 = 15, double r = 20):x(x1), y(y1),a(r){}

virtual double Area()const{return a*a;} virtual double Perimeter()const {return 4*a;}

//функция CreateQuadre, вызывающая конструктор класса, //описана как внутренняя статическая

static Shape* CreateQuadre(){return new Quadre;}}; const int QUADRE=1;

Рис. 23.6. Код производного класса Quadre

class ShapeFactory{ public:

typedef Shape*(*CreateShapeCallBack)(); private:

typedef map<int, CreateShapeCallBack> CallBackMap; public:

static bool RegisterShape(int ShapeID,

ShapeFactory::CallBackMap ShapeFactory::callbacks_;

188

ГЛОССАРИЙ

Абстрактный класс – это класс, объекты которого в программе создать нельзя

Адрес переменной – это адрес области памяти, с которой связана данная переменная

Время жизни – это время, в течение которого переменная связана с определенной областью памяти

Деструктор – функция, вызываемая в момент разрушения объекта. Содержит освобождение динамической памяти, используемой объектом. Имя совпадает с именем класса, но в начале ставится знак ~

Дружественность – отношения между классами или между классом и внешней функцией, позволяющие получить доступ к закрытым и защищенным элементам класса

Заголовочный файл – файл, содержащий прототипы функций и описание пользовательских типов данных. Имеет расширение

.h

Имя переменной – это идентификатор, используемый в программах для ссылки на значение переменной

Индекс – номер позиции элемента массива, заключенный в квадратные скобки

190

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

Исключение – событие, которого не ждали и которое нужно какимто образом обрабатывать

Класс – это абстрактный тип данных, состоящий из элемен- тов-данных и элементов-функций

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

Композиция – включение в класс объектов других типов в качестве элементов

Конкретный класс – класс, объекты которого в программе создать можно

Конструктор – функция класса, используемая для инициализации элементов-данных класса. Имя конструктора совпадает с именем класса

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

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

191

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

Перегрузка функций – определение в программе нескольких функций с одним именем, но разным списком параметров

Переменная – это объект данных, который явным образом определен и именован в программе

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

Программа – алгоритм + структура данных

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

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

Спецификатор – один из private, protected, public. Определядоступа ет доступ к элементу пользовательского класса из

внешних функций или объектов других типов

192