Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Стандартні бібліотеки. Класи, контейнери, ітератори, алгоритми
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Об’єктно-орієнтоване програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 10
з дисципліни: “Об’єктно-орієнтоване програмування”
на тему: “Стандартні бібліотеки. Класи, контейнери, ітератори, алгоритми”
Мета лабораторної роботи
Познайомитися зі стандартними бібліотеками, класами, ітераторами, алгоритмами.
Теоретичні відомості
Стандартна бібліотека шаблонів
Стандартна бібліотека шаблонів (Standard Template Library – STL) входить у стандартну бібліотеку мови C++. Уся бібліотека побудована на шаблонах класів і функцій, що забезпечує можливість уніфікованої роботи з різними типами даних. Використання шаблонів у бібліотеці дозволяє не тільки однаково обробляти вбудовані типи С++, але й працювати з користувацькими типами даних, що не були відомі в момент розробки бібліотеки.
Якщо більш конкретно розглянути склад STL, то в ній можна виділити наступні компоненти:
Контейнери (contaіners) – це класи, призначені для зберігання сукупностей об’єктів (як вбудованих, так і визначених користувачем типів). Найпростіші види контейнерів (статичні і динамічні масиви) вбудовані безпосередньо в мову C++.
Ітератори (іterators) – це абстракція покажчика, тобто об'єкт, що може посилатися на інші об'єкти, що містяться в контейнері. Основні функції ітератора – забезпечення доступу до об'єкта, на який він посилається (розіменування), і перехід від одного елемента контейнера до іншого (ітерація, звідси і назва ітератора). Для вбудованих контейнерів у якості ітераторів використовуються звичайні вказівники. У випадку з більш складними контейнерами ітератори реалізуються у виді класів з набором перевантажених операторів.
Алгоритми (algorіthms) – це функції для маніпулювання об'єктами, що містяться в контейнері. Типові приклади алгоритмів – сортування та пошук. У STL реалізовано порядку 60 алгоритмів, які можна застосовувати до різних контейнерів, у тому числі до масивів, вбудованим у мову C++.
Контейнери
У наступній таблиці приведені основні класи контейнерів бібліотеки STL.
Як уже зазначалось, контейнер призначений для збереження об'єктів. Хоча внутрішня організація контейнерів дуже сильно відрізняється, кожен контейнер зобов'язаний надати строго визначений інтерфейс, через який з ним будуть взаємодіяти алгоритми. Цей інтерфейс забезпечують ітератори. Кожен контейнер зобов'язаний мати відповідний йому ітератор. Важливо підкреслити, що жодні додаткові функції-члени для взаємодії алгоритмів і контейнерів не використовуються. Це зроблено тому, що стандартні алгоритми повинні працювати в тому числі з вбудованими контейнерами мови C++, у яких є ітератори (вказівники), але немає нічого, крім них. Власне тому при написанні власного контейнера реалізація ітератора – необхідний мінімум.
Кожен контейнер реалізує визначений тип ітераторів. При цьому вибирається найбільш функціональний тип ітератора, що може бути ефективно реалізований для даного контейнера. "Ефективно" означає, що швидкість виконання операцій над ітератором не повинна залежати від кількості елементів у контейнері. Наприклад, для вектора реалізується ітератор з довільним доступом, а для списку – двонаправлений. Оскільки швидкість виконання операції [] для списку лінійно залежить від його довжини, ітератор з довільним доступом для списку не реалізується.
Тип контейнера
Клас контейнера
Деректива #include
Послідовні контейнери
(Sequence containers)
vector – масиви
< vector >
deque – двостороння черга
<deque>
lіst – списки
< lіst>
Асоціативні контейнери
(Associative containers)
map, multіmap – карти; це структури, подібні до масиву, але в яких роль "індексу" можуть відігравати не тільки цілі числа, але будь-які упорядковані типи
<map>
set, multіset – множини
<set>
bitset – множини як бітові набори
<bitset>
Адаптори
(Container adaptors)
queue – черги, організовані за принципом FIFO
priority queue – пріоритетні черги
<queue>
stack – стеки, організовані за принципом LIFO
<stack>
Незалежно від фактичної організації контейнера елементи, що зберігаються в ньому, можна розглядати як послідовність. Ітератор першого елемента в цій послідовності повертає функція begіn(), а ітератор елемента, що слідує за останнім – функція end(). Це дуже важливо, тому що всі алгоритми в STL працюють саме з послідовностями, заданими ітераторами початку і кінця. Крім звичайних ітераторів у STL існують зворотні ітератори (reverse іterator). Зворотній ітератор відрізняється тим, що переглядає послідовність елементів у контейнері в зворотному порядку. Іншими словами, операції + і – у нього міняються місцями. Це дозволяє застосовувати алгоритми як до прямої, так і до зворотної послідовності елементів.
Ітератори
Ітератори використовуються для доступу до елементів контейнерів також, як вказівники використовуються для доступу до елементів масивів у С++. Ітератор є "розумним" покажчиком на елемент контейнера. На відміну від звичайного вказівника він пам'ятає повний тип даних на який посилається – з урахуванням типу контейнера, до елемента якого виконується звертання.
Ітератори, як було зазначено, є центральним механізмом, що забезпечує роботу з даними контейнерів. Вони є аналогом покажчиків і уможливлюють циклічний перебір всіх елементів контейнера. Існують різні види ітераторів, оскільки різні алгоритми по-різному звертаються до даних. Кожен клас контейнера може породжувати ітератори, необхідні для роботи притаманних йому алгоритмів.
У залежності від набору підтримуваних операцій розрізняють 5 типів ітераторів, що приведені в наступній таблиці.
Тип ітератора
Доступ
Розіменування
Ітерація
Порівняння
Ітератор виводу (output іterator)
Тільки запис
*
++
Ітератор вводу (іnput іterator)
Тільки читання
*, ->
++
= =, !=
Прямий ітератор (Forward іterator)
Читання і запис
*, ->
++
= =, !=
Двонапрямлений ітератор (bіdіrectіonal іterator)
Читання і запис
*, ->
++, --
= =, !=
Ітератор з довільним доступом
(random-access іterator)
Читання і запис
*, ->, []
++,--, +, -, +=, -=
= =, !=, <,
<=, >, >=
Ітератор з довільним доступом реалізує повний набір операцій, що застосовуються до звичайних вказівників.
Алгоритми
Бібліотека STL надає основні види алгоритмів:
Математичні (розрахунок сум, добутків, генерація випадкових значень)
Пошуку (мінімальне значення, пошук послідовності, підрахунок числа значень)
Сортування
Роботи з послідовностями (об'єднання послідовностей, порівняння, обробки послідовності типовою операцією)
Як уже зазначалось алгоритми призначені для маніпулювання елементами контейнера. Будь-який алгоритм розглядає вміст контейнера як послідовність, що задається ітераторами першого і наступного за останнім елементів. Ітератори забезпечують інтерфейс між контейнерами й алгоритмами, завдяки чому і досягається гнучкість і універсальність бібліотеки STL.
Кожен алгоритм використовує ітератори визначеного типу. Наприклад, алгоритм простого пошуку (fіnd) переглядає елементи підряд, поки потрібний не буде знайдений. Для такої процедури цілком достатньо ітератора вводу. З іншого боку, алгоритм більш швидкого двійкового пошуку (bіnary_search) повинен мати можливість переходити до будь-якого елемента послідовності, і тому вимагає ітератора з довільним доступом. Цілком природно, що замість менш функціонального ітератора можна передати алгоритмові більш функціональний, але не навпаки.
Індивідуальне завдання
Написати програму, яка сортує елементи масиву за спаданням.
Код програми
Stack.h
template <typename Type> class Stack
{
private:
Type *arr;
int i, size;
public:
Stack(int size)
{
this->size = size;
arr = new Type[size];
}
~Stack()
{
delete[] arr;
}
void set(Type value)
{
arr[i++] = value;
}
Type get(int i)
{
return arr[i];
}
void sort()
{
Type temp;
for (int k = 0; k < size; k++)
for (i = 0; i < size - 1; i++)
if (arr[i] < arr[i + 1])
{
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
};
main.cpp
#include <iostream>
#include <conio.h>
#include <time.h>
#include "Stack.h"
using namespace std;
void main()
{
setlocale(LC_ALL, "");
srand(time(NULL));
int n;
cout << "Введiть розмiрнiсть масиву:" << endl;
cin >> n;
cout << endl << "int:" << endl;
Stack <int> ArrInt(n);
for (int i = 0; i < n; i++)
{
ArrInt.set(rand() % 100 - 50);
}
ArrInt.sort();
for (int i = 0; i < n; i++)
{
cout << ArrInt.get(i) << " ";
}
cout << endl << endl << "float:" << endl;
Stack <float> ArrFloat(n);
for (int i = 0; i < n; i++)
{
ArrFloat.set(round((float(rand() % 100 - 50) + float(rand()) / RAND_MAX) * 100) / 100);
}
ArrFloat.sort();
for (int i = 0; i < n; i++)
{
cout << ArrFloat.get(i) << " ";
}
cout << endl;
_getch();
}
Результат виконання програми
/
Висновок
Я познайомився зі стандартними бібліотеками, класами, ітераторами, алгоритмами та написав програму, яка сортує елементи масиву за спаданням.
27.03.2016 19:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора