Абстрактний тип даних (АТД)
Тип даних, обумовлений тільки через операції, що можуть виконуватися над відповідними об'єктами без відношення до способу представлення цих об'єктів.
АТД містить у собі абстракцію як через параметризацію, так і через специфікацію. Абстракція через параметризацію може бути здійснена так само як і для процедур (функцій) використанням параметрів там, де це має сенс.Абстракція через специфікацію досягається за рахунок того, що операції представляються як частина типу.
Для реалізації АТД необхідно, по-перше, вибрати представлення пам'яті для об'єктів і, по-друге, реалізувати операції в термінах обраного представлення.
Прикладом абстрактного типу даних є клас у мові С++.
2.Перевантаження операцій.
Можливість використовувати знаки стандартних операцій для запису виразів як для вбудованих, так і для АТД.
У мові С++ для перевантаження операцій використовується ключове слово operator, за допомогою якого визначається спеціальна операція-функція (operator function).
Формат операції-функції:
тип_поверн_значення operator знак_операції(специф_параметрів)
{оператори_тіла_функції}
Перевантаження унарних операцій
· Будь-яка унарна операція Å може бути визначена двома способами: або як компонентна функція без параметрів, або як глобальна функція з одним параметром. У першому випадку вираз Å Z означає виклик Z.operatorÅ (), у другому- виклик operatorÅ (Z).
· Унарні операції, що перевантажуються в рамках визначеного класу, можуть перевантажуватися тільки через нестатичну компонентну функцію без параметрів. Викликаний об'єкт класу автоматично сприймається як операнд.
· Унарні операції, що перевантажуються поза областю класу( як глобальні функції), повинні мати один параметр типу класу. Переданий через цей параметр об'єкт сприймається як операнд.
Синтаксис:
а) у першому випадку (опис в області класу):
тип_поверн_значення operator знак_операції
б) у другому випадку (опис поза областю класу):
тип_поверн_значення operator знак_операції(ідентифікатор_типу)
Приклади.
| 1)class person | 2)class person |
| { int age; | { int age; |
| ... | ... |
| public: | public: |
| … | ... |
| void operator++(){ ++age;} | friend void operator++(person&); |
| }; | }; |
| void main() | void person::operator++(person& ob) |
| {class person jon; | {++ob.age;} |
| ++jon;} | void main() |
| {class person jon; | |
| ++jon;} |
Перевантаження бінарних операцій
· Будь-яка бінарна операція Å може бути визначена двома способами: або як компонентна функція з одним параметром, або як глобальна (можливо дружня) функція з двома параметрами. У першому випадку xÅy означає виклик x.operatorÅ(y), у другому – виклик operatorÅ(x,y).
· Операції, що перевантажуються всередині класу, можуть перевантажуватися тільки нестатичними компонентними функціями з параметрами. Викликуваний об'єкт класу автоматично сприймається в якості першого операнда.
· Операції, що перевантажуються поза областю класу, повинні мати два операнди, один із яких повинний мати тип класу.
Приклади.
1)class person{...};
class adresbook
{
// містить у якості компонентних даних множину об'єктів типу
//person, що представляються як динамічний масив, чи список дерево
…
public:
person& operator[](int); //доступ до i-ому об'єкта
};
person& adresbook : : operator[](int i){. . .}
void main()
{class adresbook persons;
class person record;
…
record = persons[3];
}
2) class person{...};
class adresbook
{ // містить у якості компонентних даних множину об'єктів типу //person, що представляються як динамічний масив, чи список дерево
…
public:
friend person& operator[](const adresbook&,int); //доступ до i-ого об'єкта
};
person& operator[](const adresbook& ob ,int i){. . .}
void main()
{class adresbook persons;
class person record;
…
record = persons[3];
}
Перевантаження операції присвоювання
Операція відрізняється трьома особливостями:
· операція не успадковується;
· операція визначена за замовчуванням для кожного класу як операцію порозрядного копіювання об'єкта, що стоїть праворуч від знака операції, в об'єкт, що стоїть ліворуч.
· операція може перевантажуватися тільки в області визначення класу. Це гарантує, що першим операндом завжди буде ліводопустимий вираз.
Формат перевантаженої операції присвоювання:
ім'я_класу& operator=(ім'я_класу&);
Відзначимо дві важливі особливості функції operanor=. По-перше, в ній використовується посилання-параметр-посилання. Це необхідно для запобігання створення копії об'єкта, переданого через параметр за значенням. У випадки створення копії, вона видаляється викликом деструктора при завершенні роботи функції. Але деструктор звільняє розподілену пам'ять, ще необхідну об'єкту, що є аргументом. Посилання-параметр-посилання допомагає вирішити цю проблему.
По-друге, функція operator=() повертає не об'єкт, а посилання на нього. Зміст цього той же, що і при використанні посилання-параметр-посилання. Функція повертає тимчасовий об'єкт, що видаляється після завершення її роботи. Це означає, що для тимчасової змінної буде викликаний деструктор, що звільняє розподілену пам'ять. Але вона необхідна для присвоювання значення об'єкту. Тому, щоб уникнути створення тимчасового об'єкта, як такого, що повертає значення, використовується посилання.
3.Створення додатків у Borland C++ 5.02.
* Проекти і вузли.
Проект- це файл, що містить усе необхідне для побудови кінцевого продукту: встановлені параметри, інформацію про цільове середовище і про вхідні файли. Файл проекту має розширення ide.
Термін “вузол” застосовується для позначення різних об'єктів, що знаходяться у вікні проекту. Кожен вузол може залежати від одного чи більшої кількості вузлів. Це означає, що до обробки такого вузла, ті вузли, від яких він залежить, повинні бути успішно оброблені. Самий верхній вузол в ієрархії вузлів називається метою. Можна внести більше, ніж одну цільову програму в файл .ide. Рекомендується зберігати в одному проекті файли, зв'язані за змістом.
* .Програма з одного модуля.
1.Якщо вихідний файл існує, відкрийте його, вибравши меню File|Open.У противному випадку- меню File|New, команда Text Edit. Введіть вихідний код у нове вікно редактора і збережіть у файлі, вибравши меню File|Save.
2.Активізуйте локальне меню редактора, натиснувши праву кнопку миші в середині вікна( чи Alt+F10) і виберіть опцію Target Expert.З'явиться вікно діалогу Target Expert.
3.Виберіть для вашої програми придатні параметри і натисніть Ok. Наприклад, можна побудувати програму як стандартний додатокDOC, як додаток EasyWinдля Windows 3.x(16-ти розрядне) чи типу Console для Win32. Рекомендується будувати EasyWinпрограму.
4.У меню Debug(Налагодження) виберіть Sun(Виконати). Програма буде відкомпільована, відредагована і виконана.
5.Для прискорення повторної компіляція у випадку виявлення і виправлення помилок рекомендується встановити режим прекомпіляції і збереження відкомпільованого коду заголовних файлів. Для цього в меню Options|Project|Compilerвиберіть опцію Precompiled Headersі встановіть прапорець Generate and use.
* .Проекти і багатомодульні програми.
Якщо для створення програми використовується кілька вихідних модулів, ви повинні організувати проект.
Для організації проекту:
1.У меню File|Newвиберіть Project. З'явиться вікноNew Target.Це розширений варіант вікнаTarget Expert.
2.У вікні вкажіть ім'я проекту (Project Path and Name), ім'я і тип вхідного модуля(Target Name) і необхідні специфікації бібліотек С++.
3.Виберіть кнопку Advanced, щоб уточнити проект. З'явиться вікно Advanced Options.
4.Якщо програма не застосовує керування ресурсами і не містить у собі файл.def, виключте селектори .rcі .def.
5.Закрийте вікна Advanced Optionsі New Target( кнопкою Ok).
6.У вікні, що з'явилося, Project за допомогою правої кнопки миші вкажіть вузол, щоб активізувати його локальне меню. Щоб включити у проект нові модулі, виберіть у меню опцію Add Node.З'явиться вікно Add to Proect List, що дозволить вам знайти і вказати ті файли, які потрібно включити в проект.
7.Після того, як ви підключили нові вузли, за допомогою правої кнопки миші вкажіть на цільовий вузол. Тепер щоб побудувати програму, виберіть опцію Make Node.
8.Після того як ви створили і зберегли проект, ви зможете надалі завантажувати його в IDEкомандою Open Projectу меню Project.При цьому завантажуються всі зв'язані з ним файли.
* .Побудова декількох цільових модулів.
1.У менюProject виберіть New Target. З'явиться вікно діалогу Add Target.
2.Введіть ім'я цільового модуля, встановіть тип мети(Standard) і натисніть Ok. З'явиться вікно New Target.
3.Встановіть у вікні New Targetнеобхідні параметри.
4.Якщо необхідно знову створений цільовий вузол зробити підвузлом іншого вузла, то за допомогою лівої кнопки миші “перенесіть” вузол і “покладіть” його на вузол, підвузлом якого він буде.
5.Викличте правою кнопкою миші локальне меню цільового вузла і виберіть Build Node, щоб побудувати програму.
4.Що таке EasyWin програма?
Інтегроване середовище розробки(IDE) BC++5.02 дає можливість створювати спеціальний вид програм, називаних EasyWin програмами, що виконуються в простому вікні, що нагадує вікно Windows. Це вікно містить стандартні кнопки і смуги скролера. Текст у вікні виводиться в кодуванні Windows, що не створює проблем з кирилицею.
* Порядок створення EasyWin програми.
1.Завантажите IDE BC++5.02.
2.Виберіть меню File.
3.Виберіть команду New/Project , щовикликає вікно New Target.
4.Введіть маршрут і ім'я файлу проекту .ide у поле введення у верхній частині вікна(поле Project Path and Name) . Введене ім'я буде повторено в поле введення імені мети (поле Target Name), тим самим ім'я програми буде відповідати імені проекту. Кнопка Browsслужить длявибору каталогу, що містить файли проекту.
5.Виберіть EasyWin[.exe] у списку Target Type.
6.Клацніть на кнопці Advanced, щоб викликати діалогове вікно Advanced Options . Виберіть у ньому перемикач, позначений як.cpp Node. Цей вибір змусить IDE вставляти .cpp вузли. Це діалогове вікно дає також можливість додавати чи видаляти модулі .rc і .def. Тому що реально вони потрібні тільки при створенні Windows-додатків, а не EasyWin, упевніться, що ці дві кнопки не вибрані. Закрийте вікно (Оk).
7.Натисніть Оk, щоб створити новий файл проекту.
8.IDE виведе вікно проекту Project, у якому перераховані вузли різних програм. Коли Ви створюєте новий файл проекту, вікно Project буде містити тільки один вузол.
9.Вузли програми EasyWin містять тільки один файл - .срр із текстом програми. Двічі клацніть на файлі .срр, для того щоб почати редагування цього файлу.
10.Введіть вихідний текст програми.
11.Відкомпілюйте програму (F9).
12.Виправте помилки і повторіть компіляцію
13.Повторюйте пункт 12, поки компіляція не буде виконуватися без помилок .
14.Виконайте програму (Ctrl+F9).
Порядок виконання роботи.
1.Вибрати клас АТД відповідно до варіанта.
2.Визначити і реалізувати в класі конструктори, деструктор, функції Input(введення з клавіатури) і Print(висновок на екран), перевантажити операцію присвоювання.
3.Написати програму тестування класу і виконати тестування.
4.Доповнити визначення класу заданими перевантаженими операціями (відповідно до варіанта).
5.Реалізувати ці операції. Виконати тестування.
Методичні вказівки.
1.Клас АТД реалізувати як динамічний масив. Для цього визначення класу повинне мати наступні поля:
- покажчик на початок масиву;
- максимальний розмір масиву;
- поточний розмір масиву.
2.Конструктори класу розміщають масив у пам'яті і встановлюють його максимальний і поточний розмір. Для завдання максимального масиву використовувати константу, обумовлену поза класом.
3.Щоб у вас не виникало проблем, акуратно працюйте з константами об'єктами. Наприклад:
* конструктор копіювання варто визначити так:
MyClass(constMyClass& ob);
* операцію присвоювання перевантажити так:
MyClass& operator = (const MyClass& ob);
4.Для зручності реалізації операцій-функцій реалізувати в класі private (protected) функції, що працюють безпосередньо з реалізацією класу. Наприклад, для класу множину - це можуть бути наступні функції:
- включити елемент у множину;
- знайти елемент і повернути його індекс;
- видалити елемент;
- визначити, чи належить елемент множини.
Зазначені функції використовуються в реалізації загальнодоступних функцій-операцій (operator).
Зміст звіту.
1.Титульний лист.
2.Конкретне завдання з вказуванням номера варіанта, реалізованого класу й операцій.
3.Визначення класу.
4.Обґрунтування включення в клас декількох конструкторів, деструктора й операції присвоювання.
5.Пояснити обране представлення пам'яті для об'єктів реалізованого класу.
6.Реалізація перевантажених операцій з обґрунтуванням обраного способу (функція-член класу, зовнішня функція, зовнішня дружня функція).
7.Тестові дані і результати тестування.
Питання для самоконтролю.
1.Що таке абстрактний тип даних?
2.Приведіть приклади абстрактних типів даних.
3.Які синтаксис/семантика “функції-операції-функції”?
4.Як можна викликати операцію-функцію?
5.Чи потрібно перевантажувати операцію присвоювання щодо визначеного користувачем типу даних, наприклад класу? Чому?
6.Чи можна змінити пріоритет перевантаженої операції?
7.Чи можна змінити кількість операндів перевантаженої операції?
8.Чи можна змінити ассоціативність перевантаженої операції?
9.Чи можна, використовуючи дружню функцію, перевантажити оператор присвоювання?
10.Чи всі оператори мови С++ можуть бути перевантажені?
11.Якими двома різними способами визначаються перевантажені операції?
12.Чи всі операції можна перевантажити за допомогою глобальної дружньої функції?
13.У яких випадках операцію можна перевантажити тільки глобальною функцією?
14.У яких випадках глобальна операція-функція повинна бути дружньою?
15.Чи обов'язковий у функції operator параметр типу “клас” чи “посилання на клас”?
16.Чи успадковуються перевантажені операції?
17.Чи можна повторно перевантажити в похідному класі операцію, перевантажену в базовому класі?
18.У чому відмінність синтаксису функції-операції-функції унарної і бінарної операції?
19.Приведіть приклади перевантаження операцій для стандартних типів.
20.Перевантажте операцію “+” для класу “комплексне число”.
21.Перевантажте операції “<”,”>”,”==” для класу “рядок символів”.
Додаток. Варіанти завдань.
1.АТД-множина з елементами типу char.Додатково перевантажити наступні операції:
“+” - додати елемент у множину (типу char + set);
“+” - об'єднання множин;
“==” - перевірка множин на рівність.
2.АТД-множина з елементами типу char.Додатково перевантажити наступні операції:
“-” - видалити елемент із множини (типу set-char);
“*” - перетинання множин;
“<” - порівняння множин .
3.АТД-множина з елементами типу char.Додатково перевантажити наступні операції:
“-” - видалити елемент із множини (типу set-char);
“>” - перевірка на підмножину;
“!=” - перевірка множин на нерівність.
4.АТД-множина з елементами типу char.Додатково перевантажити наступні операції:
“+” - додати елемент у множину (типу set+char);
“*” - перетинання множин;
“int()” - потужність множини.
5.АТД-множина з елементами типу char.Додатково перевантажити наступні операції:
“()” - конструктор множини (у стилі конструктора Паскаля);
“+” - об'єднання множин;
“<=” - порівняння множин .
6.АТД-множина з елементами типу char.Додатково перевантажити наступні операції:
“>” - перевірка на приналежність (char in set Паскаля);
“*” - перетинання множин;
“<” - перевірка на підмножину.
7.АДТ-однонаправлений список з елементами типу char. Додатково перевантажити наступні операції:
“+” – об’єднати списки (list+list);
“--” - видалити елемент із початку (типу –list);
“==” перевірка на рівність.
8.АДТ-однонаправлений список з елементами типу char. Додатково перевантажити наступні операції:
“+” - додати елемент у початок (char+list);
“--” - видалити елемент із початку (типу –list);
“==” - перевірка на рівність.
9.АДТ-однонаправлений список з елементами типу char. Додатково перевантажити наступні операції:
“+” - додати елемент у кінець (list+char);
“-і” - видалити елемент із кінця (типу list-і);
“!=” - перевірка на нерівність.
10.АДТ-однонаправлений список з елементами типу char. Додатково перевантажити наступні операції:
“[]” - доступ до елемента в заданій позиції, наприклад:
int i; char c;
list L;
c=L[i];
“+” - об'єднати два списки;
“==” - перевірка на рівність.
11.АДТ-однонаправлений список з елементами типу char. Додатково перевантажити наступні операції:
“[]” - доступ до елемента в заданій позиції, наприклад:
int i; char c;
list L;
c=L[i];
“+” - об'єднати два списки;
“!=” - перевірка на нерівність.
12.АДТ-однонаправлений список з елементами типу char. Додатково перевантажити наступні операції:
“()” - видалити елемент у заданій позиції, наприклад :
int i;
list L;
L[i];
“()” - додати елемент у задану позицію, наприклад :
int i; char c;
list L;
L[c,i];
“!=” перевірка на нерівність.
13.АТД-стек. Додатково перевантажити наступні операції:
“+” - додати елемент у стек;
“—“ - витягти елемент зі стека;
bool() - перевірка чи порожній стек?
14.АТД-черга. Додатково перевантажити наступні операції:
“+” - додати елемент ;
“—“ - витягти елемент ;
bool() - перевірка чи порожня черга?
15.АТД-одномірний масив (вектор) дійсних чисел. Додатково перевантажити наступні операції:
“+” - додавання векторів (a[i]+b[i] для всіх i);
“[]” - доступ по індексі;
“+” - додати число до вектора (double+vector).
16.АТД-одномірний масив (вектор) дійсних чисел. Додатково перевантажити наступні операції:
“-” - віднімання векторів (a[i]-b[i] для всіх i);
“[]” - доступ по індексі;
“-” - відняти з вектора число (vector-double).
17.АТД-одномірний масив (вектор) дійсних чисел. Додатково перевантажити наступні операції:
“*” - множення векторів (a[i]*b[i] для всіх i);
“[]” - доступ за індексом;
“*” - помножити вектор на число (vector*double).
18.АТД-одномірний масив (вектор) дійсних чисел. Додатково перевантажити наступні операції:
“int()” - розмір вектора;
“()” - встановити новий розмір;
“-” - відняти з вектора число (vector-double);
“[]” - доступ за індексом;
19.АТД-одномірний масив (вектор) дійсних чисел. Додатково перевантажити наступні операції:
“=” - привласнити всім елементам вектора значення (vector=double);
“[]” - доступ за індексом;
“==” - перевірка на рівність;
“!=” - перевірка на нерівність;
20.АТД-двомірний масив (матриця) дійсних чисел. Додатково перевантажити наступні операції:
“()” - доступ за індексом;
“*” - множення матриць;
“*” - множення матриці на число;
“*” - множення числа на матрицю.
21.АТД-двомірний масив (матриця) дійсних чисел. Додатково перевантажити наступні операції:
“()” - доступ за індексом;
“-” - різниця матриць;
“-” - відняти з матриці число;
“==” - перевірка матриць на рівність.
22.АТД-двомірний масив (матриця) дійсних чисел. Додатково перевантажити наступні операції:
“()” - доступ за індексом;
“=” - привласнити всім елементам матриці значення (matr=double);
“+” - додавання матриць;
“+” - скласти матрицю з числом (matr+double).
23.АТД-двомірний масив (матриця) дійсних чисел. Додатково перевантажити наступні операції:
“()” - доступ за індексом;
“==” - перевірка матриць на рівність.
“++” - транспонувати матрицю;
Лабораторна робота №6.
Шаблони функцій і класів.
Мета. Одержати практичні навички створення шаблонів і використання їх у програмах С++ .
Основний зміст роботи.
Створити шаблон заданого класу і використовувати його для даних різних типів.
Короткі теоретичні відомості.
Шаблон функції.
Шаблон функції (інакше параметризована функція) визначає загальний набір операцій (алгоритм), що будуть застосовуватися до даних різних типів. При цьому тип даних, над якими функція повинна виконувати операції, передається їй у виді параметра на стадії компіляції.
У С++ параметризована функція створюється за допомогою ключового слова template. Формат шаблона функції:
template <class тип_даних> тип_поверн_значення ім'я_функції(список_параметрів){тіло_функції}
Основні властивості параметрів шаблона функції.
* Імена параметрів шаблона повинні бути унікальними у всім визначенні шаблона.
* Список параметрів шаблона не може бути порожнім.
* У списку параметрів шаблона може бути кілька параметрів і кожному з них повинне передувати ключове слово class.
* Ім'я параметра шаблона має усі права імені типу у визначеної шаблоном функції.
* Визначена за допомогою шаблона функція може мати будь-яку кількість непараметризованих формальних параметрів. Може бути непараметризоване і значення, що повертається функцією.
* У списку параметрів прототипу шаблона імена параметрів не зобов'язані збігатися з іменами тих же параметрів у визначенні шаблона.
* При конкретизації параметризованої функції необхідно, щоб при виклику функції типи фактичних параметрів, що відповідають однаково параметризованим формальним параметрам, були однакові.
Шаблон класу.
Шаблон класу(інакше параметризований клас) використовується для побудови родового класу. Створюючи родовий клас, ви створюєте ціле сімейство родинних класів, які можна застосовувати до будь-якого типу даних. Таким чином, тип даних, яким оперує клас, указується як параметр при створенні об'єкта, що належить до цього класу. Подібно тому, як клас визначає правила побудови і формат окремих об'єктів, шаблон класу визначає спосіб побудови окремих класів. У визначенні класу, що входить у шаблон, ім'я класу є не ім'ям окремого класу, а параметризованим ім'ям сімейства класів.
Загальна форма оголошення параметризованого класу:
template <class тип_даних> class ім'я_класу { . . . };
Основні властивості шаблонів класів.
* Компонентні функції параметризованого класу автоматично є параметризованими. Їх не обов'язково повідомляти як параметризовані за допомогою template.
* Дружні функції, що описуються в параметризованому класі, не є автоматично параметризованими функціями, тобто за замовчуванням такі функції є дружніми для всіх класів, що організуються по даному шаблоні.
* Якщо friend-функція містить у своєму описі параметр типу параметризованого класу, то для кожного створеного по даному шаблоні класу є власна friend-функція.
* У рамках параметризованого класу не можна визначити friend-шаблони (дружні параметризовані класи).
* З однієї сторони шаблони можуть бути похідними (успадковуватися) як від шаблонів, так і від звичайних класів, з іншого боку, вони можуть використовуватися в якості базових для інших шаблонів чи класів.
* Шаблони функцій, які є членами класів, не можна описувати як virtual.
* Локальні класи не можуть містити шаблони як свої елементи.
Компонентні функції параметризованих класів
Реалізація компонентної функції шаблона класу, що знаходиться поза визначенням шаблона класу, повинна включати додатково наступні два елементи:
* Визначення повинне починатися з ключового слова template, за яким слідує такий же список_параметрів_типів у кутових дужках, який зазначений у визначенні шаблона класу.
* За ім'ям_класу, що передує операції області видимості (::), повинний слідувати список_імен_параметрів шаблона.
template<список_типів>тип_поверн_значення ім'я_класу<список_імен_ параметрів> : : ім'я_функції(список_параметрів){ . . . }
Порядок виконання роботи.
1.Створити шаблон заданого класу. Визначити конструктори, деструктор, перевантажену операцію присвоювання (“=”) і операції, задані у варіанті завдання.
2.Написати програму тестування, у якій перевіряється використання шаблона для стандартних типів даних.
3.Виконати тестування.
4.Визначити клас користувача, що буде використовуватися як параметр шаблона. Визначити в класі необхідні функції і перевантажені операції.
5.Написати програму тестування, у якій перевіряється використання шаблона для типу користувача.
6.Виконати тестування.
Методичні вказівки.
1.Клас АТД реалізувати як динамічний масив. Для цього визначення класу повинне мати наступні поля:
- покажчик на початок масиву;
- максимальний розмір масиву;
- поточний розмір масиву.
2.Для вводу і виводу визначити в класі функції input і print.
3.Щоб у вас не виникало проблем, акуратно працюйте з константами об'єктами. Наприклад:
* конструктор копіювання варто визначити так:
MyTmp (constMyTmp& ob);
* операцію присвоювання перевантажити так:
MyTmp& operator = (const MyTmp& ob);
4.Для шаблонів множин, списків, стеків і черг як стандартні типи використовувати символьні, цілі і речовинні типи. Для типу користувача взяти клас з лабораторної роботи №1.
5.Для шаблонів масивів як стандартні типи використовувати цілі і дійсні типи. Для типу користувача взяти клас “комплексне число” complex.
class complex{
int re; // дійсна частина
int im; // мнима частина
public;
// необхідні функції і перевантажені операції
};
6.Реализацию шаблона варто розмістити разом з визначенням у заголовному файлі.
7.Програма створюється як EasyWin-додаток у Borland C++5.02.
8.Тестування повинне бути виконане для всіх типів даних і для всіх операцій.
Зміст звіту.
1.Титульний лист: назва дисципліни, номер і найменування роботи, прізвище, ім'я, по батькові студента, дата виконання.
2.Постановка задачі.
Варто дати конкретну постановку, тобто вказати шаблон якого класу повинний бути створений, які повинні бути в ньому конструктори, компоненти-функції, перевантажені операції і т.д.
Те ж саме варто вказати для класу користувача.
3.Визначення шаблона класу з коментарями.
4.Визначення класу користувача з коментарями.
5.Реалізація конструкторів, деструктора, операції присвоювання й операцій, що задані у варіанті завдання.
6.Те ж саме для класу користувача.
7.Результати тестування. Варто вказати для яких типів і яких операцій перевірені і які виявлені помилки(чи не виявлені).
Питання для самоконтролю.
1.У чому зміст використання шаблонів?
2.Які синтаксис/семантика шаблонів функцій?
3.Які синтаксис/семантика шаблонів класів?
4.Напишіть параметризовану функцію сортування масиву методом обміну.
5.Визначте шаблон класу “вектор” - одномірний масив.
6.Що таке параметри шаблона функції?
7.Перелічіть основні властивості параметрів шаблона функції.
8.Як записувати параметр шаблона?
9.Чи можна перевантажувати параметризовані функції?
10.Перелічіть основні властивості параметризованих класів.
11.Чи може бути порожнім список параметрів шаблона? Поясніть.
12.Як викликати параметризовану функцію без параметрів?
13.Чи всі компонентні функції параметризованого класу є параметризованими?
14.Чи є дружні функції, описані в параметризованому класі, параметризованими?
15. Чи можуть шаблони класів містити віртуальні компонентні функції?
16.Як визначаються компонентні функції параметризованих класів поза визначенням шаблона класу?
Варіанти завдань.
1.Клас-одномірний масив. Додатково перевантажити наступні операції:
“*” - множення масивів;
“[]” - доступ за індексом;
2.Клас-одномірний масив. Додатково перевантажити наступні операції:
“int()” - розмір масиву;
“[]” - доступ за індексом;
3.Клас-одномірний масив. Додатково перевантажити наступні операції:
“[]” - доступ за індексом;
“==” - перевірка на рівність;
“!=” - перевірка на нерівність;
4.Клас-множина set.Додатково перевантажити наступні операції:
“+” - додати елемент у множину (типу set+item);
“+” - об'єднання множин.
“*” - перетинання множин;
5.Клас- множина set.Додатково перевантажити наступні операції:
“+” - додати елемент у множину (типу item + set);
“+” - об'єднання множин;
“==” - перевірка множин на рівність.
6.Клас-множина set.Додатково перевантажити наступні операції:
“-” - видалити елемент із множин (типу set-item);
“*” - перетинання множин;
“<” - порівняння множин .
7.Клас-множина set.Додатково перевантажити наступні операції:
“-” - видалити елемент із множини (типу set-item);
“>”- перевірка на підмножину;
“!=” - перевірка множин на нерівність.
8.Клас-множина set.Додатково перевантажити наступні операції:
“+” - додати елемент у множину (типу set+item);
“*” - перетинання множин;
“int()” - потужність множини.
9.Клас-множина set.Додатково перевантажити наступні операції:
“()” - конструктор множини (у стилі конструктора для множинного типу в мові Pascal);
“+” - об'єднання множин;
“<=” - порівняння множин .
10.Клас-множина set.Додатково перевантажити наступні операції:
“>” - перевірка на приналежність (типу операції inмножинного типу в мові Pascal);
“*” - перетинання множин;
“<” - перевірка на підмножину.
11.Класс-однонаправлений список list. Додатково перевантажити наступні операції:
“+” - додати елемент у початок (list+item);
“--” - видалити елемент із початку (--list);
“==” - перевірка на рівність.
12.Класс-однонаправлений список list. Додатково перевантажити наступні операції:
“+” - додати елемент у початок (item+list);
“-і” - видалити елемент із початку ( -іlist);
“!=” - перевірка на нерівність.
13.Класс-однонаправлений список list. Додатково перевантажити наступні операції:
“+” - додати елемент у кінець (list+item);
“-і” - видалити елемент із кінця (типу list-і);
“!=” - перевірка на нерівність.
14.Класс-однонаправлений список list. Додатково перевантажити наступні операції:
“[]” - доступ до елемента в заданій позиції, наприклад:
Type c;
int i;
list L;
c=L[i];
“+” - об'єднати два списки;
“==” - перевірка на рівність.
15.Класс-однонаправлений список list. Додатково перевантажити наступні операції:
“[]” - доступ до елемента в заданій позиції, наприклад:
int i; Type c;
list L;
c=L[i];
“+” - об'єднати два списки;
“!=” перевірка на нерівність.
16.Класс-однонаправлений список list. Додатково перевантажити наступні операції:
“()” - видалити елемент у заданій позиції, наприклад :
int i;
list L;
L(i);
“()” - додати елемент у задану позицію, наприклад :
int i;
Type c;
list L;
L(c,i);
“!=” - перевірка на нерівність.
17.Клас-стек stack. Додатково перевантажити наступні операції:
“+” - додати елемент у стек;
“—“ - витягти елемент зі стека;
bool() - перевірка чи порожній стек?
18.Клас-черга queue. Додатково перевантажити наступні операції:
“+” - додати елемент ;
“—“ - витягти елемент ;
bool() - перевірка чи порожня черга?
19.Клас-одномірний масив. Додатково перевантажити наступні операції:
“+” - додавання масивів;
“[]” - доступ за індексом;
“+” - скласти елемент із масивом.
20.Клас-одномірний масив. Додатково перевантажити наступні операції:
“-” – віднімання масивів;
“[]” - доступ за індексом;
“-” - відняти з масиву елемент.
Лабораторна робота №7.
Потокові класи.
Мета. Навчитися програмувати ввід і вивід у С++, використовуючи об'єкти потокових класів стандартної бібліотеки С++.
Основний зміст роботи.
Створення даних типу користувача, створення і збереження об'єктів цього типу у файлі, читання їх з файлу, видалення з файлу, коректування у файлі, створення маніпуляторів користувача.
Основні теоретичні відомості.
Поняття потоку.
Потокові класи представляють об'єктно-орієнтований варіант функцій ANSI-C. Потік даних між джерелом і приймачем при цьому має наступні властивості:
- Джерело чи приймач даних визначається об'єктом потокового класу.
- Потоки використовуються для вводу-виводу високого рівня.
- Загальноприйняті стандартні С-функції вводу/виводу розроблені як функції потокових класів, щоб полегшити перехід від С-функцій до С++ класів.
- Потокові класи поділяються на три групи (шаблонів класів)
· basic_istream, basic_ostream – загальні потокові класи, що можуть бути зв'язані з будь-яким буферним об'єктом;
· basic_ifstream, basic_iostream – потокові класи для зчитування і запису файлів;
· basic_istringstream, basic_ostringstream – потокові класи для об'єктів-рядків.
- Кожен потоковий клас підтримує буферний об'єкт, що надає пам'ять для переданих даних, а також найважливіші функції вводу/виводу низького рівня для їх обробки.
- Базовим шаблоном класів basic_ios для (потокових класів) і basic_streambuf (для буферних класів) передаються по два параметра шаблона:
· перший параметр (char) визначає символьний тип;
· другий параметр (traits) – об'єкт типу ios_traits (шаблон класу), у якому заданий тип і функції специфічні для використаного символьного типу;
· для типів char і wchar_t утворені відповідні об'єкти типу ios_traits і потокові класи.
Приклад шаблона потокового класу.
template <class char, class traits = ios_traits <char>> class basic_istream: virtual public basic_ios <char, traits>;
Потокові класи в С++.
Бібліотека потокових класів С++ побудована на основі двох базових класів: ios і streambuf.
Клас streambuf забезпечує організацію і взаємозв'язок буферів вводу-виводу, розташовуваних у пам'яті, з фізичними пристроями вводу-виводу. Методи і дані класу streambuf програміст явно звичайно не використовує. Цей клас потрібний іншим класам бібліотеки вводу-виводу. Він доступний і програмісту для створення нових класів на основі вже існуючих.
Схема ієрархії
Клас ios містить засоби для форматованого вводу-виводу і перевірки помилок.
Схема ієрархії
 |
