I datalogi angiver en vektor en beholder med ordnede elementer, der er tilgængelige med indekser, hvis størrelse er dynamisk: den opdateres automatisk, når elementer tilføjes eller slettes. Vektorer findes i mange programmeringssprog , herunder C ++ og Java . De medtages derefter i bibliotekerne, og brugeren behøver ikke at programmere et.
På objektsprog er vektorklassen generelt polymorf , det vil sige, at det er muligt at bruge den med enhver form for objekt.
Eksempel på håndtering af 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, der bruges her, er objektet vector(inkluderet i STL ). Det vectorer en model. Den kan derfor bruges med enhver type. For eksempel skal chardu skrive for at lave en vektor af vector<char>.
Den hukommelsesallokering af en vektor udføres generelt ved at fordoble sin kapacitet, når dens størrelse (antallet af elementer) er lig sin kapacitet (antallet af bytes allokeret). For at se dets kapacitet udvikle sig vectorhar metoderne 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 nedenstående graf, der viser kapacitet versus størrelse, kan det ses, at med vectorkapaciteten stiger med ca. 50% hver gang størrelse og kapacitet er ens. Hvis dette tal er for lavt, vil der være for mange genallokeringer. Hvis det er for højt, tager det for meget hukommelse. I begge tilfælde kan dette medføre tab af ydeevne.
Vektoren har mange fordele i forhold til et simpelt array , primært på grund af dynamisk hukommelsesallokering:
I nogle tilfælde er arrays imidlertid lettere at bruge, især når der oprettes matricer. Det er faktisk nødvendigt at oprette en vektor af vektorer. Konsekvensen er, at vi ikke garanteres at få den samme størrelse af kolonner. For at afhjælpe dette skal du oprette komplekse klasser manuelt. Derudover skal udvikleren på sprog, der ikke har markører, være tilfreds med de standarder, der er foreslået. Endelig er størrelsen og kapaciteten af en vektor ikke nødvendigvis ens. Hukommelse kan derfor bruges unødigt.
Vektoren bruges især, når man ikke på forhånd ved, hvor mange data den skal indeholde. Det er også nyttigt ikke at omdefinere en matrix for at blive genbrugt direkte. Hvis vi overvejer eksemplet på flettsortering , modtager en funktion som argument to arrays med to heltal hver. Med et array skal funktionen oprette et nyt array, mens det med to vektorer er nok bare at kopiere dataene fra den første i den anden og derefter slette den første vektor.
En anden applikation er, når man let vil kopiere data ved at stable dem. Med et klassisk array skal du bruge et heltal, der øges med 1 for hver tilføjelse. I C ++ giver 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); }Endelig er vektoren generelt meget alsidig. Det er i stand til at blive brugt som en stak, liste eller kø. Specialiserede containere er dog mere optimerede til disse opgaver.
En vektor kan generelt gives følgende instruktioner:
De kan også returnere adresser eller spor:
Derudover understøtter nogle implementeringer andre funktioner til at sortere vektoren eller formatere den for eksempel. Der er også betingede instruktioner, der gør det muligt at forkorte koden ved at fjerne en instruktion if(instruktionen replace_if()med vectori C ++, erstatter et element, hvis et predikat er markeret).
Det er nemt at oprette din egen vektor med markører . Her er et eksempel i C ++, hvor vektoren manipulerer heltal. Vektorklassen, der ikke præsenteres her i sin helhed, består af to felter: en pheltalsmarkør, der peger på starten af den hukommelsesblok, der er tildelt, og et heltal, nder registrerer mængden af data indeholdt i vektoren. I dette eksempel omplaceres hukommelsen hver gang du sletter eller tilføjer. Kun metoderne i denne klasse vil blive eksponeret.
Du behøver ikke oprette en klasse for at oprette din egen vektor. På den anden side er det nødvendigt at have adgang til markører eller referencer . Andre sprog, såsom C eller Pascal, kan derfor være egnede.
Den konstruktør , der udføres, når vektoren skabt initialisere markøren til en adresse , og indstiller det antal data til 0. destructor , der udføres, når vektoren ødelægges frigør hukommelsen blok, der er allokeret til vektoren for at undgå data lækager hukommelse . Konstruktøren tildeler kun en byte hukommelse for at have en referencehukommelsesblok, som markøren p kan adressere. Denne blok kan derefter forstørres med "omfordel" -metoden til at indeholde flere tal. Det bør også tilføje en linje til brug stdlib.h , som giver adgang til realloc(), malloc()og free()(ikke til stede her).
vecteur(){ n = 0; p = malloc(1); } ~vecteur(){ free(p); }"Reallocate" -metoden er ansvarlig for at allokere antallet af byte, der er nødvendige for, at vektoren indeholder dens data med den funktion, realloc()der forstørrer eller reducerer den allokerede hukommelsesblok. Størrelsen på et heltal, der er fast, er det muligt at erklære en konstant taille_intfor ikke at skulle skrive sizeof(int).
void reallouer(){ p = (int *) realloc(p, sizeof(int) * n); }Metoden "tilføj" kan stable et helt tal meget enkelt: det er tilstrækkeligt at øge antallet af data, hvilket vil forstørre vektoren. Så skriv bare til denne nye placering. En anden lignende metode kan pope et heltal, hvilket reducerer antallet af byte, der vil blive allokeret, hvilket frigør (ødelægger) det sidste element i vektoren.
void ajouter(int var) { n++; reallouer(); *(p + n - 1) = var; } void supprimer(){ n--; reallouer(); }For at læse og ændre en værdi fra et indeks er alt hvad du skal gøre, at bruge den klassiske markørsyntaks. I dette eksempel skal indekset være mellem 0 og antallet af data minus en (som i et klassisk array i C ++). For at undgå overløbsfejl sec(int index)kontrollerer en funktion , at indekset har den rigtige 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; }Det er muligt at oprette de début()og metoder, fin()der returnerer indekset for det første og for elementet efter det sidste for forlet at oprette sløjfer til at vise vektoren. Funktionen fin()kan bruges til at kende størrelsen på vektoren. Generelt bruges begreberne begynder og slutter mere. Der er variationer for at få det sidste element til at skabe sløjfer i den modsatte 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; }Denne metode er let at implementere; det kaldes ofte swap på engelsk. For ikke at miste data er en buffervariabel (kaldet c i dette tilfælde) nødvendig.
void echanger(int i1, int i2) { int c = lire(i1); modifier(lire(i2), i1); modifier(c, i2); }