std containers vs. own custom containers

Najprej me zanima, če kdo mogoče ve točno kako deluje std::vector. Kako to da lahko hkrati tako hitro briše element, ohranja njihov vrstni red in jih tudi vrača po indeksu ("zaporedna številka"). Kolikor vem, naj bi bil vector v bistvu ArrayList. Ampak array list alocira elemente v enem bloku memorije, torej naenkrat, zato da so lahko elementi v memoriji drug za drugim in je možno hitro vračanje po indeksu (element[x]. Zaradi tega pa je treba pri brisanju vmesnega elementa (če želimo ohraniti vrstni red) premakniti vse sledeče elemente za 1 nazaj, kar pomeni ponovno realokacijo spomina ali pa prekopiranje elementov znotraj trenutno alociranega spomina. Ta postopek ima v naslabšem možen primeru kompleksnost O(n), če je n število elementov seznama, kar vsekakor ni sprejemljivo za hitre algoritme.
Kako lahko std::vector v vseh omenjenih funkcijah ohrani kompleksnost O(1)???

Nadalje me zanima, kakšno je vaše mnenje glede implementiranja lastnih razredov za podatkovne strukture (seznami, množice, hash tables ipd.). Okrog STL knjižnice je spletenih veliko mitov, za katere se ne ve ali zares držijo ali ne. Nekateri pravijo, da je možno z lastnimi specializiranimi razredi doseči tudi 4-5 krat boljši preformans, drugi pravijo da to ni res, oz da ti to lahko uspe le če si "super-duper" programer in uporabljaš ne-vem-kakšne trike. Sam sem spisal LinkedList razred in ArrayList razred, vendar me pri obeh motijo prej omenjene pomanjkljivosti: ArrayList je počasen pri brisanje, LinkedList počasi vrača elemente po indeksu. Rad bi naredil tudi svoj Vector razred, enostavno zato ker mi STL sintaksta ni všeč in mi je bolj komot delat če si lahko naredim svojo. Če ne drugega, pa bi to rad nardil vsaj v izobraževalne namene.

Koliko od vas je že kdaj programiralo razrede podatkovnih struktur? Je kdo uspel sprogramirat vector?

Hvala 64202, ampak na žalost tvoj odgovor ne ustreza nobenemu od mojh vprašanj. Ne zanima me kako lahko vector uporabljam, ker to znam. Zanima me točno kako deluje, kakšno so kompleksnosti njegovih funkcij itd.

Dobro..če ne drugega, sem zdaj izvedel, da je performans vector-ja močno odvsien tudi od kompajlerja. OK, bom probal z debugerjem trace-at not v kodo od vectorja če mi bo uspelo, pa sam zaštekat kakšne stvari....

kdaj se lotit svojih PS? takrat ko ugotivis, da jih rabis. razlog zakaj pa ponavadi lezi v hitrosti. vcasih array pac ni zadosti :)

>Ker če v glavnem uporabljaš vektor tako, da ga enkrat alociraš, notri namečeš vse elemente >in nato le dostopaš do njih (ter morda vse skupaj resizaš enkrat na 10 minut) potem je vector >že maximum v hitrosti, ki ga lahko dosežeš

Sprobal sem naslednje:
v std::vector in v svojo implementacijo LinkedList sem vstavil dosti elementov (mislim da 100.000). Nato sem meril koliko časa traja da pride skoz vse elemente in pobere njihovo vrednost iz seznama v spremenljivko:

npr.

int size=vec.size();
for (int i=0; i<size; i++)
{
    SG_Window *wnd=vec[i];
}

vs.

foreach(SG_Window*, w, ll)
{
    SG_Window *wnd=ll.ElementAt(w);
}

Foreach je nek makro ki olajša uporabljanje iteratorjev za LinkedList strukturo. Koda z mojim LinkedList je bila približno 2x hitrejša. A je mogoče operator [] za linked list tolko počasen in nardi še kej, za ta primer, odvečnega?

Ne vem kaj si delal da si dobil tvojo kodo hitrejšo. Logično to ni. Upam da imaš vklopljene optimizacije in pa da ti hkrati kaj preveč ne optimizira. Samo asignanje spremenljivke v zanki stalno čez prejšnjo vrednost bi sicer to znalo zoptimizirati v eno samo prireditev.

Poleg tega vedi da primerjaš vektor, ki je 'identičen' tabeli / polju (int tabela[100];) z linked listo, kar tvoje rezultate naredi še bolj nesmiselne.