Vektorius (duomenų tipas)

Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

Vektoriaus abstraktus duomenų tipas dažniausia slepia masyvų funkcionalumą. Žodis „vektorius“ kilęs iš lotyniško žodžio vehere, kuris reiškia nešikas, nešiotojas, tas kuris neša.

Sąsaja

Vektorius turi funkcijas:

• Konstruktorius:
  • inicializuoti() – konstruktorius, kuris inicializuoja vektorių.

inicializavus vektorių tenkinama savybė, kad dydis()=0.

• Prieigos funkcijos:
  • dydis() – grąžina vektoriuje esančių elementų skaičių.
  • elementas(pos: sveikas skaičius) – grąžiną elementą esantį vektoriuje pozicijoje pos.

prieš bandant pasiekti elementą turi būti tenkinama savybė, kad 0 ≤ pos ≤ dydis()

• Keitimo funkcijos:
  • keisti(pos: sveikas skaičius, el: elementas) – keisti elementą el esantį pozicijoje pos.

prieš bandant pasiekti elementą keitimui turi būti tenkinama savybė, kad 0 ≤ pos ≤ dydis()

• • įterpti(pos: sveikas skaičius, el: elementas) – įterpti naują elementą el esantį pozicijoje pos paslenkant visus po jo esančius elementus dešinėn.
  • trinti(pos: sveikas skaičius) – ištrinti elementą esantį pozicijoje pos.

Įgyvendinimas

• Vektorius gali būti įgyvendinamas panaudojant vienamatį masyvą. Kuomet įterpiant naujus elementus vektoriaus narių skaičius viršija masyvo ilgį, automatiškai sukuriamas naujas masyvas, į kurį nukopijuojami visi nariai. Naujas masyvas paprastai kuriamas maždaug dvigubai didesnis, nei anksčiau buvęs (tiksli reikšmė vadinamo šio vektoriaus įkrovos faktoriumi (angl. load factor). Funkcija dydis() šiuo atveju grąžina įterptų narių skaičių, neskaičiuodama kol kas nepanaudotų masyvo elementų (galima funkcija talpa() grąžintų skaičių su nepanaudotais elementais). Toks vektorius turi pastovią prieigos prie bet kurio elemento trukmę, kuri nepriklauso nuo elemento padėties. Bendru atveju prireikia $O(n)$ operacijų naujam elementui įterpti ar pašalinti, tačiau paskutiniam elementui pašalinti pakanka $O(1)$. Jam įterpti, esant gerai parinktam įkrovos faktoriui, irgi paprasai gana labai $O(1)$ artimos trukmės.

• Vektoriai taip pat įgyvendinami panaudojant nuorodomis susietus sąrašus (linked list). Toks vektorius daug greičiau įterpia ar pašalina pirmą elementą ($O(1)$, ne $O(n)$), tačiau turi ilgesnę ir nuo elemento padėties priklausančią ($O(n)$) prieigos trukmę. Tačiau jei elementai perrenkami paeiliui, prieigos trukmė sumažėja iki $O(1)$, kaip ir naudojant masyvą.

Jei tam neskirtu vektoriumi vienu metu manipuliuoja kelios gijos, tai gali sukelti lenktynių aplinką. Lygiagrečiam darbui skirtas vektorius vadinamas sinchronizuotu. Toks vektorius dirba lėčiau, todėl nenaudojamas be reikalo. Programavimo bibliotekos siūlo sinchronizuotus (pvz., Java kalbos ArrayList, LinkedList) ir nesinchronizuotus (pvz., Java kalbos Vector) vektoriaus įgyvendinimus.

ADT sudėtingumo įvertinimas

funkcija		sudėtingumas
inicializuoti()		$O(1)$
dydis()		$O(1)$
elementas(pos: sveikas skaičius)		$O(1)$
keisti(pos: sveikas skaičius, el: elementas)		$O(1)$
iterpti(pos: sveikas skaičius, el:elementas)		$O(n)$
trinti(pos: sveikas skaičius)		$O(n)$