Podatkovna struktura Vektor

Verjetno so vsem po večini že poznana polja (array) in njihov namen uporabe (npr. shrambe podatkov). Za problem si vzamimo sledečo nalogo:

Hočemo sprogramirati opomnik, ki bi shranjeval spisek stvari, katera moramo opraviti. Ko stvar opravimo, pa jo želimo brisati iz seznama.


Stvar bi lahko rešili z uporabo kazalcev, oziroma dinamičnega pomnilnika (polja). Kjer bi stvar postala kompleksna, ter malce nadležna v kolikor poznamo že druge podatkovne strukture.

Če pa jih ne, pa bi po psevdo-kodi izgledala rešitev nekoliko takole:

int velikost=10;
int indeksVsebine=0;
string *opravila = new string[velikost];

if dodal opravilo then
   if indeksVsebine == velikost then
     povečaj velikost,

     shrani pomnilnik opravila v začasno shrambo

     pobriši pomnilnik opravila

     priredi novo velikost opravila

     iz začasne shrambe naloži podatke nazaj v                opravila

     uniči začasno shrambo

   end if

opravila[indeksVsebine] = opravilo

indeksVsebine++

end if

Že tukaj je potrebno ogromno implementacije, kaj šele za dodajanjanje na poljubno mesto, brisanje poljubnega mesta, krčenje, razširjanje,...

Če vas problem zanima, sledite lekciji oziroma nadaljnim korakom.

Vektor je razširljiv seznam, v katerem lahko shranjujemo poljubne elemente. Prav tako sam skrbi za dinamično povečevanje ali krčenje pomnilnika oziroma shrambe. 

V tej lekciji bodo predstavljene sledeče metode, ki jih lahko izvajamo nad podatkovno strukturo vector:

.push_back(element); //dodajanje na konec
.erase(lokacija) //brisi element na lokaciji
.insert(lokacija,element); //vrini element na
lokacijo
.operator[index] //vrne element na specifičnem indeksu
.clear(); //pobriši vektor
.empty() //preveri, če je vektor prazen
.size() //vrni število elementov v vektorju
.begin() //vrne "lokacijo" prvega elementa v vektorju



Rešitev slednjega problema, katero bom po delih skušal razložiti:

#include < vector>

#include < string >

#include < iostream >

using namespace std;

void dodajOpravilo(vector<string>&seznamOpravil,string opravilo)

{

seznamOpravil.push_back(opravilo);

cout<<"Opravilo: "<<opravilo<<" je dodano!"<<endl;

}

void izpisOpravil(vector<string>&seznamOpravil)

{

cout<<endl<<"IZPIS OPRAVIL:"<<endl;

if(seznamOpravil.empty())

{

cout<<"Ni opravil!"<<endl;

return;

}

for(unsigned int i=0;i<seznamOpravil.size();i++)

cout<<"opravilo: "<<i<<"#) "<<seznamOpravil[i]<<endl;

}

void zbrisiOpravilo(vector<string>&seznamOpravil,int index)

{

if(seznamOpravil.empty())

return;

cout<<"Opravilo "<<seznamOpravil[index]<<" je izbrisano!"<<endl;

seznamOpravil.erase(seznamOpravil.begin()+index);

}

void vstaviOpravilo(vector<string>&seznamOpravil,string opravilo,int index)

{

cout<<"Vstavil: "<<opravilo<<" na "<<index<<"# mesto!"<<endl;

seznamOpravil.insert(seznamOpravil.begin()+index,opravilo);

}

void izprazniSeznam(vector<string>&seznamOpravil)

{

seznamOpravil.clear();

cout<<"Izpraznil seznam!"<<endl;

}

int main()

{

vector<string>seznamOpravil;

dodajOpravilo(seznamOpravil,"Prezivi leto 2013");

dodajOpravilo(seznamOpravil,"V");

dodajOpravilo(seznamOpravil,"E");

dodajOpravilo(seznamOpravil,"C");

dodajOpravilo(seznamOpravil,"O");

dodajOpravilo(seznamOpravil,"R");

izpisOpravil(seznamOpravil);

zbrisiOpravilo(seznamOpravil,0);

izpisOpravil(seznamOpravil);

dodajOpravilo(seznamOpravil,"Prezivi leto 2014");

izpisOpravil(seznamOpravil);

vstaviOpravilo(seznamOpravil,"T",3);

izpisOpravil(seznamOpravil);

izprazniSeznam(seznamOpravil);

izpisOpravil(seznamOpravil);

cin.get();

return 0;

}

