Vector (datastruktur)

I informatikk betegner en vektor en beholder med ordnede elementer som er tilgjengelige med indekser, hvis størrelse er dynamisk: den oppdateres automatisk når elementer legges til eller slettes. Vektorer finnes i mange programmeringsspråk , inkludert C ++ og Java . De blir deretter inkludert i biblioteker, og brukeren trenger ikke å programmere en.

På objektspråk er vektorklassen generelt polymorf , det vil si at det er mulig å bruke den med alle typer objekter.

Eksempel

Eksempel på håndtering av en vektor i C ++ :

// Lien vers le fichier contenant le vector #include <vector> // Lien pour l'affichage #include <iostream> int main() { vector<int> v; // vector v manipulant des entiers(type int) v.push_back(1); // Empile l'entier 1 v.push_back(2); // Empile l'entier 2 v.pop_back(); // Dépile un élément v.insert(6, v.begin() + 1); // Insère 6 après le premier élément std::cout << v.capacity(); // Affiche 3, le nombre d'éléments }

Vektoren som brukes her er objektet vector(følger med STL ). Det vectorer en modell. Den kan derfor brukes med alle typer. For eksempel, for å lage en vektor av char, må du skrive vector<char>.

Den minnetildeling av en vektor blir vanligvis gjort ved å doble kapasiteten når dens størrelse (antall elementer) er lik dens kapasitet (antall byte tildelt). For å se kapasiteten utvikle seg, vectorhar følgende metoder size()og capacity():

#include <vector> #include <iostream> int main() { std::vector<int> v; for(int i = 0; i < 20; i++) { std::cout << "capacité = " << v.capacity() << " pour une taille de " << v.size() << std::endl; v.push_back(1); } }

Fra grafen nedenfor som viser kapasitet kontra størrelse, kan det sees at med vectorkapasiteten øker med omtrent 50% hver gang størrelse og kapasitet er like. Hvis dette tallet er for lavt, blir det for mange omdisponeringer. Hvis den er for høy, vil den ta opp for mye minne. I begge tilfeller kan dette føre til tap av ytelse.

Fordeler og ulemper

Vektoren har mange fordeler fremfor en enkel matrise , hovedsakelig på grunn av dynamisk minnetildeling:

Det er ikke nødvendig å spesifisere størrelsen på containeren når den blir opprettet;
Innenfor grensene for maskinens ressurser er det mulig å legge til så mange elementer som ønsket til vektoren uten å endre strukturen;
Omvendt er det ikke nødvendig å krympe størrelsen på beholderen når du fjerner gjenstander.
I mange implementeringer kan tilleggsinstruksjoner (for å sortere eller finne et element, for eksempel) spare tid.

I noen tilfeller er det imidlertid lettere å bruke matriser, spesielt når du lager matriser. Det er faktisk nødvendig å lage en vektor med vektorer. Konsekvensen er at vi ikke garanteres å oppnå samme størrelse på kolonner. For å avhjelpe dette må du opprette komplekse klasser manuelt. I tillegg, på språk som ikke har pekepinner, må utvikleren være fornøyd med vektorene som er foreslått som standard. Til slutt er størrelsen og kapasiteten til en vektor ikke nødvendigvis like. Minne kan derfor brukes unødvendig.

bruk

Vektoren brukes hovedsakelig når man ikke på forhånd vet hvor mange data den må inneholde. Det er også nyttig å ikke omdefinere en matrise for å bli gjenbrukt direkte. Hvis vi vurderer eksemplet på flettesortering , mottar en funksjon som argument to matriser med to heltall hver. Med en matrise må funksjonen opprette en ny matrise, mens det med to vektorer vil være nok bare å kopiere dataene til den første i den andre og deretter slette den første vektoren.

Et annet program er når man enkelt vil kopiere data ved å stable dem. Med en klassisk matrise må du bruke et heltall som økes med 1 for hvert tillegg. I C ++ gir dette:

#include <vector> int main() { //Empilement avec un tableau int n = 0; int tab[10]; tab[n++] = 2; // Avec un vecteur vector<int> vec; vec.push_back(2); }

Til slutt er vektoren generelt veldig allsidig. Den kan brukes som en stabel, liste eller kø. Spesialiserte containere er imidlertid mer optimalisert for disse oppgavene.

Primitiver

En vektor kan vanligvis gis følgende instruksjoner:

"Sett inn" for å sette inn et element før det angitte stedet;
"Slett" for å slette et element;
Med "Stack" kan du legge til et element på slutten av vektoren;
"Pop" lar deg slette et element på slutten av vektoren;
"Størrelse" gjør det mulig å kjenne antall elementer i vektoren;
"Les" for å finne ut verdien av det valgte elementet;
"Modify" lar deg justere verdien til det valgte elementet;
"Bytt" for å bytte to ting;
"Maks" for å finne ut maksimumsverdien til vektoren;
"Min" for å finne ut minimumsverdien til vektoren.

