Варіант 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 - Алгоритми бібліотеки стандартних шаблонів

Алгоритм	Призначення
adjacent_find ()	Виконує пошук суміжних парних елементів у послідовності. Повертає ітератор першої пари.
binary_search ()	Виконує бінарний пошук в упорядкованій послідовності.
copy ()	Копіює послідовність.
copy_backward ()	Аналогічна функції copy(), за винятком того, що переміщає в початок послідовності елементи з її кінця.
count ()	Повертає число елементів в послідовності.
count_if ()	Повертає число елементів в послідовності, що задовольняють деякому предикату.
equal ()	Визначає ідентичність двох діапазонів.
equal_range ()	Повертає діапазон, в який можна вставити елемент, не порушивши при цьому порядок проходження елементів у послідовності.
fill () fill_n ()	Заповнює діапазон заданим значенням.
find ()	Виконує пошук діапазону для значення та повертає перший знайдений елемент.
find_end ()	Виконує пошук діапазону для підпослідовності. Функція повертає ітератор кінця підпослідовності в середині діапазону.
find_first_of ()	Знаходить перший елемент в середині послідовності, парний елементу в середині діапазону.
find_if ()	Виконує пошук діапазону для елемента, для якого певний користувачем унарний предикат повертає істину.
for_earch ()	Призначає функцію діапазону елементів.
generate () generate_n ()	Привласнює елементам у діапазоні значення, що повертаються породжуючою функцією.
includes ()	Визначає, чи включає одна послідовність всі елементи іншої послідовності.
inplace_merge ()	Виконує злиття одного діапазону з іншим. Обидва діапазони повинні бути відсортовані в порядку зростання елементів. Результуюча послідовність сортується.
iter_swap ()	Міняє місцями значення, на які вказують два ітератора, що є аргументами функції.
lexicographical_compare ()	Порівнює дві послідовності за абеткою.
lower_bound ()	Виявляє перше значення в послідовності, що не менше заданого значення.
make_heap ()	Виконує пірамідальне сортування послідовності (піраміда, англійською мовою heap - повне двійкове дерево, що володіє тією властивістю, що значення кожного вузла не менше значення кожного з його дочірніх вузлів).
max ()	Повертає максимальне із двох значень.
max_element ()	Повертає ітератор максимального елемента в середині діапазону.
merge ()	Виконує злиття двох упорядкованих послідовностей, а результат розміщає в третій послідовності.
min ()	Повертає мінімальне із двох значень.
min_element ()	Повертає ітератор мінімального елемента в середині діапазону.
mismatch ()	Виявляє першу розбіжність між елементами у двох послідовностях. Повертає ітератори обох незбіжних елементів.
next_permutation ()	Утворює наступну перестановку (permutation) послідовності.
nth_element ()	Упорядковує послідовність таким чином, щоб всі елементи, менші заданого елемента Е, розташовувалися перед ним, а всі елементи, більші заданого елемента Е, - після нього.
partial_sort ()	Сортує діапазон.
partial_sort_copy ()	Сортує діапазон, а потім копіює стільки елементів, скільки ввійде в результуючу послідовність.
partition ()	Упорядковує послідовність таким чином, щоб всі елементи, для яких предикат повертає істину, розташовувалися перед елементами, для яких предикат повертає “неправду”.
pop_heap ()	Міняє місцями перший і попередній перед останнім елементи, а потім відновлює піраміду.
prev_permutation ()	Утворить попередню перестановку послідовності.
push_heap ()	Розміщує елемент на кінці піраміди.
random_shuffle ()	Безладно перемішує послідовність.
remove () remove_if () remove_copy () remove_copy_if ()	Видаляє елементи із заданого діапазону.
replace () replace_if () replace_copy () replace_copy_if ()	Заміняє елементи в середині діапазону.
reverse () reverse_copy ()	Змінює порядок сортування елементів діапазону на зворотній.
rotate ()	Виконує циклічне переміщення вліво елементів у діапазоні.
rotate_copy ()
search ()	Виконує пошук підпослідовності в середині послідовності.
search_n ()	Виконує пошук послідовності заданого числа однакових елементів.
set_difference ()	Створює послідовність, яка містить ділянки, що розрізняються, двох упорядкованих наборів.
set_intersection ()	Створює послідовність, що містить однакові ділянки двох упорядкованих наборів.
set_symmetric_difference ()	Створює послідовність, що містить симетричні ділянки, що розрізняються, двох упорядкованих наборів.
set_union ()	Створює послідовність, що містить об'єднання (union) двох упорядкованих наборів.
sort ()	Сортує діапазон.
sort_heap ()	Сортує піраміду усередині діапазону.
stable_partition ()	Упорядковує послідовність таким чином, щоб всі елементи, для яких предикат повертає істину, розташовувалися перед елементами, для яких предикат повертає “неправду”. Розбивання на розділи залишається постійним; відносний порядок розташування елементів послідовності не змінюється.
stable_sort ()	Сортує діапазон. Однакові елементи не переставляються.
swap ()	Міняє місцями два значення.
swap_ranges ()	Міняє місцями елементи в діапазоні.
transform ()	Призначає функцію діапазону елементів і зберігає результат у новій послідовності.
unique ()	Видаляє повторювані елементи з діапазону.
unique_copy ()	Виявляє останнє значення в послідовності, що не більше деякого значення.
upper_bound ()