Варіант 1. Задача “Банківське переведення” (дата, час, № рахунку, розмір рахунку).

Варіант 2. Задача “Студент” (прізвище, вік).

Варіант 3. Задача “Медична картка” (прізвище, вага).

Варіант 4. Задача “Результати хімічного досліду” (float, float).

Варіант 5. Задача “Результати хімічного досліду” (час, кількість речовини).

Варіант 6. Задача “Розклад” (№ рейсу та час відправлення).

Варіант 7. Задача “Успішність” (предмет, оцінка).

Варіант 8. Задача “Мобільний телефон” (час розмови, кількість грошей, № телефону).

Варіант 9. Задача “Кабельне телебачення” (кількість каналів, вартість, назва пакету).

Варіант 10. Задача “Мешканці” (прізвище, № квартири, № телефону).

 

 

Клас, що розробляється, повинен містити методи по обраним полям:

- вставка;

- сортування по полю;

- сумування;

- видалення.

Теоретичні відомості

В останніх версіях стандартних бібліотек, що базуються на стандарті для мови C++, утримується великий і вичерпний набір структур даних і функцій, заснованих на шаблонах Таке розширення стандартних бібліотек називається стандартною бібліотекою шаблонів (Standart Template library, STL). Ці структури даних містять шаблони класів для подання масивів, списків, карт (словників), стеків, черг, черг із пріоритетами та ін. Така стандартизація поліпшує мобільність і надійність програм, дозволяє швидко створювати надійні додатки й підтримувати їх з меншими зусиллями.

Всі класи бібліотеки STL розроблялися для спільного функціонування з більшим набором узагальнених алгоритмів (шаблонів функцій загального виду для маніпулювання контейнерами довільної природи). Такий поділ функцій (контейнери - зберігають дані, алгоритми - ними оперують) дозволило істотно скоротити обсяг бібліотеки, причому в багатьох випадках така реалізація виявляється більше ефективної в порівнянні з реалізаціями, заснованими на повній інкапсуляції даних і операцій.

Розглянемо основні поняття, використовувані в STL.

Приклад 1

#include "iostream.h"#include <vector> int main()

{

vector <int> v; // створення вектора нульовой довжини

int i;

cout <<”\n розмір = ” << v.size() << endl; // заповнення вектора в кінець for(i=0; i<10; i++) v.puch_back(i); cout <<”\n новий розмір = ” << v.size() << endl; for(i=0; i <10; i++) v.puch_back(i); cout <<”\n новий зміст = \n ”; for(i=0; i<10; i++) cout << v[i] << ” ”; cout << endl; //доповнення вектора новими елементами в кінець for(i=0; i<10; i++) v.puch_back(i + 10); cout <<”\n новий розмір = ” << v.size() << endl; cout <<”\n поточний зміст = \n ”; for(i=0; i< v.size(); i++) cout << v[i] << ” ”; cout << endl; // зміна значень вектора for(i=0; i< v.size(); i++) v[i] = v[i]+ v[i]; cout <<”\n новий вектор: \n”; for(i=0; i< v.size(); i++) cout << v[i] << ” ”; cout << endl; return 0;

}

Тестування:

розмір =0новий розмір =10новий зміст =0 1 2 3 4 5 6 7 8 9новий розмір =20поточний зміст =0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19новий вектор:0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38

 

У бібліотеці виділяють три основних компонентів:

1. Контейнер (container) - зберігання набору об'єктів в пам'яті.

2. Ітератор (iterator) - забезпечення засобів доступу до вмісту контейнера.

3. Алгоритм (algorithm) - визначення обчислювальної процедури.

До контейнерів відносять:

- vector - колекція елементів Т, збережених в масиві, збільшується в міру необхідності. Для того, щоб почати використання даної колекції, увімкніть # include <vector>.

- list - колекція елементів Т, збережених, як двонаправлений зв'язаний список. Для того, щоб почати використання даної колекції, увімкніть # include <list>.

- map - це колекція, яка зберігає пари значень pair <const Key, T>. Ця колекція призначена для швидкого пошуку значення T по ключу const Key. В якості ключа може бути використано все, що завгодно, наприклад, рядок або int але при цьому необхідно пам'ятати, що головною особливістю ключа є можливість застосувати до нього операцію порівняння. Швидкий пошук значення по ключу здійснюється завдяки тому, що пари зберігаються в відсортованому вигляді. Ця колекція має відповідно і недолік - швидкість вставки нової пари назад пропорційна кількості елементів, збережених в колекції, оскільки просто додати нове значення в кінець колекції не вийде. Ще одна важлива річ, яку необхідно пам'ятати при використанні даної колекції - ключ повинен бути унікальним. Для того, щоб почати використання даної колекції, увімкніть # include <map>. Якщо ви хочете використовувати дану колекцію, щоб уникнути дублікатів, то ви уникнете їх тільки по ключу.

