Vector ( std::vector<T>) er et standard C++ generisk programmeringsmønster, der implementerer et dynamisk array .
Skabelonen vectorer placeret i header-filen <vector>. Som alle standardkomponenter er den placeret i std . Denne grænseflade emulerer driften af et standard C -array (f.eks. hurtig tilfældig adgang til elementer), såvel som nogle yderligere funktioner, såsom automatisk ændring af størrelsen af en vektor, når elementer indsættes eller fjernes.
Alle elementer i en vektor skal være af samme type. For eksempel kan du ikke gemme char- og int -data sammen i den samme vektorinstans. Klassen vector har et standardsæt af metoder til at få adgang til elementer, tilføje og fjerne elementer og få antallet af elementer til at gemme.
En vektor kan initialiseres med enhver type, der har en kopikonstruktør og er defineret operator=og opfylder følgende betingelser [1] :
| Udtryk | returtype | Tilstand |
|---|---|---|
| t = u | T& | ttilsvarendeu |
| T(t) | ttilsvarendeT(t) | |
| T(u) | utilsvarendeT(u) | |
| &u | const T* | viser adresseu |
| t.~T() |
Her T er typen, som vektoren initialiseres med, t er en variabel af typen T, u er en variabel af typen (muligvis const) T.
For eksempel:
vektor < int > myVector ; // En tom vektor af elementer af typen int vektor < float > myVector ( 10 ); // En vektor med 10 flyder vektor < char > myVector ( 5 , ' ' ); // Vektor bestående af 5 mellemrum klasse T { ... }; int n = 10 ; vektor < T > minVektor ( n ); // Vektor af 10 elementer af brugerdefineret type TEt individuelt element i en vektor kan tilgås ved hjælp af operationerne beskrevet i tabellen nedenfor. Ifølge C- og C++- konventionen har det første element indeks 0, og det sidste element har indeks size() - 1[2] .
| Udtryk | returtype | Grænsekontrol? |
|---|---|---|
| v.at(i) | T&eller const T&for element i | Det er muligt at smide en undtagelseout_of_range |
| v[i] | T&eller const T&for element i | Udefineret adfærd hvornåri >= v.size() |
| v.front() | T&eller const T&for det første element | Udefineret adfærd hvornårv.empty() == true |
| v.back() | T&eller const T&for det sidste element | Udefineret adfærd hvornårv.empty() == true |
Hvor v er et objekt af typen (muligvis const) vector<T>, og i er indekset for det nødvendige element i vektoren.
En klasse vector er en beholder. Ifølge C++-standarden skal enhver container indeholde metoder begin(), end(), size(), max_size(), empty(), og swap().
Nedenfor er en kort liste over tilgængelige metoder med en beskrivelse og en angivelse af kompleksitet .
| Metode | Beskrivelse | Kompleksitet | |
|---|---|---|---|
| Konstruktører | vector::vector | Standardkonstruktøren. Tager ingen argumenter, opretter en ny vektorinstans | O(1)(optræder konstant) |
| vector::vector(const vector& c) | Standard kopikonstruktør. Opretter en kopi af vektorenc | O(n)(optræder i lineær tid proportional med størrelsen af vektoren c) | |
| vector::vector(size_type n, const T& val = T()) | Opretter en vektor med nobjekter. Hvis valde erklæres, vil hvert af disse objekter blive initialiseret med sin værdi; ellers vil objekterne få en standard konstruktørværdi af typen T. | O(n) | |
| vector::vector(input_iterator start, input_iterator end) | Opretter en vektor af elementer mellem startogend | O(n) | |
| Destruktor | vector::~vector | Ødelægger vektoren og dens elementer | |
| Operatører | vector::operator= | Kopierer værdien af en vektor til en anden. | O(n) |
| vector::operator== | Sammenligning af to vektorer | O(n) | |
| Adgang til elementer |
vector::at | Adgang til et element med out-of-bound-kontrol | O(1) |
| vector::operator[] | Adgang til et bestemt element | O(1) | |
| vector::front | Adgang til det første element | O(1) | |
| vector::back | Adgang til det sidste element | O(1) | |
| Iteratorer | vector::begin | Returnerer en iterator til det første element i vektoren | O(1) |
| vector::end | Returnerer en iterator efter det sidste element i vektoren | O(1) | |
| vector::rbegin | Vender tilbage reverse_iteratortil slutningen af den aktuelle vektor. | O(1) | |
| vector::rend | Vender tilbage reverse_iteratortil begyndelsen af vektoren. | O(1) | |
| Arbejder med vektorstørrelse |
vector::empty | Returnerer true, hvis vektoren er tom | O(1) |
| vector::size | Returnerer antallet af elementer i vektoren | O(1) | |
| vector::max_size | Returnerer det maksimalt mulige antal elementer i en vektor | O(1) | |
| vector::reserve | Indstiller det mindst mulige antal elementer i en vektor | O(n) | |
| vector::capacity | Returnerer antallet af elementer, vektoren kan indeholde, før den skal tildele mere plads. | O(1) | |
| vector::shrink_to_fit | Reducerer mængden af brugt hukommelse ved at frigøre ubrugt hukommelse ( C++11 ) | O(1) | |
| Modifikatorer | vector::clear | Fjerner alle elementer i vektoren | O(n) |
| vector::insert | Indsættelse af elementer i en vektor | Indsættelse i slutningen, forudsat at hukommelsen ikke omfordeles - O(1), til et vilkårligt sted -O(n) | |
| vector::erase | Fjerner de angivne vektorelementer (et eller flere) | O(n) | |
| vector::push_back | Indsættelse af et element i slutningen af en vektor | O(1) | |
| vector::pop_back | Fjern sidste element af vektor | O(1) | |
| vector::resize | Ændrer størrelsen af vektoren med den givne mængde | O(n) | |
| vector::swap | Skift indholdet af to vektorer | O(1) | |
| Andre metoder | vector::assign | Forbinder givne værdier med en vektor | O(n), hvis den ønskede vektorstørrelse er indstillet, O(n*log(n))ved omallokering af hukommelse |
| vector::get_allocator | Returnerer den allokator , der bruges til at allokere hukommelse | O(1) |
Ud over de direkte elementadgangsfunktioner beskrevet ovenfor, kan elementerne i en vektor tilgås ved hjælp af iteratorer .
Iteratorer bruges normalt i par, hvoraf den ene bruges til at angive den aktuelle iteration, og den anden bruges til at angive slutningen af beholderen. Iteratorer oprettes ved hjælp af standardmetoder som begin()f.eks end(). Funktionen begin()returnerer en pointer til det første element og returnerer en pointer til et end() imaginært ikke-eksisterende element efter det sidste.
Vektoren bruger den mest funktionsrige iteratortype, RandomAccessIterator (random access iterator), som giver dig mulighed for at krydse beholderen i en hvilken som helst rækkefølge, samt ændre indholdet af vektoren i traverseringsprocessen. Men hvis vektoren ændres, kan iteratoren blive ugyldig.
Et eksempel på beregning af summen af vektorelementer ved hjælp af iteratorer:
#include <iostream> #inkluder <vektor> #inkluder <iterator> bruger navneområde std ; int main () { vektor < int > vektoren ; vektor < int >:: iterator the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { vektoren . push_back ( i ); } int total = 0 ; the_iterator = the_vector . begynde (); while ( the_iterator != the_vector . end ()) { total += * the_iterator ++ ; } cout << "summa= " << total << endl ; returnere 0 ; } vektor < int > vektoren ; vektor < int >:: iterator the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { vektoren . push_back ( i ); } int total = 0 ; the_iterator = the_vector . begynde (); while ( the_iterator != the_vector . end ()) { total += * the_iterator ; /* Bemærk, at elementet kan tilgås ved at dereferere iteratoren */ ++ the_iterator ; } cout << "Total=" << total << endl ;Resultat: I
alt=45
En typisk vektorimplementering er en pointer til et dynamisk array. Størrelsen af en vektor er det faktiske antal elementer, og størrelsen er mængden af hukommelse, den bruger.
Hvis, når der indsættes nye elementer i en vektor, dens størrelse bliver større end dens volumen, omfordeles hukommelsen. Typisk vil dette få vektoren til at allokere et nyt lagerområde, flytte elementerne og frigøre gamle områder til den nye hukommelsesplacering.
Fordi adresserne på elementer ændres under denne proces, kan alle referencer eller iteratorer af elementer i vektoren blive ugyldige. Brug af ugyldige referencer resulterer i udefineret adfærd. Eksempel:
#inkluder <vektor> int main () { std :: vektor < int > v ( 1 ); // Opret en vektor med ét int-element, hvis værdi er 0 int & first = * v . begynde (); // Opret et link til det første element v . indsætte ( v . ende (), v . kapacitet (), 0 ); // Tilføj nye elementer int i = først ; // Udefineret adfærd. Linket er muligvis ikke gyldigt }Metoden reserve()bruges til at forhindre unødvendig hukommelsesomfordeling. Efter opkald reserve(n)er størrelsen af vektoren garanteret ikke mindre end n. Eksempel:
#inkluder <vektor> int main () { std :: vektor < int > v ( 1 ); // Opret en vektor bestående af et enkelt element af typen int, hvis værdi er 0 v . reserve ( 10 ); // Reserve plads int & first = * v . begynde (); // Opret et link til det første element v . indsætte ( v . ende (), 5 , 0 ); // Tilføjelse af elementer til vektoren int i = first ; // OK, da der ikke var nogen omallokering af hukommelse }En vektor opretholder en specifik rækkefølge af sine elementer, således at når et nyt element indsættes i begyndelsen eller i midten af vektoren, flyttes efterfølgende elementer bagud i forhold til deres tildelingsoperator og kopikonstruktør. Derfor er elementreferencer og iteratorer efter indsættelsespunktet ugyldige. Eksempel:
#inkluder <vektor> int main () { std :: vektor < int > v ( 2 ); // Opret en vektor bestående af to elementer af typen Int // Opret referencer til begge elementer int & first = v . foran (); int & sidste = v . tilbage (); v . indsætte ( v . begynde () + 1 , 1 , 1 ); // Tilføj nye elementer til midten af vektoren int i = first ; // Udefineret adfærd, hvis en indsættelse forårsagede en omallokering int j = last ; // Udefineret adfærd, i henhold til C++-standarden, §23.2.4.3/1 }C++ Standardbiblioteket definerer en vektorskabelonspecialisering for bool. Ifølge specialiseringen skal vektoren pakke elementerne, så hvert element af typen bооlkun bruger én bit hukommelse [3] . Dette kaldes en fejl af mange [4] [5] , fordi det ikke overholder kravene i C++ Standard Library-vector<bool> containeren . For eksempel skal beholderen være sand for type T. Dette er ikke tilfældet med c , som er en pladsholder , der kan konverteres til [6] . Ud over, giver ikke på dereference. Der er en aftale mellem C++ standardiseringsudvalget og biblioteksudviklingsteamet om, at det skal forældes og derefter fjernes fra standardbiblioteket, og funktionaliteten vil blive gendannet, men under et andet navn. [7]<T>::referencelvaluevector<bool>::referenceboolvector<bool>::iteratorbool&vector<bool>
C++- programmer , der bruger en vektor, skal indeholde en header-fil <vector>:
#inkluder <vektor> // Derefter kan du initialisere variablen std :: vector < T > myVector ;Her T - den type data, der vil blive lagret i containeren, og myVector - den variabel, der vil blive brugt. Tkan være enhver datatype, inklusive en brugerdefineret datatype.
I C og C++ er et array data i sammenhængende hukommelsesblokke. Hver blok tildeles derefter et indeks, og indholdet af hver blok kan findes ved at kende dens indeks. Alle elementer i et array skal være af samme type.
En vektor ligner et dynamisk array, men en vektor kan ændre størrelsen på sig selv. Det er heller ikke nødvendigt at frigøre hukommelse manuelt.
Da elementerne i en vektor er lagret sammenhængende, kan adressen på det første element i vektoren videregives til funktionen som et array (peger til det første element). Følgende eksempel illustrerer, hvordan en vektor kan bruges med C-standardbiblioteksfunktionerne memcpyog printf:
#include <cstring> // memcpy #inkluder <vektor> #include <cstdio> // printf int main () { bruger navneområde std ; const char arr [] = "1234567890" ; // Opret en vektor med 11 '\0' vektor < char > vec ( sizeof arr ); // Kopier 11 elementer af typen 'char' ind i en vektor memcpy ( vec . data (), arr , sizeof arr ); // Udskriver "1234567890" printf ( "%s" , vec . data ()); }Bemærk, at brugen af memcpyog printffrarådes, til fordel for sikrere alternativer fra C++ Standard Library
Det følgende eksempel demonstrerer forskellige teknikker, der involverer en vektor og C++-standardbiblioteksalgoritmer , såsom blande, sortere, finde det største element og slette fra en vektor ved hjælp af slette-fjern-idiomet.
#include <iostream> #inkluder <vektor> #include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound #include <funktionel> // større, bind2nd // Bruges for nemheds skyld. I rigtige programmer, brug med omhu ved at bruge navneområde std ; int main () { int arr [ 4 ] = { 1 , 2 , 3 , 4 }; // Initialiser en vektor ved hjælp af en matrixvektor < int > tal ( arr , arr + 4 ) ; // Tilføj tal til talvektoren . push_back ( 5 ); tal . push_back ( 6 ); tal . push_back ( 7 ); tal . push_back ( 8 ); // Nu ser vektoren sådan ud: {1, 2, 3, 4, 5, 6, 7, 8} // Bland tilfældigt elementerne random_shuffle ( tal . begynde (), tal . slut ()); // Få det maksimale element, kompleksitet O(n) vektor < int >:: const_iterator største = max_element ( tal . begynder (), tal . slut () ); cout << "største element" << * største << endl ; cout << "Indeks for dette element" << største - tal . begynde () << endl ; // Sorter elementerne, kompleksitet O(n log n) sorter ( tal . begynde (), tal . slut ()); // Find positionen af tallet 5 i vektoren, kompleksitet O(log n) vektor < int >:: const_iterator fem = nedre_grænse ( tal . begynder (), tal . slut (), 5 ); cout << "Tallet 5 er ved indeks" << fem - tal . begynde () << endl ; // Fjern alle elementer større end 4 tal . erase ( remove_if ( tal . begynde (), tal . slut (), bind2nd ( større < int > (), 4 )), tal . slut () ); // Udskriv resten for ( vektor < int >:: const_iterator it = tal . begynde (); it != tal . slut (); ++ it ) { cout << * it << ' ' ; } returnere 0 ; }Outputtet vil indeholde:
Største element 8
Indekset for dette element er 6 (implementeringsafhængig)
Tallet 5 er placeret under indekset 4
1 2 3 4
Et eksempel på en 2-dimensionel dynamisk vektor, samt et eksempel på adgang til og ændring af den
typedef std :: vektor < std :: vektor < int > > pxMP ; void funktion () { int størrelseX , størrelseY ; // angiv størrelsen på farten. pxMP pxMap ( sizeX , std :: vektor < int > ( sizeY )); // matrix af størrelse X/Y pixels 0,1. pxMap [ 0 ][ 5 ] = 1 ; /* adgang */ // fjern venstre og højre kolonne af pxMap . pop_back (); pxMap . slet ( pxMap.begin ( ) ); // fjern de øverste og nederste rækker fra alle kolonner, opret først nogle værktøjer til dette: std :: vektor < std :: vektor < int > >:: iterator iterlvl2 ; // iterator for den anden dimension. std :: vektor < int >:: iterator iterlvl1 ; // iterator for den første dimension // Gå dybt for ( iterlvl2 = pxMap . begin (); iterlvl2 != pxMap . end (); iterlvl2 ++ ) { iterlvl1 = ( * iterlvl2 ). begynde (); // Kun til demonstrationsformål ( * iterlvl2 ). pop_back (); ( * iterlvl2 ). slette (( * iterlvl2 ) .begin ()); // Hvor er vi? størrelseY = ( * iterlvl2 ). størrelse (); // Indstil størrelse Y, mens vi er på dette niveau. Så kan vi ikke gøre det } }Et eksempel på en endimensionel dynamisk vektor, sortering og fjernelse af dubletter:
#inkluder <vektor> #inkluder <streng> #include <algorithm> // For at bruge std::sort, std::unikke algoritmer int main () { std :: vektor < std :: streng > v_str ; //Tøm vektor v_str v_str . push_back ( "zz" ); // {"zz"} v_str . push_back ( "aa" ); // {"zz", "aa"} v_str . push_back ( "bb" ); // {"zz", "aa", "bb"} v_str . push_back ( "aa" ); // {"zz", "aa", "bb", "aa"} v_str . push_back ( "xx" ); // {"zz", "aa", "bb", "aa", "xx"} v_str . push_back ( "dd" ); // {"zz", "aa", "bb", "aa", "xx", "dd"} v_str . push_back ( "xx" ); // {"zz", "aa", "bb", "aa", "xx", "dd", "xx"} //Sorter alle elementer i vektoren std :: sort ( v_str . begin (), v_str ende ()) ; //Resultat af vektorsortering: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"} // Fjern dubletter v_str . erase ( std :: unik ( v_str . start (), v_str . end () ), v_str . end () ); //Resultat af fjernelse af dubletter: {"aa","bb","dd","xx","zz"} return 0 ; }