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

Пред да ги разгледаме најчесто користените алгоритми, да напоменеме дека во сите функции кои очекуваат опсег од податоци (на пример, sort(pocetok, kraj)), алгоритамот се извршува врз податоците кои се наоѓаат во интервалот [pocetok, kraj), односно врз сите податоци од итераторот pocetok до итераторот kraj - но не вклучувајќи го тука и kraj.

Важно е да напоменеме дека временските сложености дадени во табелата се однесуваат на бројот на елементи кои се споредуваат (тоа е всушност сложеноста на алгоритамот за едноставни податочни типови - int, float, double, char, итн). Но, доколку работиме со контејнери кои содржат повеќе елементи, тогаш сложеноста се множи со бројот на елементи во соодветните контејнери. На пример, функцијата min(x, y) има константна сложеност О(1) бидејќи е потребно да се споредат вредностите на само 2 елемента (x и y). Но, доколку тие елементи се текстуални низи, за да се одговори кој од нив е лексикографски помал (споредба знак по знак - како во телефонски именик), тогаш е потребно да се споредат О(N) елементи (во случајов, знаци).

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

int main()
{
      int a = min(3, 5);                                      //a=3
      int b = max(3, 5);                                      //b=5
      
      vector<int> v;
      
      for (int i=0; i<10; i++)
      {
            v.push_back((i*i*i)%10);
      }

      //v={0, 1, 8, 7, 4, 5, 6, 3, 2, 9}
      
      //min_element i max_element vrakjaat iteratori
      //shto znaci deka treba da napravime *(it) za da ja
      //dobieme vrednosta na najmaliot/najgolemiot element
      int c = *(min_element(v.begin(), v.end()));             //c='0'
      int d = *(max_element(v.begin(), v.end()));             //d='9'
      
      v.push_back(3);
      //v={0, 1, 8, 7, 4, 5, 6, 3, 2, 9, 3}
      
      int e = count(v.begin(), v.end(), 3);                   //e='2'
      
      vector<int>::iterator f;
      f = find(v.begin(), v.end(), 5);                        //*f = 5
      
      v.clear();
      for (int i=1; i<=3; i++)
            v.push_back(1);                                   //v={1, 2, 3}
      
      vector<int> v2 = v;                                     //v2={1, 2, 3}
      
      if (equal(v.begin(), v.end(), v2.begin()))              //true
            cout << "ednakvi" << endl;                        //pechati 'ednakvi'
      
      return 0;
}

Секое подредување на опсег од вредности се нарекува негова пермутација. На пример, пермутации на листата {1, 2, 3} се: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} и {3, 2, 1} - подредени според првиот елемент, па според вториот, па според третиот. Алгоритамот next_permutation(pocetok, kraj) ги прераспоредува вредностите во интервалот [pocetok, kraj) во нивната следна пермутација - на пример, опсегот {1, 3, 2} ќе се промени во {2, 1, 3}. Од друга страна, алгоритамот prev_permutation(pocetok, kraj) ги прераспоредува вредностите во интервалот [pocetok, kraj) во нивната претходна пермутација - на пример, опсегот {1, 3, 2} ќе се промени во {1, 2, 3}.

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

int main()
{
      vector<int> v;
      
      v.push_back(1);
      v.push_back(2);
      v.push_back(3);
      
      do
      {
            vector<int>::iterator it;
            it = v.begin();
            
            while (it != v.end())
            {
                  cout << *it << " ";
                  it++;
            }
            cout << endl;
      }
      while (next_permutation(v.begin(), v.end()));
      
      return 0;
}

Програмата дадена погоре ќе ги отпечати истите пермутации за кои зборувавме во претходниот дел:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Забележете дека, доколку сакаме да ги генерираме сите пермутации од одреден опсег на елементи со користење на алгоритамот next_permutation(pocetok, kraj), тој опсег мора иницијално да е подреден. Во спротивно, ќе ги изгубиме првите неколку пермутации - всушност, сите оние пермутации кои што претходат на почетниот распоред на тој опсег на елементи.

Да ги разгледаме сега алгоритмите за подредување на опсег од елементи, како и алгоритмите за вршење операции врз опсег од подредени елементи. Најпрвин, запаметете дека, иако овие алгоритми може да ги повикувате врз секаков контејнер - тие се корисни само доколку ги користите врз контејнери кои нудат пристап до случаен елемент во константно време (на пример, вектор). Во спротивно, алгоритмите имаат многу поголема сложеност од онаа наведена во табелата. Едноставно, за одредени контејнери е потребно да се имплементираат специфични алгоритми. На пример, алгоритамот lower_bound(pocetok, kraj, vrednost) наведен во следната табела има логаритамска O(logN) сложеност за вектори, но линеарна O(N) сложеност за множества (set). Множествата си имаат свој метод (кој веќе го споменавме - set.lower_bound(vrednost)), кој е специјално имплементиран за тој тип на контејнер и кој има логаритамска O(logN) сложеност.

Следната програма го илустрира ефектот од користењето на дел од функциите наведени во табелата:

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

int main()
{
      vector<int> v;
      
      v.push_back(3);                                       //v={3}
      v.push_back(1);                                       //v={3, 1}
      v.push_back(2);                                       //v={3, 1, 2}
      
      sort(v.begin(), v.end());                             //v={1, 2, 3}
      
      if (binary_search(v.begin(), v.end(), 3))             //true
            cout << "najdeno" << endl;                      //pechati 'najdeno'
      
      vector<int>::iterator it;
      it = lower_bound(v.begin(), v.end(), 2);
      cout << *it << endl;                                  //pechati '2'
      
      it = upper_bound(v.begin(), v.end(), 2);
      cout << *it << endl;                                  //pechati '3'
      
      return 0;
}

Последната група на алгоритми која што ќе ја разгледаме се т.н. алгоритми за модифицирање на елементи (или опсег од елементи).

Првите неколку функции се јасни сами по себе. Од друга страна, функциите copy(pocetok1, kraj1, pocetok2), unique(pocetok, kraj) и remove(pocetok, kraj, vrednost) се малку поспецифични. Да разгледаме еден пример:

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

int main()
{
      int a = 3, b = 5;
      cout << a << " " << b << endl;                      //pechati '3 5'
      
      swap(a, b);
      cout << a << " " << b << endl;                      //pechati '5 3'
      
      vector<int> v;
      for (int i=6; i>=0; i--)
            v.push_back(i);                               //v={6, 5, 4, 3, 2, 1, 0}
      
      reverse(v.begin(), v.end());                        //v={0, 1, 2, 3, 4, 5, 6}
      replace(v.begin(), v.end(), 2, 0);                  //v={0, 1, 0, 3, 4, 5, 6}
      
      random_shuffle(v.begin(), v.end());                 //v={6, 0, 3, 5, 4, 1, 0}
      
      fill(v.begin(), v.end(), 0);                        //v={0, 0, 0, 0, 0, 0, 0}
      
      v[1] = 3;                                           //v={0, 3, 0, 0, 0, 0, 0}
      v[3] = 2;                                           //v={0, 3, 0, 2, 0, 0, 0}
      
      vector<int> v2;
      
      //v2 mora da ima dovolna golemina
      v2.resize(v.size());
          
      copy(v.begin(), v.end(), v2.begin());               //v2={0, 3, 0, 2, 0, 0, 0}
      
      remove(v.begin(), v.end(), 0);                      //v={3, 2, X, X, X, X, X}
      
      v2.erase(unique(v2.begin(), v2.end()), v2.end());   //v2={0, 3, 0, 2, 0}
      
      return 0;
}

Она што е специфично за функцијата copy(pocetok1, kraj1, pocetok2) е тоа што таа нема да додава нови вредности во векторот, туку ќе ги пребришува старите. Поради тоа, потребно е опсегот кој започнува со pocetok2 да има доволна големина за да ги смести сите елементи од опсегот [pocetok1, kraj1).