Poglejmo si kako inicializirati objekt vector.

vector<string>seznamOpravil;

Vector koristi "tehnologijo" template (predloge), da lahko sprejme spremenljivke različnih tipov (int,double,string,...)

V ta namen moramo za deklaracijo objekta vector, nujno v kotnih oklepajih definirati <TIP>, katerega bo sprejel. Za tem pa sledi ime objekta.


Pravtako ga moramo pred uporabo vključiti:

#include < vector >

Poglejmo si funkcjo dodajOpravilo.

V njej na naš seznamOpravil uporabimo metodo .push_back(naše opravilo tipa string)


Vse kar naredi ta metoda je, da na zadnje mesto doda nov element.

Primer:

[a,b,c,d] -> push_back(e) -> [a,b,c,d,e]

Poglejmo si funkcijo izpisOpravil.

V njej na naš seznamOpravil uporabimo metodo
.empty()


Katera vrne true, če je seznam prazen. Oziroma false, če ni.

Primer:

[a] -> empty() -> false
[] -> empty() -> true

V for zanki opazimo še metodo .size().

Ta vrne število elementov v vektorju.

Primer:

[a] -> size() -> 1
[a,b] -> size() -> 2
[a,b,c] -> size() -> 3
.
.
.


Opazimo še eno metodo,
oziroma prekriti operator [], kateri sprejme indeks, kateri element seznamaOpravil naj vrne.
prekriti operatorji so v bistvu metode, njihov 

eksplicitni klic pa izgleda takole:

seznamOpravil.operator[]((unsigned int)index);

torej operator[] je ime metode sledijo pa oklepaji, kateri nosijo vhodne parametre za to metodo.


Primer:

[a,b,c] -> operator[0] -> a
[a,b,c] -> operator[1] -> b
[a,b,c] -> operator[2] -> c

Poglejmo si funkcijo zbrisiOpravilo.

V njej opazimo metodo .erase()

Katera zbriše element iz vektorja na določeni lokaciji.

Te metoda potrebuje začetno točko elementa, katerega bo brisala.
Vanj bomo poslali lokacijo 1. elementa, tako, da bomo klicali metodo .begin(), katera nam jo vrne. Ker pa hočemo zbrisati element na določenem indeksu pa prištejemo lokaciji še toliko mest, da se bo kazalec ustavil na zahtevanem mestu.

polje.erase(polje.begin()+index);

To si lahko predstavljamo tako:

polje[0+indeks]; //begin kot začetni element ~0


Primer:

[aa,a,b,c]->.erase(.begin()) -> [a,b,c]

[a,b,c]->.erase(.begin() + 1) -> [a,c]

Poglejmo si funkcijo vstaviOpravilo.

V njej opazimo metodo .insert()


Deluje podobno kot .erase() (princip izbire elementa)

Vendar nam ta metoda vrine element na poljubnem indeksu.




Primer:

[a,b,d,e] -> .insert(.begin()+2,c) -> [a,b,c,d,e];

Poglejmo si funkcijo izprazniSeznam.

Vector bomo izpraznili z metodo .clear()



Primer:

[a,b,c,d,e,f,g,h] -> .clear() -> []

S tem so osnove pokrite in lekcija je zaključena. 

"Zanimivost": 

V vektor, lahko dodajamo vektor (gnezdimo poljubno v globino).

vector<vector< bool >*>dvaD; 
//dodajanje

for(int i=0;i<10;i++)

dvaD.push_back(new vector< bool >());

//Brisanje

for(int i=0;i<10;i++)

delete dvaD[i];

dvaD.clear();



Ali brez kazalcev (ne pozabimo na prazen konstruktor)

vector<vector< bool >>dvaD;

for(int i=0;i<10;i++)

dvaD.push_back(vector< bool >());

dvaD.clear();