Во сите примери и програми кои ќе ги пишуваме во продолжение, ќе користиме делови од т.н. Стандардна библиотека на шаблони во C++. Оваа исклучително популарна библиотека се користи насекаде, и е една од причините поради која C++ е толку популарен јазик. Всушност, доколку некој човек се појави пред вас, извади лист хартија и ве праша "Дечко/Девојко, сакаш да видиш една C++ програма?", програмата што ќе ви ја покаже, со голема сигурност, ќе содржи делови од Стандардната библиотека на шаблони - STL.

Во претходното предавање, разгледавме неколку податочни структури кои често се користат при решавање на разни проблеми. Тука, ќе разгледаме како овие податочни структури се користат во програмскиот јазик C++. Бидејќи, како дел од Стандардната библиотека на шаблони, овие структури се веќе имплементирани, вие нема потреба истите да ги пишувате. Така, и во иднина, главниот проблем во однос на податочните структури, ќе биде да препознаеме која структура е најсоодветна за решавање на одреден проблем, и истата да ја примениме. Самата имплементација е веќе направена за нас – како во програмскиот јазик C++ (преку Стандардната библиотека на шаблони), така и во другите посовремени програмски јазици (како Јава, Python, итн.)

Ова предавање ќе биде малку покомплицирано од останатите, но од истото ќе научите многу корисни работи за програмскиот јазик C++. Имањето на добра основа во знаењето на податочни структури ќе ве направи многу подобар програмер. Почнувајќи од наредните предавања, ќе разгледуваме вистински проблеми и техники за нивно решавање - меѓутоа важно е, пред да почнеме со тоа, да знаеме како да ги искористиме податочните структури кои ги споменавме претходно. Па, да почнеме.

Низа со динамичка големина

Како што беше наведено во претходното предавање, податочната структура која што најчесто ќе ја користиме при решавање на проблеми е низата со динамичка големина. Во Стандардната библиотека на шаблони, оваа структура може да ја најдеме под името vector<>, и за создавање на истата е потребно, покрај типот на податок кој ќе се чува, да наведеме и име. На пример, со следната наредба, создаваме низа со динамичка големина под името numbers, која ќе чува податоци од тип int.

vector<int> numbers;

За користење на vector<>, потребно е, на почетокот на нашите програми, да ја додадеме наредбата #include <vector>. За пристап до одреден елемент, го користиме истиот принцип како и кај низите (numbers[0] за првиот елемент, numbers[1] за вториот, итн). За додавање на нов елемент, ја користиме функцијата push_back(), а доколку не интересира колку елементи се додадени досега, функцијата size(). Тоа се сите основни операции кои ќе ги користиме кај низите со динамичка големина. Сите тие се извршуваат во константно време O(1).

Во продолжение е дадена програма која што ги користи сите операции и функции споменати погоре. Запаметете, кај vector<>, нема потреба, при создавањето на истиот, однапред да ја дефинираме неговата големина - како кај низите. Напротив, ова се прави за нас од страна на самиот програмски јазик.

Забелешка: Оваа програма, како и сите останати кои ќе ги пишуваме во иднина, можете да ја извршувате и на вашиот компјутер, како и да експериментирате со истата - што претставува одличен начин за да научите повеќе за материјалот кој го изучувате.

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


int main()
{
     vector<int> numbers;
     
     do
     {
          int N;
          cin >> N;
          
          if (N > 0) 
          {
               numbers.push_back(N);
          }
          else 
          {
               break;
          }
     }
     while (true);
     
     cout << numbers[0] << endl;
     cout << numbers.size() << endl;
     
     return 0;
}

Самата програма дадена погоре, од стандарден влез, чита листа од неколку цели броеви, се додека корисникот не внесе број кој што е помал или еднаков на 0. Кога корисникот ќе внесе таков број, со користење на break, програмата излегува од циклусот, и потоа го печати првиот прочитан број (првиот број во низата со динамичка големина е numbers[0]), а потоа и вкупниот број на елементи во низата со numbers.size().

Ред

Во Стандардната библиотека на шаблони, можеме директно да ја користиме и податочната структура ред, која се наоѓа под името queue<>; и, за чие создавање, слично како и кај низите со динамичка големина, потребно е покрај типот на податоци кои ќе се чуваат во редот, да се наведе и името. За користење на ред, важно е, на почетокот на програмата, да ја додадеме и наредбата #include <queue>.

