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

Стандардната библиотека на шаблони (STL - Standard Template Library) претставува множество од структури и алгоритми кои може да вршат операции над различни типови на податоци. За да имате претстава за што ќе зборуваме во ова предавање, да разгледаме еден едноставен пример на програма која создава листа од 10 цели броеви, ја подредува истата во растечки редослед и потоа ја печати на екран:

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

int main()
{
      vector<int> v;
      
      for (int i=1; i<=10; i++)
            v.push_back((i*i*i) % 20);
      
      //v={1, 8, 7, 4, 5, 16, 3, 12, 9, 0}
      
      //podredi gi broevite
      sort(v.begin(), v.end());
      
      for (int i=0; i<v.size(); i++)
            cout << v[i] << " ";                 //pechati "0 1 3 4 5 7 8 9 12 16 "
      
      return 0;
}

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

Контејнерите претставуваат структури на податоци во кои може да се чуваат разни информации. Досега, во сите предавања, зборувавме за само еден симплифициран "контејнер" на податоци: низата. Всушност, во целиот програмски јазик C++ (без STL), не постои друг контејнер во кој може да се сместуваат повеќе податоци од еден ист тип. Во примерот даден погоре, вектор (vector) претставува контејнер за чување на податоци од тип int (затоа и запишавме vector<int>). Сите контејнери кои се дел од Стандардната библиотека на шаблони се имплементирани како параметаризирани структури. Ова значи дека еден контејнер може да служи за чување на податоци од кој било тип (int, float, double, string, vector<int>, vector<float>, vector<vector<float> >, итн). За да може да користиме еден контејнер за чување на податоци, потребно е да ја вклучиме датотеката во која е тој дефиниран - во програмата дадена погоре, тоа го правиме со наредбата #include <vector>.

Итераторите претставуваат еден вид покажувачи кон елементите од контејнерите. Итераторите се користат за движење низ елементите од еден контејнер, како и за означување на делови од податоци врз кои сакаме да вршиме операции. Во програмата дадена погоре, како параметри на функцијата sort испративме два итератора: v.begin() и v.end(). Овие итератори означуваат дека сакаме да ги подредиме сите елементи од векторот v - сите елементи помеѓу v.begin() и v.end().