Функциите remove(pocetok, kraj, vrednost) и unique(pocetok, kraj) се специфични по тоа што тие не ја намалуваат големината на контејнерот туку враќаат итератор (it) до крајот на новиот (средениот) опсег. Бришењето на елементи е наша обврска: како што можете да видите во примерот даден погоре, функцијата unique(pocetok, kraj) ги елиминира последователните дупликати во v2, но обврската за бришење на другите елементи (нормално, доколку е тоа потребно) паѓа на нас. Во конкретниот пример, unique(pocetok, kraj) враќа итератор до крајот на новиот опсег, а ние ги бришеме сите елементи од новиот крај до стариот (тоа се елементите од векторот кои веќе не ни требаат). Имајте во предвид дека функциите не нудат никакви гаранции за тоа какви елементи ќе се наоѓаат по итераторот кој го враќаат како резултат. Поради тоа, во коментарот на програмата напишавме дека во v се сместени елементите {3, 2, X, X, X, X, X} - 'X' означува непозната или недефинирана вредност.

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

Ред и магацин

Ред (queue) претставува линеарна листа која овозможува внесување на елементи од едната нејзина страна, а извлекување на елементи од другата страна. Првиот елемент што ќе биде додаден во листата ќе биде и првиот елемент кој што ќе биде извлечен (тука зборуваме за FIFO - first in, first out пристап). Редовите наоѓаат примена во различни области - компјутерска наука, транспорт, трговија, земање на бројче и чекање во ред за пријавување на данок во Управа за јавни приходи, итн.

Во Стандардната библиотека на шаблони, редовите претставуваат т.н. "адаптери" - структури кои во позадина користат друг контејнер за имплементирање на потребните методи. Редовите ги нудат методите empty, size, front (за пристап до следниот елемент за извлекување), back (за пристап до последниот додаден елемент), push (за додавање на нов елемент) и pop (за извлекување на следниот елемент).

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

int main()
{
      queue<int> q;
      
      for (int i=1; i<=5; i++)
            q.push(i);                        //q={1, 2, 3, 4, 5}
      
      cout << q.size() << endl;               //pechati '5'
      
      while (!q.empty())
      {
            cout << q.front() << " ";         //pechati '1 2 3 4 5 '
            q.pop();
      }
      
      return 0;
}

Можно е користење на контејнерите deque и list за имплементација на потребните методи. По правило, доколку не се наведе поинаку - како во програмата дадена погоре, редовите користат ред со два краја (deque). Доколку сакаме да користиме друг контејнер, потребно е да го наведеме неговото име при самото креирање на редот:

queue<int, list<int> > d;

Понатаму, додавањето и извлекувањето на елементи се врши на истиот начин како и претходно - без понатамошно споменување на контејнерот. Адаптерот е задолжен за поврзување на соодветните методи кои ги нуди queue во методи кои се имплементирани од страна на deque и list.