Кај queue<>, најчесто ќе ги користиме следните неколку операции: size() за добивање на бројот на елементи кои моментно се наоѓаат во редот, push() за додавање на нов елемент во редот, front() за добивање на следниот елемент за процесирање (кај редовите, важи принципот “прв влегува, прв излегува”, па ова е всушност елементот кој е внесен најрано, а сеуште не е изваден од редот), и pop() за вадење на елемент од редот (и тоа првиот кој сеуште не е изваден). Сите операции се изведуваат во константно време O(1).

За да стане појасно, да ја разгледаме следната програма:

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


int main()
{
     queue<int> numbers;
     numbers.push(3);
     numbers.push(5);
     
     cout << numbers.front() << endl;   //3
     cout << numbers.front() << endl;   //3
     numbers.pop();
     
     cout << numbers.front() << endl;   //5
     numbers.pop();
     
     numbers.push(10);
     numbers.push(30);
     
     cout << numbers.front() << endl;   //10
     cout << numbers.size() << endl;    //2
     return 0;
}

Како коментари во изворниот код (со //), наведен е излезот од програмата – т.е., што ќе биде излез кај секоја од наредбите за печатење. Забележете дека со front() само го добиваме следниот елемент, а дека е потребно да се повика pop() за тој елемент и да го извадиме од редот. Како паралела со примерот за ред наведен во претходното предавање, front() е функцијата која би кажувала кое лице треба следно да дојде до шалтерот, додека pop() известува дека тоа лице веќе ја завршило потребната работа, и дека треба да се прејде на следниот кој чека во редот.

Стек

Во предавањето за податочните структури, наведовме дека стек не се користи директно, туку најчесто се користи рекурзија или некоја друга структура за решавање на истите проблеми. Сепак, бидејќи истата е веќе имплементирана во Стандардната библиотека на шаблони, тука ќе наведеме како оваа податочна структура може да се користи, со цел предавањето да е комплетно.

Стек се користи на многу сличен начин како ред, со тоа што наместо queue<> ќе користиме stack<>. Нормално, слично како и за другите структури, потребно е, на почетокот на програмата, да ја додадеме наредбата #include <stack>.

Кај стек, најчесто ќе ги користиме истите неколку операции како и кај редовите: size() за добивање на бројот на елементи кои моментно се наоѓаат во стекот, push() за додавање на нов елемент во стекот, како и pop() за вадење на елемент од стекот (и тоа најгорниот елемент кој сеуште не е изваден). Единствената разлика помеѓу ред и стек е дека, кај стек, ќе користиме top() за добивање на следниот елемент за процесирање (бидејќи, кај стековите, важи принципот “прв влегува, последен излегува”, па всушност од интерес ни е елементот кој е внесен најдоцна, а сеуште не е изваден од стекот). Исклучително е лесно да се запамети од каде доаѓа името на функцијата top(), доколку се потсетиме на примерот со чиниите од претходното предавање - чиниите кои се додадени последни се наоѓаат на врвот. Кога ни треба чинија, земаме од врвот. Сите споменати операции, слично како и кај низите со динамичка големина и редовите, се изведуваат во константно време O(1).

Во продолжение е дадена и програма која го илустрира она што беше наведено погоре:

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


int main()
{
     stack<int> numbers;
     numbers.push(3);
     numbers.push(5);
     
     cout << numbers.top() << endl;     //5
     numbers.pop();
     
     cout << numbers.top() << endl;     //3
     numbers.pop();
     
     cout << numbers.size() << endl;    //0
     return 0;
}

Како коментари во изворниот код (со //), наведен е излезот од програмата – т.е., што ќе биде излез кај секоја од наредбите за печатење.

Поврзана листа

При пишувањето на програми, нема често да работиме со поврзани листи директно. Сепак, важно е да наведеме дека тие се веќе имплементирани во програмскиот јазик C++ под името list, и дека истите може да се користат доколку додадеме #include <list> на почетокот на нашите програми. Тука, важат слични операции како и кај низите со динамичка големина. Но, за разлика од нив, не можеме ефикасно (во константно време) да пристапиме на елемент на произволна позиција. Затоа пак, можеме ефикасно да додадеме елемент на почеток, или во средина на листата.

Поконкретно, сите овие операции имаат константна сложеност O(1), и истите можете да ги користите едноставно: size() за добивање на бројот на елементи, push_back() за додавање на елемент на крајот, push_front() за додавање на елемент на почетокот, front() за добивање на елементот кој се наоѓа на почетокот на листата, back() за добивање на елементот кој се наоѓа на крајот на листата, pop_front() за вадење на почетниот елемент и pop_back() за вадење на крајниот елемент.

Множества и мапи

Бинарните дрва се исклучително корисни за чување на разни типови на податоци, како и за решавање на разни проблеми кои се среќаваат при програмирањето. Во Стандардната библиотека на шаблони, има повеќе начини за користење на истите. Во овој дел, ќе се запознаеме со множества и мапи. Истите, поради нивната ефикасност и корисност, ќе ги среќаваме кај повеќе алгоритми и проблеми. Поради тоа, од исклучителна важност е да знаеме како тие функционираат.

Во Стандардната библиотека на шаблони, множествата се среќаваат под името set<>, а за нивно создавање, слично како и кај низите, редовите и стековите, потребно е да го наведеме типот на податоци кои ќе се чуваат. За користење на множества, потребно е на почетокот на програмата да додадеме #include <set>.

Кај едно множество, можеме да додаваме елементи (со insert()), да бришеме елементи (со erase()), како и ефикасно да провериме дали еден елемент се наоѓа во множеството или не (со find() или count()). По правило, во множеството не се чуваат дупликати - доколку се обидеме да додадеме одредена вредност повеќе пати, таа ќе се додаде само еднаш. Сите споменати операции имаат логаритамска сложеност O(logN).

Во константно време, слично како и кај другите структури, со користење на операцијата size(), можеме да видиме колку елементи се наоѓаат во множеството.

Па, да разгледаме една програма која користи множества. Во продолжение, дадена е програма кај која внесуваме неколку цели броеви во множество, но и бришеме дел од нив. Забележете како, иако повеќе пати внесуваме одредена вредност, кај множествата истите се чуваат само еднаш. Поради тоа, еден од начините на кои се користи set<> е и за броење на уникатни вредности со користење на функцијата size().

#include <iostream>
#include <set>
#include <string>
using namespace std;


int main()
{
     set<string> names;
     names.insert("bojan");
     names.insert("darko");
     names.insert("nikola");
     
     names.insert("darko");
     names.insert("darko");
     
     cout << names.size() << endl;           //3
     cout << names.count("bojan") << endl;   //1
     cout << names.count("darko") << endl;   //1
     
     names.erase("darko");
     names.erase("nikola");
     
     cout << names.size() << endl;           //1
     return 0;
}

Покрај множества, во Стандардната библиотека на шаблони, со помош на бинарни дрва, се имплементирани и мапи. Кај мапите, можеме да чуваме разни вредности под разни имиња (точниот термин е клуч, наместо име). Мапите можете да ги познаете по тоа што истите вршат слична функција како и низите - со таа разлика што, кај низите користиме броеви за пристап до елементите (array[0], array[1], итн), додека кај мапите тоа може да бидат и клучеви од друг тип (на пример, count["bojan"], numbers[0], итн). Дополнително, кога ги дефинираме низите, одбираме и максимална големина за нив (на пример, 10000 елементи), па клучевите можат да бидат броеви помеѓу 0 и 9999. Кај мапите, кога клучевите претставуваат цели броеви, немаме такви ограничувања и може да користиме и многу поголеми броеви, како и да користиме негативни броеви како -12345, итн.

Бидејќи, во позадина, мапите користат бинарни дрва за чување на елементите, временската сложеност за пристап до одреден елемент е O(logN). За разлика од ова, сложеноста кај низите беше O(1).

За создавање на мапа, користиме map<> и, се разбира, на почетокот на програмата, додаваме #include <map>. При дефинирањето на самата мапа, покрај името на променливата, потребно е да ги наведеме и податочниот тип на клучевите, како и податочниот тип на вредностите. На пример, со следната наредба дефинираме мапа каде клучевите ќе бидат од тип string, додека вредностите ќе бидат од тип int (цели броеви). Името на променливата е values.

map<string, int> values;

Да разгледаме пример за користење на мапа. Во следната програма, најпрвин читаме еден цел број N, а потоа и N имиња. Со помош на мапа, ќе броиме колку пати се појавува секое име досега, и тоа ќе го отпечатиме на стандарден излез (екран).

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


int main()
{
     map<string, int> occurrences;
     
     int N;
     cin >> N;
     
     for(int i=0; i<N; i++)
     {
          string name;
          cin >> name;
          
          occurrences[name] = occurrences[name] + 1;
          cout << name << " appears for the "
               << occurrences[name] << " time." << endl;
     }
     
     cout << "There are a total of " << occurrences.size()
          << " different names read." << endl;
     return 0;
}

Пар од вредности

При програмирањето, често сакаме, наместо една вредност, да чуваме најмалку две. На пример, сакаме да користиме име и презиме (и нив да ги третираме како еден податок – пар), x и y координати на некоја точка, итн. Но, кај сите примери на користење на Стандардната библиотека на шаблони што ги видовме погоре, забележуваме дека можеме да додаваме само по една вредност.

Кога сакаме да чуваме две вредности заедно, тоа можеме да го направиме користејќи pair<>. Притоа, двете вредности кои ќе ги чуваме не мора да бидат од ист тип. Поконкретно, сите примери на создавање на пар од вредности дадени во продолжение се валидни, и може да се користат:

pair<int, int> coordinates;
pair<int, string> priority;
pair<string, string> names;

За создавање на нов пар, ја користиме функцијата make_pair(). На пример, make_pair(3, 5), make_pair(5, “bojan”), итн. Кога веќе имаме пар од вредности, до самите вредности можеме да пристапиме користејќи first (за првата вредност), и second (за втората). Да го разгледаме следниот пример:

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


int main()
{
     vector<pair<int, int> > coordinates;
     
     pair<int, int> point1;
     point1 = make_pair(10, 10);
     coordinates.push_back(point1);
     
     coordinates.push_back(make_pair(1, 2));
     coordinates.push_back(make_pair(0, 0));
     
     for(int i=0; i < coordinates.size(); i++)
     {
          pair<int, int> point = coordinates[i];
          cout << point.first << " " << point.second << endl;
     }
     
     return 0;
}

Доколку не забележавте, кај програмата дадена погоре, при создавањето на низата со динамичка големина coordinates, оставивме едно празно место помеѓу двата знака > (каде што завршува дефинирањето на типот на податоци за парот, и она за низата). Внимавајте, при пишувањето на програми во иднина, да не заборавите да го направите истото – во спротивно, кај некои верзии на програмскиот јазик C++, тоа може да го збуни системот (бидејќи веќе постои оператор >>, со сосема друго значење), и да добиете грешка. Затоа, секогаш оставајте празно место помеѓу двата знака >.

Приоритетен ред

Во претходното предавање, наведовме дека често е потребна и податочна структура каде елементите ќе бидат разгледувани по редослед кој зависи од одредена вредност за приоритет. На пример, лекар во некоја установа треба да ги прегледа пациентите кои имаат проблем со дишење пред оние со мала главоболка - иако, можеби, тој со главоболка дошол во болницата прв. Во Стандардната библиотека на шаблони, за оваа намена имаме priority_queue<>, а, за создавање на приоритетен ред, слично како и кај низите со динамичка големина, редовите, стековите и множествата, потребно е покрај типот на податоци кои ќе се чуваат во приоритетниот ред, да се наведе и името. На почетокот на програмата, ја додаваме наредбата #include <queue>.

Кај priority_queue<>, најчесто ќе ги користиме следните неколку операции: size() за добивање на бројот на елементи кои моментно се наоѓаат во приоритетниот ред, push() за додавање на нов елемент во редот, top() за добивање на следниот елемент за процесирање (првиот по приоритет), и pop() за вадење на елемент од редот (првиот по приоритет). Додавање и бришење на елементи од приоритетен ред се извршува со логаритамска сложеност O(logN), додека операцијата за добивање на број на елементи size() во константно време O(1).

Да ја разгледаме следната програма.

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


int main()
{
     priority_queue<int> pq;
     
     pq.push(3);
     pq.push(1);
     pq.push(5);
     
     cout << pq.top() << endl;   //5
     pq.pop();
     
     cout << pq.top() << endl;   //3
     pq.pop();
     
     cout << pq.top() << endl;   //1
     pq.pop();
     
     
     pq.push(10);
     cout << pq.size() << endl;  //1
     return 0;
}

Забележете дека, кај приоритетен ред, најпрво ги добиваме вредностите кои се најголеми (на пример, во програмата погоре, 5 има најголем приоритет, па 3, па 1). Но, во одредени ситуации, го сакаме обратното - прво да ги разгледуваме најмалите броеви (на пример, ова е случај кај алгоритмите за пронаоѓање на најкраток пат помеѓу две локации, кои ќе ги разгледаме во иднина). Во таков случај, наједноставното решение е покрај самиот елемент, со помош на пар, да дефинираме и вредност за приоритет. Во Стандардната библиотека на шаблони, кога имаме споредба на два пара од броеви, најпрво се споредува првата вредност (first), па втората (second). Поради тоа, можеме во приоритетниот ред, како прва вредност да ставиме било кој број (кој ќе означува приоритет), а како втора вредност да биде самиот елемент (со кој ќе работиме).

Во конкретниот случај, за да ги добиеме елементите во обратен редослед, можеме како приоритет да ја ставиме обратната вредност од бројот (бројот помножен со -1). Да ја разгледаме следната програма. Забележете дека оваа програма работи на истиот начин како и претходната, но ги печати броевите во обратен редослед (од најмал до најголем).

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


int main()
{
     priority_queue<pair<int, int> > pq;
     
     pq.push(make_pair(-3, 3));
     pq.push(make_pair(-1, 1));
     pq.push(make_pair(-5, 5));
     
     cout << pq.top().second << endl;   //1
     pq.pop();
     
     cout << pq.top().second << endl;   //3
     pq.pop();
     
     cout << pq.top().second << endl;   //5
     pq.pop();
     
     
     pq.push(make_pair(-10, 10));
     cout << pq.size() << endl;         //1
     return 0;
}

Како уште едно подобрување (трик), забележете дека, кога се работи за цели или реални броеви, нема ни потреба да правиме пар од вредности, туку можеме само да ја ставиме обратната вредност од бројот (бројот помножен со -1), а при вадењето на елементот, да го помножиме истиот со -1 уште еднаш, со што би ја добиле оригиналната вредност. Бидејќи, додека се елементите во приоритетниот ред, истите се помножени со -1, тогаш системот ќе ги гледа во обратен редослед, со што сме ја постигнале целта која си ја зададовме на почеток.

Корисни алгоритми

Покрај чувањето на елементи во податочни структури, Стандардната библиотека на шаблони нуди и голем број алгоритми кои може да се применуваат врз податоци. За да ги користиме овие алгоритми, на почеток на програмата треба да додадеме #include <algorithm>.

Бидејќи постојат огромен број на алгоритми, тука нема да ги разгледаме сите. Сепак, ќе ги разгледаме оние кои навистина ќе ви требаат, и ќе ги користите најчесто. Тоа се алгоритмите за подредување на елементи, замена на два елементи, превртување на елементите во обратен редослед, пронаоѓање на најголема вредност и пронаоѓање на најмала вредност. Притоа, Стандардната библиотека на шаблони ги користи функциите begin() и end() за означување на опсегот во кој ги вршиме операциите. На пример, за низа со динамичка големина numbers, опсегот на сите елементи во оваа низа е опсегот помеѓу numbers.begin() и numbers.end(). Забележете и дека, овие алгоритми ќе ги користиме само на низи со динамичка големина, бидејќи дел од нив и немаат свое значење кај другите податочни структури (на пример, не може да се превртат елементите кај едно множество и слично).

Па, да ги разгледаме конечно алгоритмите. Притоа, претпоставуваме дека веќе имаме создадено низа со динамичка големина со име numbers.

Навистина едноставно. Да напишеме и кратка програма која ќе го илустрира ова:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
     vector<int> numbers;
     
     numbers.push_back(3);  //numbers = [3]
     numbers.push_back(1);  //numbers = [3, 1]
     numbers.push_back(5);  //numbers = [3, 1, 5]
     numbers.push_back(7);  //numbers = [3, 1, 5, 7]
     
     sort(numbers.begin(), numbers.end());      //numbers = [1, 3, 5, 7]
     reverse(numbers.begin(), numbers.end());   //numbers = [7, 5, 3, 1]
     
     swap(numbers[0], numbers[1]);              //numbers = [5, 7, 3, 1]
     
     cout << numbers[0] << endl;   //5
     return 0;
}

Конечно, дојдовме до крајот на ова предавање, во кое се запознавме со Стандардната библиотека на шаблони, но и како да ги користиме сите позначајни податочни структури кои беа наведени во претходното предавање. Ова знаење многу ќе ни помогне при изучувањето на разните техники и алгоритми кои ќе ги разгледаме во продолжение.

Дозвола за користење: CC BY-NC 2.5 ©