Алгоритмите служат за вршење на операции врз податоци (подредување, пронаоѓање на најголема вредност, итн.). Во програмата дадена погоре, извршивме операција подредување врз сите податоци помеѓу v.begin() и v.end(). Ова го направивме со повикување на функцијата sort(pocetok, kraj). И тука, повторно, забележете дека е потребно вклучување на соодветната датотека во која е дефинирана функцијата за подредување (#include <algorithm>)

Вектор

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

Следнава програма креира празен вектор, додава неколку елементи (од тип string) во векторот и, на крај, ја печати неговата содржина.

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

int main()
{
      vector<string> zborovi;
      
      zborovi.push_back("zdravo");
      zborovi.push_back("pero");
      zborovi.push_back("kako");
      zborovi.push_back("si");
      
      for (int i=0; i<zborovi.size(); i++)
            cout << zborovi[i] << " ";          //pechati "zdravo pero kako si "
      
      return 0;
}

До елементите на векторот пристапуваме на идентичен начин како што пристапуваме и до елементите на една низа - со користење на операторот [p]. Како што може да забележите од програмата дадена погоре, елементи во векторот додаваме со повик на методот push_back(string str). На тој начин, ја зголемуваме големината на векторот за 1. Векторот ја одредува потребната меморија автоматски, па не се грижете за перформансите на операцијата за додавање на нов елемент. Всушност, за да може да додаваме елементи во векторот во константно O(1) време, кога се додаваат одредени елементи, векторот врши алоцирање на повеќе меморија отколку што е тоа потребно во тој момент. Со методот capacity() може да одредиме за колку точно елементи е резервирано меморија - односно колку елементи може да се сместат во векторот пред неговата големина да биде (автоматски) зголемена.

Бројот на елементи во векторот може да се открие со повик на методот size(). Важно е да знаете дека size() враќа целобројни типови на податоци (што е нормално), но податоци кои се без знак (unsigned). Поради тоа, кога ја преведуваме програмата дадена погоре, компајлерот ќе не предупреди дека споредуваме (i < zborovi.size()) два различни целобројни типови на податоци (едниот со знак - i, а другиот без знак). Поради тоа, потребно е или да го промениме типот на променливата i, или да извршиме кастирање (претопување) на податокот кој ќе го врати методот size() - на пример, i < (int) zborovi.size(). Кај сите примери кои ќе бидат дадени во продолжение, ќе биде извршено претопување (во тип int) на податокот кој го враќа методот size().

Големината на векторот (бројот на елементи) може да ја специфицираме и при неговото креирање - со наведување на бројот на елементи и нивната иницијална вредност: по името на променливата, во загради. Покрај ова, за време на извршување на програмата, со повикување на методот resize може да го зголемиме или намалиме бројот на елементи во векторот. Доколку, како аргумент на resize, пратиме вредност која е поголема од тековниот број на елементи, тогаш на крајот од векторот ќе се додадат нови елементи. Во спротивно, доколку како аргумент испратиме вредност која е помала од тековниот број на елементи, тогаш од векторот ќе се избришат последните неколку елементи. Можеме да ги избришеме сите елементи од векторот (да ја поставиме неговата големина на 0) со повикување на методот clear().

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

int main()
{
      vector<int> v0;                                    //v={}
      vector<int> v1(5, 0);                              //v1={0, 0, 0, 0, 0}
      vector<int> v2(3, 5);                              //v2={5, 5, 5}
      
      //ako ne navedeme vtor argument, se pretpostavuva 0
      vector<int> v3(3);                                 //v3={0, 0, 0}
      
      vector<int> v4(v2);                                //v4={5, 5, 5}
      
      //v1.resize(n, v) -> [n] oznacuva kolku elementi, a [v] koja vrednost
      //treba da se iskoristi dokolku treba da se dodadat novi elementi
          
      v1.resize(7, 3);                                   //v1={0, 0, 0, 0, 0, 3, 3}
      v1.push_back(2);                                   //v1={0, 0, 0, 0, 0, 3, 3, 2}
      v1.resize(2, 5);                                   //v1={0, 0}
      v1.resize(2, 8);                                   //v1={0, 0}
      v1.push_back(5);                                   //v1={0, 0, 5}
      
      v1.resize(4, 3);                                   //v1={0, 0, 5, 3}
      v1.resize(5);                                      //v1={0, 0, 5, 3, 0}
      
      v1.clear();                                        //v1={}
      v2.clear();                                        //v2={}
      
      cout << v1.size() + v2.size() << endl;             //pechati '0'
      return 0;
}

Два вектори може да се споредат со примена на операторите == и != (на пример, v1 == v2). Притоа, споредувањето се врши елемент по елемент. Сложеноста на оваа постапка е O(N).

Дозволено е и креирање на повеќедимензионални низи. Притоа, треба да се внимава да се остави празно место помеѓу двата знака '>' на крајот од дефиницијата на еден вектор. Ова треба да се направи бидејќи, во C++, веќе постои оператор '>>' (кој, како што веќе знаете, служи за поместување на битови).

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

int main()
{
      //edna dimenzija
      vector<string> v1(3, "ABC");                         //v1={"ABC", "ABC", "ABC");
            
      //dve dimenzii (zabelezhete '> >')
      vector<vector<int> > v2(3);                           //v2={{}, {}, {})
                  
      v2[0].push_back(1);                                   //v2={{1}, {}, {})
      v2[0].push_back(2);                                   //v2={{1, 2}, {}, {})
                              
      v2[1].push_back(3);                                   //v2={{1, 2}, {3}, {})
                                    
      v2[2].push_back(4);                                   //v2={{1, 2}, {3}, {4})
      v2[2].push_back(5);                                   //v2={{1, 2}, {3}, {4, 5})
      v2[2].push_back(6);                                   //v2={{1, 2}, {3}, {4, 5, 6})
                                                      
      cout << v2[0][0] + v2[0][1] << endl;                  //pechati '3' (1+2)
      cout << v2[1][0] << endl;                             //pechati '3' (3)
      cout << v2[2][0] + v2[2][1] + v2[2][2] << endl;       //pechati '15' (4+5+6)
                                                      
      cout << v2[0].size() << endl;                         //pechati '2'
      cout << v2[1].size() << endl;                         //pechati '1'
      cout << v2[2].size() << endl;                         //pechati '3'
                                                      
      return 0;
}

Постојат и методи (insert и erase) кои служат за вметнување на елемент (или елементи) на произволна позиција во векторот (не само на крајот, како што го прави тоа push_back), односно бришење на произволен елемент (или елементи) од векторот. Овие операции имаат линеарна сложеност: за додавање или бришење на елемент е потребно поместување на сите елементи кои се наоѓаат по тој елемент - на десно, доколку се додава нов елемент, или на лево, доколку се брише одреден елемент. За insert и erase ќе зборуваме повеќе во делот за итератори.

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

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

int main()
{
      vector<int> v;                                    //v={}
      v.push_back(3);                                   //v={3}
      v.push_back(1);                                   //v={3, 1}
      v.push_back(5);                                   //v={3, 1, 5}
      
      v.pop_back();                                     //v={3, 1} - brishenje na posledniot element
      
      v.front() = 1;                                    //v={1, 1} - promena na prviot element
      v.back() = 7;                                     //v={1, 7} - promena na posledniot element
      
      cout << v.front() + v.back() << endl;             //pechati '8' (1+7)
      
      if (v.empty() == false)
            cout << v.size() << endl;                   //pechati '2'
      
      v.insert(v.begin(), 9);                           //v={9, 1, 7}
      v.insert(v.begin(), 3, 2);                        //v={2, 2, 2, 9, 1, 7}
      v.erase(v.begin());                               //v={2, 2, 9, 1, 7}
      
      cout << v.size() << endl;                         //pechati '5'
      return 0;
}

Кај векторите, методите size, empty, push_back, pop_back, front, back, begin и end имаат константна сложеност O(1). Пристапувањето до елемент на одредена позиција (со помош на операторот [p]) има, исто така, константна сложеност O(1). Останатите методи (resize, clear, insert, erase) имаат линеарна сложеност O(N), која зависи од бројот на елементи во векторот и/или бројот на елементи кои се внесуваат или бришат од векторот.

Ред со два краја

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

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

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

int main()
{
      deque<int> d;
      
      for (int i=0; i<3; i++)
            d.push_back(i);                           //d={0, 1, 2}
      
      for (int i=0; i<3; i++)
            d.push_front(i);                          //d={2, 1, 0, 0, 1, 2}
      
      int s = 0;
      
      for (int i=0; i < (int)d.size(); i++)
            s += d[i];
      
      cout << s << endl;                              //pechati '6'
      return 0;
}

Како што рековме, редот со два краја ги нуди истите методи како и векторите - пристап до елемент на одредена позиција (операторот '[p]'), size, empty, push_back, pop_back, front, back, begin и end со константна сложеност O(1), и resize, clear, insert, erase со линеарна сложеност O(N). Дополнително, тој ги нуди и методите push_front и pop_front - и двата со константна сложеност O(1).

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

Листа

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

Следната програма ги прикажува можностите на листите:

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

int main()
{
      list<int> l;                     //l={}
      l.push_back(4);                  //l={4}
      l.push_front(1);                 //l={1, 4}
      l.push_back(5);                  //l={1, 4, 5}
      l.push_back(6);                  //l={1, 4, 5, 6}
      l.push_back(6);                  //l={1, 4, 5, 6, 6}
      
      l.pop_front();                   //l={4, 5, 6, 6}
      l.pop_back();                    //l={4, 5, 6}
      
      l.insert(l.begin(), 3);          //l={3, 4, 5, 6}
      l.insert(l.begin(), 2, 1);       //l={1, 1, 3, 4, 5, 6}
      
      cout << l.size() << endl;        //pechati '6'
      return 0;
}

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

Кај листите, методите size, empty, push_back, pop_back, push_front, pop_front, front, back, begin и end имаат константна сложеност O(1). Останатите методи (resize, clear, insert, erase) имаат линеарна сложеност O(N), која зависи од бројот на елементи во листата или бројот на елементи кои се внесуваат или бришат. За внесување на елемент на произволна позиција ќе зборуваме во некој следен дел.

Листите нудат и методи за подредување на елементите (sort - со сложеност O(NlogN)), за преместување (не за копирање) на една листа во друга (splice - со константна O(1) сложеност) и за спојување на две подредени листи во нова подредена листа (merge - со линеарна O(N) сложеност).

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

int main()
{
      list<int> l1;
      list<int> l2;
      
      for (int i=0; i<5; i++)
            l1.push_back(i);                     //l1={0, 1, 2, 3, 4}
      
      for (int i=4; i<10; i+=2)
            l2.push_back(i);                     //l2={4, 6, 8}
      
      list<int>::iterator it = l1.begin();
      it++;                                      //it pokazuva na '1' vo listata l1
      
      l1.splice(it, l2);                         //l1={0, 4, 6, 8, 1, 2, 3, 4}
          
      //tuka l2={}, bidejki site elementi se premestija vo l1
      
      l2.push_back(6);                           //l2={6}
      l2.push_back(4);                           //l2={6, 4}
      
      l1.sort();                                 //l1={0, 1, 2, 3, 4, 4, 6, 8}
      l2.sort();                                 //l2={4, 6}
      
      l2.merge(l1);                              //l2={0, 1, 2, 3, 4, 4, 4, 6, 6, 8}
          
      //tuka l1={}, bidejki site elementi se premestija vo l2
      
      cout << l2.size() << endl;                 //pechati '10'
      return 0;
}

Итератори

Итераторите овозможуваат движење низ елементите од еден контејнер, но и означување на групи податоци врз кои сакаме да вршиме одредени операции. Итераторите (интересно) нудат слични можности како и покажувачите: движење нанапред или наназад со помош на операторите ++ и --, скокање нанапред или наназад со одреден чекор (v.begin() + 20, v.end() - 4), добивање на вредноста кон која покажува итераторот (*it), споредување со други итератори (!=, ==, <, <=, >, >=) и одредување на растојанието (во број на елементи) помеѓу два итератори (користејќи го изразот it1 - it2, или преку повикување на методот distance).

Забележете дека, поради фактот што итераторите нудат слични операции како покажувачите, во C++ е овозможено користење на алгоритмите кои се дел од Стандардната библиотека на шаблони врз низи од податоци.

Да разгледаме еден пример:

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

int main()
{
      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}
      
      sort(v.begin(), v.end());
      //v={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
      
      //vrz nizi
      int array[10];
      for (int i=0; i<10; i++)
            array[i] = (i*i*i) % 10;
      
      //array={0, 1, 8, 7, 4, 5, 6, 3, 2, 9}
      
      sort(array, array+10);
      //array={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
      
      vector<int>::iterator it = v.begin();
      cout << *it << endl;                                //pechati '0'
      
      it++;
      cout << *it << endl;                                //pechati '1'
      
      *it = 7;
      //v={0, 7, 2, 3, 4, 5, 6, 7, 8, 9}
      
      cout << *it << endl;                                //pechati '7'
      
      it += 2;
      cout << *it << endl;                                //pechati '3'
      
      //izminuvanje na site elementi
      it = v.begin();
      while (it != v.end())
      {
            cout << *it << endl;
            it++;
      }
      
      cout << distance(v.begin(), v.end()) << endl;       //pechati '10'
      
      return 0;
}

Забележете дека (овој факт го искористивме и кај двата повици на методот sort) итераторот begin() покажува на првиот елемент на еден контејнер (заменето со array - што е локацијата на првиот елемент на низата array). Од друга страна, итераторот end() не покажува на последниот елемент!!! од контејнерот, туку на еден елемент после него (заменето со array + 10 - локацијата на array[10]). На овој начин, можеме ефикасно да ги изминеме сите елементи од еден контејнер - се движиме низ елементите се додека не биде исполнет условот it == container.end(). Сите контејнери и алгоритми кои се дел од Стандардната библиотека на шаблони го користат овој факт - при повикување на која било функција која очекува опсег на елементи (почетен и краен итератор), се вршат операции од почетниот итератор (вклучувајќи го и елементот на кој тој покажува) до крајниот итератор (но, не вклучувајќи го елементот на кој тој покажува).

Всушност, во претходната програма, елементите v[10] и array[10] не ни постојат, и пристапувањето до нивната вредност би било грешка.

Текстуални податоци (string)

Стандардната библиотека на шаблони нуди посебен контејнер (string) за работа со текстуални податоци. Иако досега, во неколку програми, работевме со овој контејнер, сега е време подетално да ги наведеме методите кои тој ги нуди.

Најпрвин, треба да кажеме дека string всушност дава еден вид проширување на операциите кои се нудат од страна на vector<char>. Како таков контејнер, string ги нуди повеќето методи кои ги нуди и контејнерот вектор - size, empty, push_back, begin, end, resize, clear, insert и erase. Дополнително, string (како и вектор) овозможува пристапување до елемент на произволна позиција - преку операторот '[p]' (во овој случај, тоа се знаците во текстот). За разлика од vector<char>, string користи посебен механизам за управување со меморија (небитно за нас), и нуди неколку методи за манипулирање со текстуални податоци.

Најпрвин, да разгледаме како може да споиме два string-a. Првиот начин на спојување е со помош на операторот '+': имено, два string-a str1 и str2 може да ги споиме во нов string со нивно едноставно "собирање" - str1+str2, или, доколку е тоа потребно, str1+=str2. Вториот начин на спојување го користи методот append(vtor): prv.append(vtor) ќе ги спои string-овите prv и vtor и ќе го смести резултатот во променливата prv.

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

int main()
{
      string a = "pocetok";
      string b = " i ";
      string c = "kraj";
      
      cout << a.size() << endl;             //pechati '7'
      
      for (int i=0; i<c.size(); i++)
            cout << c[i] << " ";            //pechati 'k r a j ';
      
      cout << endl;
      
      a += b;                               //a='pocetok i '
      a.append(c);                          //a='pocetok i kraj'
      a.push_back('!');                     //a='pocetok i kraj!'
      
      string res = b + c;                   //res=' i kraj'
      cout << res << endl;                  //pechati ' i kraj'
      return 0;
}

Контејнерот string нуди метод substr преку кој може да вратиме одреден дел од почетниот string. Притоа, доколку го повикаме методот преку наведување на само еден аргумент од тип int, на пример str.substr(x), тој ќе врати дел од оригиналниот string str кој почнува од позицијата x и завршува со завршување на string-от str. Од друга страна, доколку наведеме два аргумента од тип int, на пример str.substring(x, len), операцијата ќе врати дел од оригиналниот string str кој почнува од позиција x и има големина најмногу len (доколку од x до крајот на оригиналниот string има помалку од len знаци, се враќаат само онолку знаци колку што има до крајот на string-от).

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

int main()
{
      string str = "alo alo alo halo";
      
      cout << str.substr(0, 3) << endl;          //pechati 'alo'
      cout << str.substr(0, 5) << endl;          //pechati 'alo a'
      
      cout << str.substr(12) << endl;            //pechati 'halo'
      cout << str.substr(12, 100) << endl;       //pechati 'halo'
      
      return 0;
}

Контејнерот string може едноставно да се претвори (доколку, за некое чудо, има потреба од тоа) во стандардна текстуална низа (C тип на текстуален податок - char*) со повикување на методот c_str(). На пример, следниве две линии претвораат string во низа од char знаци:

char* cstr = new char [str.size()+1];
strcpy (cstr, str.c_str());

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

Читање на текстуални податоци. Запишување во string

Стандардната библиотека на шаблони овозможува читање од текстуални податоци (string), како тие да претставуваат влезен поток на податоци (користејќи istringstream), и запишување на податоци во текстуална низа (string) - слично, како да вршиме операции врз излезен поток на податоци (користејќи ostringstream).

За istringstream е доволно да знаеме како да ги наведеме влезните податоци (со предавање на променлива/константа од тип string: во загради, при самото креирање на потокот), и како да ги читаме податоците (со операторот >>).

За ostringstream е доволно да знаеме како да запишуваме податоци во потокот (со операторот <<) и како да го претвориме потокот во string (со повикување на методот str). Дополнително, доколку работиме со децимални броеви и сакаме да отпечатиме одреден број со X децимали, потребно е да го повикаме методот precision - со аргумент X, и, пред печатењето, да наведеме fixed како информација до потокот (види го примерот подолу). Изразот fixed означува дека сакаме да го отпечатиме децималниот број на стандарден начин - во спротивно, системот може да одлучи дека е подобро да го отпечати бројот во т.н. научна форма - на пример, 1.356*10⁷ или 1.356E7.

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

int main()
{
      string s;
      s = "1 20 3 40";
      
      int temp;
      vector<int> v;
      
      istringstream is(s);
      while (is >> temp)
            v.push_back(temp);                  //v={1, 20, 3, 40};
      
      ostringstream os;
      for (int i=0; i<(int) v.size(); i++)
            os << v[i];
      
      string res = os.str();
      cout << res << endl;                      //pechati '120340'
      
      ostringstream d;
      d.precision(4);
      d << fixed << 3.5 << " ";
      d << fixed << 2.01010101 << " " << 8.0;
      
      res = d.str();
      cout << res << endl;                      //pechati '3.5000 2.0101 8.0000'
      
      return 0;
}

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

Множество

Множество (set) претставува контејнер за чување на уникатни вредности. По правило, множествата се имплементирани како бинарни дрва за пребарување, што овозможува внесување, пребројување и бришење на елементи во, многу ефикасно, O(logN) време. Важно е да напоменеме дека, покрај set, постои и контејнер (multiset) кој овозможува чување и на неуникатни вредности (вредности кои може да се повторуваат). Овој контејнер (multiset) ги има истите карактеристики како и обичните множества.

Да разгледаме еден пример:

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

int main()
{
      //SET
      set<int> s;
      
      for (int i=0; i<10; i++)
            s.insert(i);
      
      cout << s.size() << endl;        //pechati '10'
      
      for (int i=0; i<5; i++)
            s.insert(i);               //nema efekt
      
      cout << s.size() << endl;        //pechati '10'
      
      s.erase(2);
      s.erase(8);
      
      cout << s.size() << endl;        //pechati '8'
      
      //MULTISET
      multiset<int> ms;
      
      for (int i=0; i<10; i++)
            ms.insert(i);
      
      cout << ms.size() << endl;       //pechati '10'
      
      for (int i=0; i<5; i++)
            ms.insert(i);
      
      cout << ms.size() << endl;       //pechati '15'
      
      ms.erase(2);                     //se brishat dvete 2-ki
      ms.erase(8);
      
      cout << ms.size() << endl;       //pechati '12'
      
      return 0;
}

Внесување на елемент во множество се прави со повикување на методот insert. Доколку сакаме да ги избришеме сите елементи со одредена вредност, тоа може да го направиме со користење на методот erase - како што е тоа направено во примерот даден погоре. Големината (бројот на елементи) во едно множество може да ја добиеме на идентичен начин како и кај контејнерот vector - со повикување на методот size. Слично, методот empty враќа true/false вредност која означува дали контејнерот е празен или не (дали содржи најмалку еден елемент).

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

Доколку сакаме да ги изминеме сите елементи еден по еден (и, на пример, да ги отпечатиме на екран), тоа може да го направиме со користење на итератори - притоа, потребно е да се движиме од почетокот (container.begin()) до крајот (container.end()) на множеството.

Постојат две методи со кои може да провериме дали еден елемент постои во множество или не - тоа се методите find и count. Притоа, find враќа итератор до елементот кој го бараме (или container.end(), доколку елементот не постои), додека count го враќа бројот на елементи кои се еднакви на вредноста која ја бараме.

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

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

int main()
{
      //SET
      set<int> s;
      
      for (int i=0; i<10; i++)
            s.insert(i);
      
      if (s.find(5) != s.end())
            cout << "BINGO" << endl;           //pechati 'BINGO'
      
      cout << s.count(2) << endl;              //pechati '1'
      
      s.erase(2);
      cout << s.count(2) << endl;              //pechati '0'
      
      set<int>::iterator it = s.begin();
      while (it != s.end())
      {
            cout << *it << " ";
            it++;
      }
      cout << endl;
      //pechati '0 1 3 4 5 6 7 8 9 '
      
      
      //MULTISET
      multiset<int> ms;
      
      for (int i=0; i<10; i++)
            ms.insert(i);
      
      for (int i=0; i<5; i++)
            ms.insert(i);
      
      cout << ms.count(2) << endl;             //pechati '2'
      
      //izbrishi edna 2-ka
      ms.erase(ms.find(2));
      
      cout << ms.count(2) << endl;             //pechati '1'
      
      //izbrishi gi site elementi pomegju 5 i 8 (bez 8)
      ms.erase(ms.find(5), ms.find(8));
      
      return 0;
}

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