Сите методи - empty, size, front, back, push и pop имаат константна сложеност O(1). За да може да користиме редови, потребно е вклучување на соодветната датотека која ја содржи нивната дефиниција (#include <queue>).

Магацин (stack) претставува линеарна листа која овозможува внесување и извлекување на елементи од една страна на листата. Последниот елемент кој се додава во листата е првиот елемент кој ќе биде извлечен (тука зборуваме за LIFO - last in, first out пристап).

Терминот магацин доаѓа од фактот што, доколку редиме кутии една врз друга, кутијата која што е ставена прва (онаа најдолу) е последната кутија што ќе ја извадиме.

Магацините ги нудат методите empty, size, top (за пристап до следниот елемент за извлекување, т.е. последниот додаден елемент), push (за додавање на нов елемент) и pop (за извлекување на следниот елемент).

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

int main()
{
      stack<int> s;
      
      for (int i=1; i<=5; i++)
            s.push(i);                      //q={1, 2, 3, 4, 5}
      
      cout << s.size() << endl;             //pechati '5'
      
      while (!s.empty())
      {
            cout << s.top() << " ";         //pechati '5 4 3 2 1 '
            s.pop();
      }
      
      return 0;
}

Можно е користење на контејнерите deque, list и vector за имплементација на потребните методи. По правило, доколку не се наведе поинаку, магацините користат ред со два краја (deque).

Сите методи - empty, size, top, push и pop имаат константна сложеност O(1). За да може да користиме магацини, потребно е вклучување на соодветната датотека која ја содржи нивната дефиниција (#include <stack>).

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

Приоритетен ред (priority_queue) претставува специјално дизајниран адаптер кој овозможува извлекување, дел по дел, на најголемите елементи од едно множество. Ние, во примерите, ќе работиме со податочни типови за кои е веќе дефиниран начинот на подредување (на пример, int). Во продолжение на предавањето ќе зборуваме и за креирање на сопствени структури и дефинирање на начинот на кој тие може да се споредуваат.

Приоритетните редови ги нудат методите empty, size, top (за пристап до најголемиот елемент), push (за додавање на нов елемент) и pop (за извлекување на најголемиот елемент).

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

int main()
{
      priority_queue<int> pq;
      
      pq.push(3);
      pq.push(2);
      pq.push(5);
      
      while (!pq.empty())
      {
            cout << pq.top() << " ";         //pechati '5 3 2 '
            pq.pop();
      }
      
      return 0;
}

Можно е користење на контејнерите deque и vector за имплементација на потребните методи. По правило, доколку не се наведе поинаку, приоритетните редови користат vector. Одржувањето на елементите во редослед кој овозможува ефикасно извлекување на најголемиот елемент се врши автоматски од страна на адаптерот.

Забелешка: Често, кога се работи со броеви и е потребно елементите да се извлекуваат во обратен редослед (од најмал кон најголем), многу програмери не креираат нов податочен тип кој ќе овозможи соодветен начин на подредување, туку ги сместуваат спротивните вредности на елементите во приоритетен ред. Слично, кога се извлекуваат броеви, се прави уште една негација - за да се добијат вистинските вредности на елементите. На пример, наместо да се внесат 3, 2 и 5, во приоритетниот ред се внесуваат броевите -3, -2, - 5. На овој начин, во понатамошното извршување на програмата, од редот ќе се извлечат броевите -2, -3 и -5 (во тој редослед). Доколку извршиме нивна негација, ќе ги добиеме вистинските вредности на елементите, но во редослед од најмал кој најголем (2, 3, 5).

Методите empty, size и top имаат константна сложеност O(1). Методите push и pop имаат логаритамска сложеност O(logN), која зависи од бројот на елементи во редот. За да може да користиме приоритетни редови, потребно е вклучување на соодветната датотека која ја содржи нивната дефиниција (#include <queue>).

Множества од битови

Множество од битови (bitset) претставува специјален контејнер од Стандардната библиотека на шаблони. Имплементацијата на овој контејнер е многу слична со имплементацијата на вектор од bool (точно/неточно) вредности. Множествата од битови овозможуваат ефикасно сместување на битови (само 1 бит по вредност) и едноставен пристап до елементите од множеството.

Бидејќи претставуваат множества со фиксна големина, при самото креирање на контејнерот е потребно, како параметар, да се зададе бројот на битови (на пример, bitset<8> bs).

За множествата од битови се дефинирани следниве оператори: & (И), &=, | (ИЛИ), |=, ^ (ИСКЛУЧИВО ИЛИ), ^=, << (ПОМЕСТУВАЊЕ НА ЛЕВО), <<=, >> (ПОМЕСТУВАЊЕ НА ДЕСНО), >>=, ~ (НЕ), == и !=. Дополнително, bitset нуди метод за одредување на големината на множеството (size), метод за одредување на бројот на битови кои се еднакви на 1/true (името на методот е count), метод за поставување на бит на вредност 1/true (името на методот е set), метод за бришење на бит и негово поставување на вредност 0/false (името на методот е reset), метод за промена на бит (со име flip), метод за проверка на тоа дали постои барем еден бит кој е различен од 0/false (името на методот е any) и метод за проверка на тоа дали сите битови се еднакви на 0/false (името на овој метод е none). Со користење на операторот '[p]' може да пристапиме до произволен бит од множеството.

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

int main()
{
      bitset<6> bs1;                          //bs1= 000000
      bitset<6> bs2 (string("010101"));       //bs2="010101
      
      cout << bs2.count() << endl;            //pechati '3'
      
      //poziciite se brojat od desno na levo (pochnuvajki so 0)
      bs1[0] = bs1[1] = bs2[0];               //bs1= 000011
      
      bs1 &= bs2;                             //bs1= 000001
      bs1 <<= 2;                              //bs1= 000100
      
      cout << bs1 << endl;                    //pechati '000100'
      return 0;
}

Во стандардот не е дефинирана сложеноста на поголем број од методите кои ги нудат множествата од битови. Сепак, разумно е да се претпостави дека повеќето методи што ги споменавме (size, count, any, none и операторот [p]) имаат константна сложеност O(1). Исклучок од ова се операторите кои вршат менување или споредба на повеќе од еден бит од множеството (&, &=, |, |=, ^, ^=, <<, <<=, >>, >>=, ~, ==, !=). Овие оператори, логично, имаат линеарна сложеност О(N) - која зависи од бројот на битови (N).

За да може да користиме множества од битови, потребно е вклучување на соодветната датотека која ја содржи нивната дефиниција (#include <bitset>).

Контејнери како аргументи на функција

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

int calc(vector<int> v)        //losho - se kopira celata sodrzina
{
      return v[0];
}

int calc(vector<int> &v)       //dobro - se koristi istiot vektor
{
      return v[0];
}

Сопствени типови. Подредување

Ако креираме сопствен податочен тип во C++ и сакаме да користиме некој од контејнерите и/или алгоритмите од Стандардната библиотека на шаблони, неопходна ни е дефиниција за начинот на подредување (на пример, за да може да користиме set или sort). За да креираме ваква дефиниција за подредување, единствено нешто што треба да направиме е да го преоптовариме операторот за споредба '<'. На пример, следнава програма дефинира структура Frac (за складирање на дропки), креира вектор од неколку дропки (од видот a/b) и истите ги подредува во растечки редослед:

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

struct Frac
{
      int a, b;
      
      bool operator <(const Frac &o) const
      {
            //treba da se sporedi (a/b) so (o.a/o.b)
            
            //a/b < o.a/o.b, ako a*(o.b) < b*(o.a)
            //objasnuvanje: pomnozhi gi dvete strani so (b)*(o.b)
            
            return (a*o.b < b*o.a);
      }
};

int main()
{
      Frac f1;
      f1.a = 1;
      f1.b = 2;
      
      Frac f2;
      f2.a = 1;
      f2.b = 3;
      
      Frac f3;
      f3.a = 3;
      f3.b = 4;
      
      vector<Frac> v;
      v.push_back(f1);                                    //v={1/2};
      v.push_back(f2);                                    //v={1/2, 1/3};
      v.push_back(f3);                                    //v={1/2, 1/3, 3/4};
      
      sort(v.begin(), v.end());                           //v={1/3, 1/2, 3/4);
      
      for (int i=0; i< (int) v.size(); i++)
            cout << v[i].a << "/" << v[i].b << " ";       //pechati '1/3 1/2 3/4 '
      
      return 0;
}

Запаметете ја дефиницијата на операторот за споредба '<': резултат од тип bool (точно/неточно), параметар кој претставува константна референца до структура од типот за кој е дефиниран операторот; и клучното зборче 'const'.

Алгоритмите за подредување овозможуваат и наведување на функција за споредба на два елементи од ист тип - како посебен аргумент при повикување на самата функција која го имплементира алгоритамот:

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

//prvo neparnite broevi, pa parnite
bool oddeven(const int &a, const int &b)
{
      if (a%2!=0 && b%2==0)
            return true;
      
      if (a%2==0 && b%2!=0)
            return false;
      
      //dvata se parni ili dvata se naparni
      return (a<b);
}

int main()
{
      vector<int> v;
      
      v.push_back(2);
      v.push_back(5);
      v.push_back(8);
      v.push_back(3);                          //v={2, 5, 8, 3};
      
      sort(v.begin(), v.end(), oddeven);       //v={3, 5, 2, 8};
      
      for (int i=0; i<(int)v.size(); i++)
      {
            cout << v[i] << " ";               //pechati '3 5 2 8 '
      }
      
      return 0;
}

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