- set - це колекція унікальних значень const Key - кожне з яких є також і ключем - тобто, простіше кажучи, це відсортована колекція, призначена для швидкого пошуку необхідного значення. До ключу пред'являються ті ж вимоги, що й у випадку ключа для map. Природно, використовувати її для цієї мети немає сенсу, якщо ви хочете зберегти в ній прості типи даних, щонайменше вам необхідно визначити свій клас, який зберігає пару ключ - значення і визначає операцію порівняння по ключу. Дуже зручно використовувати дану колекцію, якщо ви хочете уникнути повторного збереження одного і того ж значення. Для того, щоб почати використання даної колекції, увімкніть # include <set>.

- multimap - це модифікований map, в якому відсутня вимоги унікальності ключа - тобто, якщо ви справите пошук по ключу, то вам повернеться не одне значення, а набір значень, збережених з даним ключем. Для того, щоб почати використання даної колекції увімкніть # include <map>.

- multiset - те ж саме відноситься і до цієї колекції, вимоги унікальності ключа в ній не існує, що призводить до можливості зберігання дублікатів значень. Тим не менш, існує можливість швидкого знаходження значень по ключу у випадку, якщо ви визначили свій клас. Оскільки всі значення в map і set зберігаються в відсортованому вигляді, то виходить, що в цих колекціях ми можемо дуже швидко відшукати необхідне нам значення по ключу, але при цьому операція вставки нового елемента T буде коштувати нам дещо дорожче, ніж наприклад в vector. Для того, щоб почати використання даної колекції, увімкніть # include <set>.

Ітератори

Одним з найважлівішіх елементів бібліотеки, поряд з контейнером и узагальнення алгоритмом - ітератор.

Ітератор являє собою клас, що забезпечує доступ до даніх іншого класу, тобто ітератор узагальнює поняття покажчика: він надає доступ до елементів контейнера без необхідності інкапсулювати контейнер. Аналогічно тому, як використовуються звичайні покажчики, ітератори можуть використовуватися для різних цілей. Ітератор може вказувати на конкретній об'єкт, пари ітераторів визначає діапазон об'єктів у послідовності (початок - кінець). При чому елементи послідовності випливають один за одним у логічній послідовності (у фізічній пам'яті вони розташовуються не обов'язково послідовно). Фізична реалізація порядку вибірки елементів з послідовності покладає на контейнери.

Внутрішній устрій ітератора може виглядати так:

class Iterator

{

T * pointer;

public:

T * GetPointer ()

{

return this -> pointer;

}

void SetPointer (T * pointer)

{

this -> pointer = pointer;

}

:

};

У STL існує три типи итераторов: iterator, reverse_iterator, і random access iterator. Для обходу колекції від меншого індексу до більшого, використовуються звичайні або forward ітератори. Для обходу колекції у зворотному напрямку використовуються reverse ітератори. Random access iterator є ітераторами, які можуть обходити колекцію як вперед, так і назад. Нижче наведено приклад використання итераторов для видалення половини елементів вектора:

# Include "stdafx.h"

# Include <iostream>

# Include <vector>

# Include <algorithm>

using namespace std;

void printInt (int number);

int _main (int argc, _TCHAR * argv [])

{

vector <int> myVec;

vector <int>:: iterator first, last;

for (long i = 0; i <10; i + +)

{

myVec.push_back (i);

}

first = myVec.begin ();

last = myVec.begin () + 5;

if (last> = myVec.end ())

{

return - 1;

}

myVec.erase (first, last);

for_each (myVec.begin (), myVec.end (), printInt);

return 0;

}

void printInt (int number)

{

cout << number << endl;

}

Важливо пам'ятати, що коли ви отримуєте ітератор до колекції, а після цього вносите колекцію, то цей ітератор стає вже непридатним до використання. Природно, не всі зміни призводять до непридатності ітератора для подальшого використання, а тільки зміни структури колекції. У разі ж, якщо ви просто зміните значення, збережені в колекції, то нічого страшного не станеться і ітератор не зіпсується.

Ітерація по колекції вперед відбувається так:

for (iterator element = begin (); element <end (); element + +)

{

t = (* element);

}