De kan også returnere adresser eller ledetråder:

"Start" for å få adressen til det første elementet;
"Slutt" for å få adressen til elementet som følger den siste (for for løkker );
"Søk" for å få adressen til det første matchende elementet.

I tillegg støtter noen implementeringer andre funksjoner for å sortere vektoren eller formatere den for eksempel. Det er også betingede instruksjoner som lar deg forkorte koden ved å fjerne en instruksjon if(instruksjonen replace_if()med vectori C ++, erstatter et element hvis et predikat er merket av).

Eksempel på implementering

Det er enkelt å lage din egen vektor med pekere . Her er et eksempel i C ++ hvor vektoren manipulerer heltall. Vektorklassen, som ikke presenteres her i sin helhet, består av to felt: en pheltallspeker, som peker på begynnelsen til blokken minne som er tildelt, og et heltall nsom registrerer datamengden som finnes i vektoren. I dette eksemplet omdisponeres minne hver gang du sletter eller legger til. Bare metodene i denne klassen blir eksponert.

Du trenger ikke lage en klasse for å lage din egen vektor. På den annen side er det nødvendig å ha tilgang til pekere eller referanser . Andre språk, slik som C eller Pascal, kan derfor være passende.

Den konstruktøren som kjøres når vektoren blir opprettet initialiseres pekeren til en adresse , og angir antallet av data til 0. destructor som kjøres når vektoren blir ødelagt frigjør den hukommelsesblokk som er allokert til vektoren for å unngå at dataene lekkasjer minne . Konstruktøren tildeler bare en byte minne for å ha en referanseminneblokk som pekeren p kan adressere. Denne blokken kan deretter forstørres med "omfordel" -metoden for å inneholde flere tall. Det bør også legge til en linje for å bruke stdlib.h , som gir tilgang til realloc(), malloc()og free()(ikke til stede her).

vecteur(){ n = 0; p = malloc(1); } ~vecteur(){ free(p); }

“Reallocate” -metoden er ansvarlig for å tildele antall byte som er nødvendige for at vektoren skal inneholde dataene med funksjonen realloc()som forstørrer eller reduserer den tildelte minneblokken. Størrelsen på et heltall som er løst, er det mulig å erklære en konstant taille_intfor ikke å måtte skrive sizeof(int).

void reallouer(){ p = (int *) realloc(p, sizeof(int) * n); }

Legg til og fjern

"Legg til" -metoden kan stable et heltall veldig enkelt: det er tilstrekkelig å øke antall data, som vil forstørre vektoren. Så er det bare å skrive til dette nye stedet. En annen lignende metode kan poppe et helt tall, og redusere antall byte som vil bli allokert, noe som frigjør (ødelegger) det siste elementet i vektoren.

void ajouter(int var) { n++; reallouer(); *(p + n - 1) = var; } void supprimer(){ n--; reallouer(); }

Les og rediger

For å lese og endre en verdi fra en indeks, er alt du trenger å gjøre den klassiske pekersyntaxen. I dette eksemplet må indeksen være mellom 0 og antall data minus en (som i en klassisk matrise i C ++). For å unngå overløpsfeil, kontrollerer en funksjon sec(int index)at indeksen har riktig størrelse.

int sec(int i){ return (i>=n) * (n-1) + ((i>-1)&&(i<n)) * i; } int lire(int index){ return *(p + sec(index)); } void modifier(int var, int index){ *(p + sec(index)) = var; }

Posisjonering

Det er mulig å lage début()og og metoder fin()som returnerer indeksen til det første og elementet etter det siste for forenkelt å lage sløyfer for å vise vektoren. Funksjonen fin()kan brukes til å kjenne størrelsen på vektoren. Generelt vilkårene begynne og slutten er mer utbredt. Det er variasjoner for å få det siste elementet til å lage løkker i motsatt retning.

int debut(){ return 0; } int fin(){ return n; } void afficher() { for(int i = debut(); i < fin(); i++) std::cout << lire(i) << endl; } void afficher_taille(){ std::cout << fin() << endl; }

Bytt to ting

Denne metoden er enkel å implementere; det kalles ofte swap på engelsk. For ikke å miste data, er det nødvendig med en buffervariabel (kalt c i dette tilfellet).

void echanger(int i1, int i2) { int c = lire(i1); modifier(lire(i2), i1); modifier(c, i2); }

Se også

Merknader og referanser

Bibliografi

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest og Clifford Stein , Introduksjon til algoritmikk , Dunod ,2002[ detalj av utgaven ] (kap. 17.4, “Dynamiske tabeller”, s. 406-414).