STL jämnförelser

Om man tänker sig en Vector som en Array och en List som en länkad lista så kan man ju räkna lite själv på det beroende på vad man sak göra.

// BeatBox

Ja, om du vill komma åt element i mitten är vektor snabbare förstås och logiskt sett borde de andra klasserna som list och queue och deque osv vara bättre om du bara vill läsa från den ena sidan till den andra och om du bara vill lägga till något i en ände och inte i mitten.

Nakdelen med en vektor är att man bara kan stoppa in i slutet och jag läste att en list är 30% snabbare på att stoppa in ibörjan än i slutet.

jag kan inte förstå hur en vektor skulle vara snabbare att komma åt element i mitten?

Det jag vill göra är att kunna stoppa in snabbast möjligast efter det att jag konstaterat att elementet inte finns i vektorn/listan.

<font size="1" face="Verdana, Arial, Helvetica, sans-serif">Kod:<font size="1" face="Verdana, Arial, Helvetica, sans-serif" color="#666600">
så här använder jag det (väldigt strippat):

min_struct{
string value;
};

int main( int arc, char* argv[] )
{
vector< min_struct > x;
vector< min_struct >::iterator y;

struct min_struct z;
z.value = "test";

for(y=x.begin(); y != x.end(); y++)
{
   if(y-\>value == z.value)
        break;
}

if( y == x.end() )
{
   x.push_back(z);
   cout \<\< "new insert" \<\< endl;
}
else
{
   cout \<\< "element existed" \<\< endl;
}

}

Jag måste alltså springa igenom hela vektor för att hitta elementet eftersom jag inte kan använda find eftersom jag ska leta upp stringen i min_struct.

provade att koda om detta till en map. snabb som fan med lite element i men vid en map på storlek över 1000 så blev den långsam plus att den tog lång tid att bygga om trädet.

jag kan inte förstå hur en vektor skulle vara snabbare att komma åt element i mitten?

Det beror väl på hur du kommer åt elementet. Du har något exempel där du söker ett element som du inte vet var det finns. Det tar ju ett tag. Men om du vet var det finns, så kommer du åt det direkt. Hur ska du kunna göra en direktåtkomst i en länkad lista?

sant... det kan man ju inte... men nu vet jag ju inte vilken position det finns på... så då skulle det inte spela roll om jag har en lista eller en vektor, men det jag mest undrar är tid för inserts till dessa templates...

Jo, i det fallet borde list vara snabbare men jag vet inte säkert. Annars kan du skriva x.insert(x.begin(), z) för att sätta in först i vektorn. Då kanske det går lika snabbt?

Annars kan du skriva x.insert(x.begin(), z) för att sätta in först i vektorn. Då kanske det går lika snabbt?

Skulle inte tro det. Du blir tvungen att flytta fram allt vector-innehåll ett snäpp för att ge plats åt elementet i början. Det står en del om STL på http://www.devx.com/upload/free/features/vcdj/2000/06jun00/bw0600/bw0600-1.asp
Där står det en hel del om vad de olika typerna är bra för. Kolla gärna lite om gamla traditionella vektorer och länkade listor. De ger ledtrådar om hur "vector" och "list" fungerar.

Vad vill du prioritera? Insättningar eller sökning? Ge ett typiskt scenario, typ:

"Vid uppstart, lägg in 1000 element i <containern> (vad det nu blir för typ).

Vid körning, cirka var 5:e minut ska jag söka snabbast möjligt. Jag bedömer att man i 90% av fallen hittar elementet. Annars ska det läggas till. osv..."

Har du något behov av sortering?

En hashtabell är bra om du är ute efter den snabba sökningen, men det inte i STL.

En annan sak, du gör:<font size="1" face="Verdana, Arial, Helvetica, sans-serif">Kod:<font size="1" face="Verdana, Arial, Helvetica, sans-serif" color="#666600">for(y=x.begin(); y != x.end(); y++)Det farliga här är "y++". Det innebär att en kopia av y görs (eftersom den är vad som ska returneras). Sedan körs operatorn ++. Kopian slängs i ditt fall bort. För en inbyggd datatyp (int, char, ...) är detta helt ok - då optimerar kompilatorn bort copy constructorn. Men du kan inte anta att så är fallet för en klass. Skriv istället ++y.<font size="1" face="Verdana, Arial, Helvetica, sans-serif">Kod:<font size="1" face="Verdana, Arial, Helvetica, sans-serif" color="#666600">for(y=x.begin(); y != x.end(); ++y)Det är en god tumregel att alltid använda pre-inkrementering (++VARIABEL) i såna här fall.

for(y=x.begin(); y != x.end(); y++)
--------------------------------------------------------------------------------
Det farliga här är "y++". Det innebär att en kopia av y görs (eftersom den är vad som ska returneras). Sedan körs operatorn ++. Kopian slängs i ditt fall bort. För en inbyggd datatyp (int, char, ...) är detta helt ok - då optimerar kompilatorn bort copy constructorn. Men du kan inte anta att så är fallet för en klass. Skriv istället ++y.Kod:
--------------------------------------------------------------------------------
for(y=x.begin(); y != x.end(); ++y)

for(y=x.begin(); y != x.end(); y++)
eller
for(y=x.begin(); y != x.end(); ++y)

y++ : det gamma värdet används sedan görs y = y + 1

++y : y = y + 1 och sedan används värdet

Hur kan kopilatorn optimera bort i det andra fallet ?

// BeatBox

y++ och ++y... i båda fallen returneras ju innehållet i y väl?

Meningen är väl att jag ska ha typ 10000 - 20000 argument i denna datatyp. sorterad... nä, det behövs ju inte fast det hade varit bäst. Har tänkt på en hash, men slutade pilla på det då KCC kompilatorn inte hade stöd för STL:ernas.

Sökning är viktigare än insert, det är bara det att optimering på båda ställena hade varit bra.

Inte så insatt i hashning men får väl sätta mig och läsa på idag då eftersom det kommer att göras ca: 100 sökningar i sekunden, eller det görs det nu eftersom den inte hinner med mer... och ja... finns inte elementet så ska det in i listan (och dessa element går inte att förskapa så att jag kan skapa dem initialt tyvärr)