istream – клас вхідних потоків;
ostream – клас вихідних потоків;
iostream – клас вводу-виводу;
istrstream – клас вхідних строкових потоків;
ifstream – клас вхідних файлових потоків і т.д.
Потокові класи, їх методи і дані стають доступними в програмі, якщо в неї включений потрібний заголовний файл.
iostream.h - для ios, ostream, istream.
strstream.h - для strstream, istrstream, ostrstream
fstream.h - для fstream, ifstream, ofstream
Базові потоки вводу-виводу
Для введення з потоку використовуються об'єкти класу istream. Для виводу в потік - об'єкти класу ostream.
У класі istream визначені наступні функції.
· istream& get (char* buffer, int size, char delimiter='\n');
Ця функція витягає символи з istream і копіює їх у буфер. Операція припиняється при досягненні кінця файлу, або коли буде скопійовано size символів, або при виявленні зазначеного роздільника. Сам роздільник не копіюється і залишається в streambuf. Послідовність прочитаних символів завжди завершується нульовим символом.
· istream& read(char* buffer,int size);
Не підтримує роздільників, і зчитані в буфер символи не завершуються нульовим символом. Кількість зчитаних символів запам'ятовується в istream::gcount_ (private).
· istream& getline(char* buffer,int size, char delimiter='\n');
Роздільник витягається з потоку, але в буфер не заноситься. Це основна функція для витягу рядків з потоку. Зчитані символи завершуються нульовим символом.
· istream& get(streambuf& s,char delimiter='\n');
Копіює дані з istream у streambuf доти, поки не знайде кінець файлу чи символ-роздільник. Останній не витягається з istream. У s нульовий символ не записується.
· istream get (char& C);
Читає символ з istream у С. У випадку помилки, С приймає значення 0XFF.
· int get();
Витягає з istream черговий символ. При виявленні кінця файлу повертає EOF.
· int peek();
Повертає черговий символ з istream, не витягаючи його з istream.
· int gcount();
Повертає кількість символів, зчитаних під час останньої операції неформатованого вводу.
* istream& putback(З)
Якщо в області get об'єкта streambuf є вільний простір, то туди міститься символ С.
* istream& ignore(int count=1,int target=EOF);
Витягає символ з istream, поки не відбудеться наступне:
- функція не витягне count символів;
- не буде виявлений символ target;
- не буде досягнуто кінця файлу.
У класі ostream визначені наступні функції.
* ostream& put(char C);
Поміщає в ostream символ С.
* ostream& write(const char* buffer,int size);
Записує в ostream вміст буфера. Символи копіюються доти, поки не виникне помилка чи не буде скопійовано size символів. Буфер записується без форматування. Обробка нульових символів нічим не відрізняється від обробки інших. Дана функція здійснює передачу неопрацьованих даних (бінарних чи текстових) у ostream.
* ostream& flush();
Скидає буфер streambuf.
Для прямого доступу використовуються наступні функції установки позиції читання - запису.
При читанні
* istream& seekg(long p);
Встановлює покажчик потоку get (не плутати з функцією) зі зсувом р від початку потоку.
* istream& seekg(long p,seek_dir point);
Вказується початкова точка переміщення
* enum seek_dir{beg,curr,end}
Позитивне значення р переміщає покажчик get вперед (до кінця потоку), негативне значення р – назад (до початку потоку).
* long tellg();
Повертає поточне положення покажчика get.
При записі
*ostream& seekp(long p);
Переміщає покажчик put у streambuf на позицію р від початку буфера streambuf.
* ostream& seekp(long p,seek_dir point);
Вказується точка відліку.
* long tellp();
Повертає поточне положення покажчика put.
Крім цих функцій у класі istream перевантажена операція >>, а в класі ostream <<. Операції << і >> мають два операнда Лівим операндом є об'єкт класу istream (ostream), а правим – дане, тип якого заданий у мові.
Для того щоб використовувати операції << і >> для всіх стандартних типів даних використовується відповідне число перевантажених функцій operator<< і operator>>. При виконанні операцій вводу-виводу в залежності від типу правого операнда викликається та чи інша перевантажена функція operator.
Підтримуються наступні типи даних: цілого, речовинні, рядка (char*). Для висновку – void* (усі покажчики, відмінні від char*, автоматично переводяться до void*). Перевантаження операції >> і << не змінюють їх пріоритету.
Функції operator<< і operator>>повертають посилання на той потоковий об'єкт, що зазначений ліворуч від знака операції. Таким чином, можна формувати “ланцюжок ” операцій.
cout << a << b << c;
cin >> i >> j >> k;
При вводі-виводі можна виконувати форматування даних.
Щоб використовувати операції >> і << з даними типів користувачів, обумовлених користувачем, необхідно розширити дія цих операцій, ввівши нові операції-функції. Першим параметром операції-функції повинна бути посилання на об'єкт потокового типу, другим – посилання на об'єкт типу користувача.
У файлі iostream.h визначені наступні об'єкти, зв'язані зі стандартними потоками вводу-виводу.
cin – об'єкт класу istream, зв'язаний зі стандартним буферизованим вхідним потоком.
cout – об'єкт класу ostream, зв'язаний зі стандартним буферизованим вихідним потоком.
cerr – не буферизований вихідний потік для повідомлення про помилки.
clog – буферизований вихідний потік для повідомлення про помилки.
Форматування
Безпосереднє застосування операцій вводу << і виводу >> до стандартних потоків cout, cin, cerr, clog для даних базових типів приводить до використання форматів зовнішнього представлення, що “замовчуються”, значень, що пересилаються.
Формати представлення виведеної інформації і правила сприйняття даних при вводі можуть бути змінені програмістом за допомогою прапорів форматування. Ці прапори успадковані всіма потоками з базового класу ios. Прапори форматування реалізовані у виді окремих фіксованих бітів і зберігаються в protected компоненті класу long x_flags. Для доступу до них наявні відповідні public функції.
Крім прапорів форматування використовуються наступні protected компонентні дані класу ios.
int x_width – мінімальна ширина поля виводу.
int x_precision – точність представлення дійсних чисел (кількість цифр дробової частини) при виводі.
int x_fill – символ заповнювач при виводі, за замовчуванням – пробіл.
Для одержання (встановлення) значень цих полів використовуються наступні компонентні функції
int width();
int width(int);
int precision();
int precision(int);
char fill();
char fill(char);
Маніпулятори
Незважаючи на гнучкість і великі можливості керування форматами за допомогою компонентних функцій класу ios, їхнє застосування достатньо громіздке. Більш простий спосіб зміни параметрів і прапорів форматування забезпечують маніпулятори.
Маніпуляторами називаються спеціальні функції, що дозволяють модифікувати роботу потоку. Особливість маніпуляторів полягає в тому, що їх можна використовувати в якості правого операнда операції >> чи <<. У якості лівого операнда, як звичайно, використовується потік (посилання на потік), і саме на цей потік впливає маніпулятор.
Для забезпечення роботи з маніпуляторами в класах istream і ostream є наступні перевантажені функції operator.
istream& operator>>(istream&(*_f)( istream&));
ostream& operator<<(ostream&(*_f)(ostream&));
При використанні маніпуляторів варто включити заголовний файл <iomanip.h>, у якому визначені вбудовані маніпулятори.
Визначення користувальницьких маніпуляторів
Порядок створення маніпулятора користувача з параметрами, наприклад для виводу наступний:
1.Визначити клас (my_manip) з полями: параметри маніпулятора + поле – покажчик на функцію типу
ostream& (*f)(ostream&,<параметри маніпулятора>);
2.Визначити конструктор цього класу (my_manip) з ініціалізацією полів.
3.Визначити в цьому класі дружню функцію – operator<<. Ця функція як правий аргумент приймає об'єкт класу (my_manip) лівого аргументу (операнда), потік ostream і повертає потік ostream як результат виконання функції *f. Наприклад,
typedef far ostream&(far *PTF)(ostream&,int,int,char);
class my_man{
int w;int n;char fill;
PTF f;
public:
//конструктор
my_man(PTF F,int W,int N,char FILL):f(F),w(W),n(N),fill(FILL){}
friend ostream& operator<<(ostream&,my_man& );
};
ostream& operator<<(ostream& out,my_man& my)
{return my.f(out,my.w,my.n,my.fill);}
4.Визначити функцію типу *f (fmanip), що приймає потік і параметри маніпулятора і повертаючу потік. Ця функція власне і виконує форматування. Наприклад,
ostream& fmanip(ostream& s,int w,int n,char fill)
{s.width(w);
s.flags(ios::fixed);
s.precision(n);
s.fill(fill);
return s;}
5.Визначити власне маніпулятор (wp) як функцію, що приймає параметри маніпулятора і повертає об'єкт my_manip, поле f якого містить покажчик на функцію fmanip. Наприклад,
my_man wp(int w,int n,char fill)
{return my_man(fmanip,w,n,fill);}
Для створення користувальницьких маніпуляторів з параметрами можна використовувати макроси, що містяться у файлі <iomanip.h>:
OMANIP(int)
IMANIP(int)
IOMANIP(int)
Стан потоку
Кожен потік має зв'язаний з ним стан. Стани потоку описуються в класі ios у виді перерахування enum.
public:
enum io_state{
goodbit, //немає помилки 0Х00
eofbit, //кінець файлу 0Х01
failbit, //остання операція не виконалася 0Х02
badbit, //спроба використання неприпустимої операції 0Х04
hardfail //фатальна помилка 0Х08
};
Прапори, що визначають результат останньої операції з об'єктом ios, містяться в змінній state. Одержати значення цієї змінної можна за допомогою функції int rdstate().
Крім того, перевірити стан потоку можна наступними функціями:
int bad(); 1, якщо badbit чи hardfail
int eof(); 1, якщо eofbit
int fail(); 1, якщо failbit, badbit чи hardfail
int good(); 1, якщо goodbit
Якщо операція >> використовується для нових типів даних, то при її перевантаженні необхідно передбачити відповідні перевірки.
Файловий ввід-вивід
Потоки для роботи з файлами створюються як об'єкти наступних класів:
ofstream – запис у файл;
ifstream – читання з файлу;
fstream – читання/запис.
Для створення потоків маються наступні конструктори.
* fstream();
створює потік, не приєднуючи його ні до якого файлу.
* fstream(const char* name,int mode,int p=filebuf::openprot);
створює потік, приєднує його до файлу з ім'ям name, попередньо відкривши файл, встановлює для нього режим mode і рівень захисту p. Якщо файл не існує, то він створюється. Для mode=ios::out, якщо файл існує, те його розмір буде усічений до нуля.
Прапори режиму визначені в класі ios і мають наступні значення.
in -для читання
out -для запису
ate -індекс потоку поміщений у кінець файлу. Читання більше не припустиме, виведені дані записуються в кінець файлу.
app -потік відкритий для додавання даних у кінець. Незалежно від seekp() дані будуть записуватися в кінець
trunc -усікання існуючого потоку до нуля
nocreate -команда відкриття потоку буде завершена невдало, якщо файл не існує
noreplace -команда відкриття потоку буде завершена невдало, якщо файл існує
binary - потік відкривається для двійкового обміну
Якщо при створенні потоку він не приєднаний до файлу, то приєднати існуючий потік до файлу можна функцією
void open(const char* name,int mode,int p=filebuf::openprot);
Функція
void fstreambase::close();
скидає буфер потоку, від'єднує потік від файлу і закриває файл. Цю функцію необхідно явно викликати при зміні режиму роботи з потоком. Автоматично вона викликається тільки при завершенні програми.
У такий спосіб створити потік і зв'язати його з файлом можна трьома способами:
1.
Створюється об'єкт filebuf
filebuf fbuf;
Об'єкт filebuf зв'язується з пристроєм (файлом)
fbuf.open(“ім'я”,ios::in);
Створюється потік і зв'язується з filebuf
istream stream(&fbuf);
2.
Створюється об'єкт fstream (ifstream, ofstream)
fstream stream;
Відкривається файл, що зв'язується через filebuf з потоком
stream.open(“ім'я”,ios::in);
3.
Створюється об'єкт fstream, одночасно відкривається файл, що зв'язується з потоком
fstream stream(“ім'я”,ios::in);
Порядок виконання роботи.
1.Визначити тип даних (клас) користувача. Визначити і реалізувати в ньому конструктори, деструктор, операції присвоювання, вводу і виводу для стандартних потоків.
2.Написати програму №1 для створення об'єктів класу користувача (вводу вихідної інформації з клавіатури з використанням перевантаженої операції “>>”) і збереження їх у потоці (файлі). Передбачити в програмі вивід повідомлення про кількість збережених об'єктів і про довжину отриманого файлу в байтах.
3.Виконати тестування програми.
4.Реалізувати для висновку в потік свій маніпулятор з параметрами.
5.Написати програму №2 для читання об'єктів з потоку, збереження їх у масиві і перегляду масиву. Для перегляду об'єктів використовувати перевантажену для cout операцію “<<” і свій маніпулятор. Передбачити в програмі вивід повідомлення про кількість прочитаних об'єктів і байтів.
6.Виконати програму для читання з файлу збережених попередньої програмою об'єктів і їх перегляду.
7.Написати програму №3 для додавання об'єктів у потік.
8.Виконати програму, додавши в потік кілька об'єктів і переглянути отриманий файл.
9.Написати програму №4 для видалення об'єктів з файлу.
10.Виконати програму, видаливши з потоку кілька об'єктів і переглянути отриманий файл.
11.Написати програму №5 для коректування (тобто заміни) записів у файлі.
12.Виконати програму і переглянути отриманий файл.
Методичні вказівки.
1.Програми створюється як EasyWin-додаток у Borland C++5.02.
Проект повинний містити 5 цільових вузлів (по числу програм).
2.Як користувальницький тип даних узяти клас з лабораторної роботи №1. Поля класу типу char* замінити на char[ціле].
3.У сукупності програми повинні використовувати всі класи потоків: istream, ostream, fstream, ifstream, ofstream.
4.Також у програмах варто показати всі три способи створення потоку і відкриття файлу (див. вище).
5.Необхідно продемонструвати читання з файлу і запис у файл як за допомогою функцій read/write, так і за допомогою перевантажених операцій >>і <<.
6.Маніпулятор користувача створюється з не менш, ніж із двома параметрами.
7.Визначення класу користувача зберегти в h-файлі.
8.Визначення компонентних функцій класу користувача зберегти в cpp-файлі.
9.Реалізацію маніпулятора зберегти в h-файлі.
Як параметри маніпулятора можна використовувати:
а) ширину поля виводу;
б) точність виводу дійсних чисел:
в) символ - заповнювач:
г) спосіб вирівнювання (до лівої чи правої межі). і т.д.
10.У потік записати не менш 5-ти об'єктів.
11.Після запису об'єктів у файл і перед читанням їх з файлу визначити кількість записаних об'єктів і вивести цю інформацію.
Визначити кількість записаних у файл об'єктів можна в такий спосіб:
а) стати на кінець файлу - функції seekp(),seekg().
б) визначити розмір файлу в байтах - функції tellp(),tellg().
в) визначити кількість записаних об'єктів - розмір файлу поділити на розмір об'єкта.
12.Необхідно тестувати помилки при роботі з файлом. Для цього варто використовувати перевантажені операції operator!(), operator void*() і функції bad(), good().
13.Оскільки у файлі може зберігатися кожна, заздалегідь не відома, кількість об'єктів, для їх збереження в програмі №2 при читанні з файлу використовувати динамічний масив.
14.Варто визначити функцію find(), що приймає значення ключового полю об'єкта і повертає зсув цього об'єкта від початку файлу. Викликати цю функцію перед видаленням/зміною об'єкта у файлі.
15.Для зміни і видалення об'єкта написати функції del()іrepl(), яким передається посилання на потік, зсув від початку файлу змінної чи запису, що видаляється, (результат виклику функціїfind), нове значення змінюваного запису.
Зміст звіту.
1.Титульний лист.
2.Постановка задачі.
3.Визначення класу користувача.
4.Реалізація маніпулятора.
5.Реалізація функцій find(), del()і repl().
6.Пояснення до програм. Для кожної програми вказуються які потокові класи в ній використовуються, як створюються об'єкти потокових класів, як відкриваються файли, яким чином виконується ввід і вивід даних
Лабораторна робота №8
Стандартна бібліотека шаблонів
Мета. Освоїти технологію узагальненого програмування з використанням бібліотеки стандартних шаблонів (STL) мови C++.
Основний зміст роботи.
Написати чотири програми з використанням STL. Перша і друга програми повинні демонструвати роботу з контейнерами STL, третя і четверта — використання алгоритмів STL.
Основні теоретичні відомості.
Стандартна бібліотека шаблонів (STL).
STL забезпечує загально цільові, стандартні класи і функції, що реалізують найбільш популярні і широко використовувані алгоритми і структури даних.
STL будується на основі шаблонів класів і тому вхідні в неї алгоритми і структури застосовуються майже до всіх типів даних.
Склад STL.
Ядро бібліотеки утворять три елементи: контейнери, алгоритми і ітератори.
Контейнери (containers) – це об'єкти, призначені для збереження інших елементів. Наприклад: вектор, лінійний список, множина.
Асоціативні контейнери (associative containers) дозволяють за допомогою ключів одержати швидкий доступ до значень, що зберігаються в них.
У кожному класі-контейнері визначений набір функцій для роботи з ними. Наприклад: список містить функції для вставки, видалення і злиття елементів.
Алгоритми (algorithms) виконують операції над змістом контейнера. Існують алгоритми для ініціалізації, сортування, пошуку, заміни вмісту контейнерів. Багато алгоритмів призначені для роботи з послідовністю (sequence), що являє собою лінійний список елементів всередині контейнера.
Ітератори (iterators) – це об'єкти, що стосовно контейнера відіграють роль покажчиків. Вони дозволяють одержати доступ до вмісту контейнера приблизно так, як покажчики використовуються для доступу до елементів масиву.
З ітераторами можна працювати так само, як з покажчиками. До них можна застосувати операції *, інкремента, декремента. Типом ітератор являється тип iterator, що визначений у різних контейнерах.
Існує п'ять типів ітераторів:
1.Ітератори вводу(input_iterator) підтримують операції рівності, розіменування та інкремента.
==, !=, *i, ++i, i++, *i++
Спеціальним випадком ітератора вводу є istream_iterator.
2.Ітератори виводу(output_iterator) підтримують операції розіменування, припустиме тільки з лівої сторони присвоювання та інкремента.
++i, i++, *i=t, *i++=t
Спеціальним випадком ітератора виводу є ostream_iterator.
3.Односпрямовані літератори(forward_iterator) підтримують всі операції ітераторів вводу/виводу і, крім того, дозволяють без обмеження застосовувати присвоювання:
==, !=, =, *i, ++i, i++, *i++
4.Двохнаправлені літератори(biderectional_iterator) мають усі властивості forward-ітераторів, а також мають додаткову операцію декремента (--i, i--, *i--), що дозволяє їм проходити контейнер в обох напрямках.
5.Ітератори довільного доступу(random_access_iterator) мають усі властивості biderectional-ітераторів, а також підтримують операції порівняння та адресної арифметики, а саме безпосередній доступ за індексом.
i+=n, i+n, i-=n, i-n, i1-i2, i[n], i1<i2, i1<=i2, i1>i2, i1>=i2
У STL також підтримуються зворотні ітератори (reverse iterators). Зворотніми ітераторами можуть бути або двонаправлені ітератори, або ітератори довільного доступу, але минаючі послідовність у зворотному напрямку.
Надодачу до контейнерів, алгоритмів і ітераторів у STL підтримується ще кілька стандартних компонентів. Головними серед них є розподільники пам'яті, предикати і функції порівняння.
У кожного контейнера є визначений для нього розподільник пам'яті (allocator), що керує процесом виділення пам'яті для контейнера.
За замовчуванням розподільником пам'яті є об'єкт класу allocator. Можна визначити власний розподільник.
У деяких алгоритмах і контейнерах використовується функція особливого типу, що називається предикатом. Предикат може бути унарним і бінарним. Значення, що повертається: істина або неправда. Точні умови одержання того чи іншого значення визначаються програмістом. Тип унарних предикатів UnPred, бінарних – BinPred. Тип аргументів відповідає типу об'єктів, що зберігаються в контейнері.
Визначено спеціальний тип бінарного предиката для порівняння двох елементів. Він називається функцією порівняння (comparison function). Функція повертає істину, якщо перший елемент менше другого. Типом функції є тип Comp.
Особливу роль у STL грають об'єкти-функції.
Об'єкти-функції - це екземпляри класу, у якому визначена операція “круглі дужки” (). У ряді випадків зручно замінити функцію на об'єкт - функцію. Коли об'єкт – функція використовується як функцію, то для її виклику використовується operatot().
Приклад 1.
class less{
public:
bool operator()(int x,int y)
{return x<y;}
};
Класи-контейнери.
У STL визначені два типи контейнерів – послідовності й асоціативні контейнери.
Ключова ідеядля стандартних контейнерів полягає в тім, що коли це представляється розумним, вони повинні бути логічно взаємозамінними. Користувач може вибирати між ними, ґрунтуючись на розуміннях ефективності і потреби в спеціалізованих операціях. Наприклад, якщо часто потрібен пошук по ключі. можна скористатися map (асоціативним масивом). З іншого боку, якщо переважають операції, характерні для списків, можна скористатися контейнером list. Якщо додавання і видалення елементів часто виконується в кінці контейнера, варто подумати про використання черги queue, черги з двома кінцями deque, стека stack. За замовчуванням користувач повинний використовувати vector; він реалізований, щоб добре працювати для самого широкого діапазону задач.
Ідея звертання з різними видами контейнерів – і, у загальному випадку, із усіма видами джерел інформації – уніфікованим способом, веде до поняття узагальненого програмування. Для підтримки цієї ідеї STL містить множину узагальнених алгоритмів. Такі алгоритми рятують програміста від необхідності знати подробиці окремих контейнерів.
У STL визначені наступні класи-контейнери(у кутових дужках зазначені заголовні файли, де визначені ці класи):
bitset множину бітів <bitset.h>
vector динамічний масив <vector.h>
list лінійний список <list.h>
deque двостороння черга <deque.h>
stack стек <stack.h>
queue черга <queue.h>
priority_queueчерга з пріоритетом <queue.h>
map асоціативний список для збереження пар ключ/значення, де з кожним ключем зв'язане одне значення <map.h>
m