Кај множествата, методите size, empty, begin и end имаат константна сложеност O(1). Методите insert, erase, find и count имаат логаритамска сложеност O(logN), додека методот clear (за бришење на сите елементи од едно множество) има линеарна сложеност O(N).

Важно е да напоменеме дека постојат две методи lower_bound и upper_bound кои примаат вредност V како аргумент, а враќаат итератор до првиот елемент (кога множеството се разгледува како подредена низа од елементи) поголем или еднаков на V (за lower_bound) или првиот елемент поголем од V (за upper_bound). На пример, ако елементите во множеството се {0, 2, 4, 6, 8, 10}, set.lower_bound(3) ќе врати итератор кој покажува на елементот 4, set.lower_bound(2) ќе врати итератор кој покажува на елементот 2, set.upper_bound(3) ќе врати итератор кој покажува на елементот 4, додека set.upper_bound(2) ќе врати итератор кој покажува на елементот 4.

Креирање на вектори и множества

Уште при самото креирање на вектор или множество, можеме да наведеме опсег на вредности од кои тој контејнер треба да биде составен. На пример, следнава програма креира вектор и множество - составени од неколку цели броеви:

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

int main()
{
      int arr[] = {1, 3, 7, 6, 3, 4, 7};
      
      vector<int> v(arr, arr+7);                //v={1, 3, 7, 6, 3, 4, 7}
      set<int> s(v.begin(), v.end());           //s={1, 3, 4, 6, 7}
      
      vector<int> v2(s.begin(), s.end());       //v2={1, 3, 4, 6, 7}
      
      cout << v2.size() << endl;                //pechati '5'
      
      return 0;
}

Множествата не чуваат повеќе од една копија од една вредност, па со примерот даден погоре ефективно ги елиминиравме дупликатите од една листа на цели броеви. Дополнително, бидејќи множествата се имплементирани како бинарни дрва, при нивното изминување со итератор (од s.begin() до s.end()) елементите се враќаат во подреден (растечки) редослед - практично, покрај елиминирање на дупликати, сме успеале и да ги подредиме вредностите.

Векторите овозможуваат повикување на методите insert и erase и врз опсег од елементи: vector.insert(kade, pocetok, kraj) и vector.erase(pocetok, kraj). На тој начин можеме, како и при самото креирање на контејнерот, да додаваме, наеднаш, повеќе елементи во векторот. Дополнително, можеме и да избришеме опсег од елементи со едноставно наведување на итератор до првиот елемент од опсегот и итератор до крајот на опсегот. Како и се останато во Стандардната библиотека на шаблони, итераторот до крајот на опсегот (kraj) не се смета како дел од опсегот.

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

int main()
{
      int arr[] = {1, 3, 7, 6, 3};
      vector<int> v(arr, arr+5);                  //v={1, 3, 7, 6, 3}
      
      vector<int> v2;                             //v2={}
      v2.push_back(2);                            //v2={2}
      v2.push_back(3);                            //v2={2, 3}
      
      vector<int>::iterator it = v.begin();       //it pokazuva na v[0]
      it = it+2;                                  //it pokazuva na v[2]
      
      v.insert(it, v2.begin(), v2.end());         //v={1, 3, 2, 3, 7, 6, 3}
      
      //"it" ne vazi povekje
      //prakticno, ne znaeme na shto pokazuva
      it = v.begin();                             //ne "znaevme!" na shto pokazuva :)
      
      v.erase(it+2, v.end());                     //v={1, 3}
      
      cout << v.size() << endl;                   //pechati '2'
      cout << v2.size() << endl;                  //pechati '2'
      
      return 0;
}