Ітерація по колекції назад відбувається так:

for (reverse_iterator element = rbegin (); element <rend ();

element + +)

{ t = (* element); }

Якщо ви працюєте і з random access iterator ітератором, то синтаксис конструкції може бути, наприклад, таким:

for (iterator element = begin (); element <end ();

element + = 2)

{

t = (* element);

}

Для більш ефективного використання контейнерів використовуйте typedef або наслідуйте свій клас від класу колекції.

Зробити це можна так:

typedef vector <int> myVector

typedef map <string, int> myMap

typedef deque <string> myQue

Або ось така техніка в разі спадкування:

class myVector: public vector <int> {};

У випадку з ітератором застосовна попередня техніка:

typedef myVector:: iterator vectorIterator

typedef myVector:: reverse_iterator revVectorIterator

Для роботи з вектором необхідно:

1. Підключити заголовний файл

# Include "vector"

2. Оголосити робочу область:

using namespace std;

3. Оголосити вектор:

це можна зробити двома способами.

vector <int> vArray1;

vector <int> vArray2 (30);

У першому випадку вказується порожній вектор, а в другому початковий розмір.

4. Ініціалізація вектора

vector vVec (5,10);

for (int x = 0; x <5; x + +)

cout << vVec [x] << endl;

Для отримання інформацію про параметри вектора:

* Size () - скільки даних зберігатися

* Capacity () - скільки може зберігатися до зміни розміру

* Max_size () - максимальний розмір звичайно дорівнює найбільш великим доступному блоку пам'яті

Приклад роботи з вектором

1. Заповнити частину вектора необхідними даними.

У даному прикладі перші три елементи заповнюються цифрою два:

vVec.assign (3,2);

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

cout << vVec [x] << endl;

2. Отримати перший і останній елемент вектора, для цього є функції front () і back ().

vVec.assign (5,1);

vVec [0] = 0;

vVec [4] = 4;

cout << vVec.front () << "" << vVec.back () << endl;

3. Вставку елемента з переміщенням можна зробити функцією insert. Вставка проводиться в першу позицію з переміщенням елементів вниз.

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

cout << vVec [x] << "";

cout << endl;

vVec.insert (vVec.begin (), 25);

for (x = 0; x <6; x + +)

cout << vVec [x] << "";

cout << endl;

4.Поместіть число в кінець вектора скориставшись функцією push_back ():

vVec.push_back (99);

for (x = 0; x <7; x + +)

cout << vVec [x] << "";

cout << endl;

5. Видалити останній елемент зі скороченням розміру:

vVec.pop_back ();

for (x = 0; x <vVec.size (); x + +)

cout << vVec [x] << "";

cout << endl;

 

6. Для видалення используеться функція erase ():

vVec.erase (vVec.begin () +2, vVec.begin () +4);

for (x = 0; x <vVec.size (); x + +)

cout << vVec [x] << "";

cout << endl;

7. Для зміни розміру вектора используеться функція resize ():

vVec.resize (3);

for (x = 0; x <vVec.size (); x + +)

cout << vVec [x] << "";

cout << endl;

8. Заповнення масиву:

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

v.puch_back (rand ()); v.puch_back (rand ()% 10);

9.Вставка елемента:

cout << "\ n Enter pos_ins"; cin >> pos_ins;

vector <char>:: iterator ch_p = ch.begin ();

ch_p = ch_p + pos_ins;

cout << "\ n Enter new_elem ="; cin >> new_elem;

if (pos_ins> = 0 && pos_ins <= ch.size ())

{Ch.insert (ch_p, 1, new_elem);}

10.Видалення елемента:

cout << "\ n Enter pos_ins"; cin >> pos_ins;

cout << "\ n size =" << ch.size ();

if (pos_ins> = 0 && pos_ins <= ch.size ())

{Ch.erase (ch.begin () + pos_ins, ch.begin () + pos_ins + 1)

Алгоритми

До цього ми подивилися основні прийоми використання STL колекцій на прикладі використання вектора. Це основа STL, але для того, щоб по - справжньому використовувати всю міць цієї бібліотеки, доведеться розширити наші знання. З використанням алгоритмів можливе створення дуже потужних і ефективних програм. За компактності такий код перевершує код, написаний на таких сучасних мовах, як Java і С #, і в значній мірі ефективніше останнього.

STL - алгоритми представляють набір готових функцій, які можуть бути застосовані до STL колекціям і можуть бути поділені на три основних групи (табл.11.1).

Таблиця 11.1 - Алгоритми бібліотеки стандартних шаблонів