И двата метода, vector.insert(kade, pocetok, kraj) и vector.erase(pocetok, kraj) имаат линеарна сложеност O(N), која зависи од бројот на внесени + преместени елементи (за insert) или бројот на избришани + преместени елементи (за erase).

Пар

Пар претставува комбинација од две различни вредности (можеби од различен тип) кои се чуваат под едно заедничко име. Конкретните вредности може да се пристапат преку членовите first и second. Притоа, бидејќи е непрактично да се подесуваат и двата члена при самото доделување вредност на парот (потребни се повеќе линии код), за дефинирање на одреден пар може да ја искористиме функцијата make_pair(val1, val2).

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

int main()
{
      pair<int, string> p;
      p.first = 5;                                      //p.first e od tip 'int'
      p.second = "pet";                                 //p.second e od tip 'string'
      
      cout << p.first << " " << p.second << endl;       //pechati '5 pet'
      
      vector<pair<string, double> > v;
      
      pair<string, double> p1;
      p1 = make_pair("bla bla", 3.5);
      
      v.push_back(p1);
      v.push_back(p1);
      
      for (int i=0; i<5; i++)
      {
            pair<string, double> temp;
            temp = make_pair("chu chu", 0.5 * i);
            
            v.push_back(temp);
      }
      
      cout << v.size() << endl;                         //pechati '7'
      
      return 0;
}

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

Важно е да напоменеме дека за паровите се веќе имплементирани сите оператори за споредба (==, !=, <, <=, >, >=). Дополнително, може да се користат и алгоритмите од Стандардната библиотека на шаблони за кои е потребна дефиниција за начинот на споредба - на пример sort(pocetok, kraj). Споредбата се врши на тој начин што најпрвин се споредува првата вредност (pair.first) и елементите се подредуваат според неа. Единствено доколку првата вредност е еднаква, се споредува втората вредност (pair.second) и елементите (кои имале еднаква pair.first вредност) се подредуваат според оваа вредност.

Мапа

Мапа (map) претставува контејнер за чување на пар од податоци - клуч и вредност. На пример, можеби имаме потреба да направиме програма која ќе прочита одреден текст - листа од зборови (на пример, "Tosho", "e", "najgolem", "fraer", "vo", "Bitola", "i", "vo", "Skopje"), и за секој од зборовите ќе изброи колку пати се појавува тој во текстот (во претходниот пример единствено "vo" се појави повеќе од еднаш - "Tosho" = 1, "e" = 1, "najgolem" = 1, "fraer" = 1, "vo" = 2, "Bitola" = 1, "i" = 1, "Skopje" = 1). Ова е еден пример за мапа каде клучеви се зборовите, а вредноста број кој означува колку пати се појавил клучот. Да разгледаме еден пример:

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

int main()
{
      map<string, int> m;
      m["prv"] = 13;
      m["vtor"] = 17;
      m["tret"] = 8;
      
      m["tret"] = m["tret"] + 12;                   //m["tret"] = 20
      
      cout << m["prv"] << endl;                     //pechati '13'
      cout << m["vtor"] << endl;                    //pechati '17'
      
      cout << (m["prv"] + m["vtor"]) << endl;       //pechati '30'
      
      return 0;
}

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

Важно е да кажеме дека постојат два начини за пристапување до елемент со одреден клуч: преку наведување на клучот во '[p]' загради (види програма) и преку користење на методот find. Притоа, методот find никогаш не резултира со менување на елементите во мапата. Од друга страна, '[p]' ќе креира нов пар (клуч, вредност) во мапата доколку таков клуч не постои. Како и кај множествата, може да го користиме методот count за да изброиме колку парови во мапата имаат клуч со одредена вредност. Кај map, резултатот секогаш ќе биде 1 (доколку постои таков клуч) или 0 (доколку не постои таков клуч). Од друга страна, кај multimap може да добиеме вредност која што е поголема од 1.

Кај мапите, методите size, empty, begin и end имаат константна сложеност O(1). Методите insert, erase, find, count, lower_bound, upper_bound и операторот '[p]' имаат логаритамска сложеност O(logN), додека методата clear (за бришење на сите елементи од мапата) има линеарна сложеност O(N).

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