Vector ( std::vector<T>) är ett standard C++ generiskt programmeringsmönster som implementerar en dynamisk array .
Mallen vectorfinns i rubrikfilen <vector>. Liksom alla standardkomponenter finns den i std . Detta gränssnitt emulerar driften av en standard C -matris (till exempel snabb slumpmässig åtkomst till element), såväl som några ytterligare funktioner, såsom automatisk storleksändring av en vektor när element infogas eller tas bort.
Alla element i en vektor måste vara av samma typ. Till exempel kan du inte lagra char- och int- data tillsammans i samma vektorinstans. Klassen vector har en standarduppsättning metoder för att komma åt element, lägga till och ta bort element och få antalet element att lagra.
En vektor kan initieras med vilken typ som helst som har en kopieringskonstruktor och är definierad operator=och uppfyller följande villkor [1] :
| Uttryck | returtyp | Skick |
|---|---|---|
| t = u | T& | tlikvärdigu |
| T(t) | tlikvärdigT(t) | |
| T(u) | ulikvärdigT(u) | |
| &u | const T* | visar adressu |
| t.~T() |
Här T , är den typ med vilken vektorn initieras, t är en variabel av typen T, u är en variabel av typen (eventuellt const) T.
Till exempel:
vektor < int > myVector ; // En tom vektor av element av typen int vektor < float > myVector ( 10 ); // En vektor med 10 flyter vektor < char > myVector ( 5 , ' ' ); // Vektor bestående av 5 mellanslag klass T { ... }; int n = 10 ; vektor < T > myVector ( n ); // Vektor av 10 element av anpassad typ TEtt enskilt element i en vektor kan nås med de operationer som beskrivs i tabellen nedan. Enligt C- och C++- konventionen har det första elementet index 0, och det sista elementet har index size() - 1[2] .
| Uttryck | returtyp | Gränskontroll? |
|---|---|---|
| v.at(i) | T&eller const T&för element i | Att kasta ett undantag är möjligtout_of_range |
| v[i] | T&eller const T&för element i | Odefinierat beteende näri >= v.size() |
| v.front() | T&eller const T&för det första elementet | Odefinierat beteende närv.empty() == true |
| v.back() | T&eller const T&för det sista elementet | Odefinierat beteende närv.empty() == true |
Where v är ett objekt av typen (möjligen const) vector<T>, och i är indexet för det nödvändiga elementet i vektorn.
En klass vector är en behållare. Enligt C++-standarden måste alla behållare innehålla metoderna begin(), end(), size(), max_size(), empty()och swap().
Nedan följer en kort lista över tillgängliga metoder med en beskrivning och en indikation på komplexitet .
| Metod | Beskrivning | Komplexitet | |
|---|---|---|---|
| Konstruktörer | vector::vector | Standardkonstruktorn. Tar inga argument, skapar en ny vektorinstans | O(1)(uppträder i konstant tid) |
| vector::vector(const vector& c) | Standardkopieringskonstruktören. Skapar en kopia av vektornc | O(n)(uppträder i linjär tid proportionell mot vektorns storlek c) | |
| vector::vector(size_type n, const T& val = T()) | Skapar en vektor med nobjekt. Om valde deklareras kommer vart och ett av dessa objekt att initieras med sitt värde; annars kommer objekten att få ett standardkonstruktorvärde av typen T. | O(n) | |
| vector::vector(input_iterator start, input_iterator end) | Skapar en vektor av element mellan startochend | O(n) | |
| Förstörare | vector::~vector | Förstör vektorn och dess element | |
| Operatörer | vector::operator= | Kopierar värdet av en vektor till en annan. | O(n) |
| vector::operator== | Jämförelse av två vektorer | O(n) | |
| Tillgång till element |
vector::at | Åtkomst till ett element med kontroll utanför gränserna | O(1) |
| vector::operator[] | Tillgång till ett specifikt element | O(1) | |
| vector::front | Åtkomst till det första elementet | O(1) | |
| vector::back | Åtkomst till det sista elementet | O(1) | |
| Iteratorer | vector::begin | Returnerar en iterator till det första elementet i vektorn | O(1) |
| vector::end | Returnerar en iterator efter det sista elementet i vektorn | O(1) | |
| vector::rbegin | Återgår reverse_iteratortill slutet av den aktuella vektorn. | O(1) | |
| vector::rend | Återgår reverse_iteratortill början av vektorn. | O(1) | |
| Arbeta med vektorstorlek |
vector::empty | Returnerar trueom vektorn är tom | O(1) |
| vector::size | Returnerar antalet element i vektorn | O(1) | |
| vector::max_size | Returnerar det högsta möjliga antalet element i en vektor | O(1) | |
| vector::reserve | Ställer in minsta möjliga antal element i en vektor | O(n) | |
| vector::capacity | Returnerar antalet element som vektorn kan innehålla innan den behöver allokera mer utrymme. | O(1) | |
| vector::shrink_to_fit | Minskar mängden använt minne genom att frigöra oanvänt minne ( C++11 ) | O(1) | |
| Modifierare | vector::clear | Tar bort alla element i vektorn | O(n) |
| vector::insert | Infoga element i en vektor | Insättning i slutet, förutsatt att minnet inte kommer att omfördelas - O(1), till en godtycklig plats -O(n) | |
| vector::erase | Tar bort de angivna vektorelementen (ett eller flera) | O(n) | |
| vector::push_back | Infoga ett element i slutet av en vektor | O(1) | |
| vector::pop_back | Ta bort det sista elementet i vektorn | O(1) | |
| vector::resize | Ändrar storleken på vektorn med den givna mängden | O(n) | |
| vector::swap | Byt innehållet i två vektorer | O(1) | |
| Andra metoder | vector::assign | Associerar givna värden med en vektor | O(n), om den önskade vektorstorleken är inställd, O(n*log(n))vid omallokering av minne |
| vector::get_allocator | Returnerar allokatorn som används för att allokera minne | O(1) |
Förutom de direkta elementåtkomstfunktionerna som beskrivs ovan, kan elementen i en vektor nås med iteratorer .
Iteratorer används vanligtvis i par, varav en används för att indikera den aktuella iterationen, och den andra används för att indikera slutet av behållaren. Iteratorer skapas med standardmetoder begin()som end(). Funktionen begin()returnerar en pekare till det första elementet och returnerar en pekare till ett end() imaginärt icke-existerande element efter det sista.
Vektorn använder den mest funktionsrika iteratortypen, RandomAccessIterator (random access iterator), som låter dig korsa behållaren i valfri ordning, samt ändra innehållet i vektorn under traverseringsprocessen. Men om vektorn ändras kan iteratorn bli ogiltig.
Ett exempel på att beräkna summan av vektorelement med iteratorer:
#include <iostream> #inkludera <vektor> #inkludera <iterator> använder namnutrymme std ; int main () { vektor < int > vektorn ; vektor < int >:: iterator the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { the_vector . push_back ( i ); } int totalt = 0 ; the_iterator = the_vector . börja (); while ( the_iterator != the_vector . end ()) { totalt += * the_iterator ++ ; } cout << "summa= " << totalt << endl ; returnera 0 ; } vektor < int > vektorn ; vektor < int >:: iterator the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { the_vector . push_back ( i ); } int totalt = 0 ; the_iterator = the_vector . börja (); while ( the_iterator != the_vector . end ()) { totalt += * the_iterator ; /* Observera att elementet kan nås genom att referera till iteratorn */ ++ the_iterator ; } cout << "Total=" << totalt << endl ;Resultat:
Totalt=45
En typisk vektorimplementering är en pekare till en dynamisk array. Storleken på en vektor är det faktiska antalet element, och storleken är mängden minne som den använder.
Om, när nya element infogas i en vektor, dess storlek blir större än dess volym, omfördelas minnet. Vanligtvis kommer detta att få vektorn att allokera ett nytt lagringsområde, flytta elementen och frigöra gamla områden till den nya minnesplatsen.
Eftersom adresserna till element ändras under denna process, kan alla referenser eller iteratorer av element i vektorn bli ogiltiga. Att använda ogiltiga referenser resulterar i odefinierat beteende. Exempel:
#inkludera <vektor> int main () { std :: vektor < int > v ( 1 ); // Skapa en vektor med ett int-element vars värde är 0 int & first = * v . börja (); // Skapa en länk till det första elementet v . infoga ( v . slut (), v . kapacitet (), 0 ); // Lägg till nya element int i = first ; // Odefinierat beteende. Länken kanske inte är giltig }Metoden reserve()används för att förhindra onödig minnesomfördelning. Efter anrop reserve(n)är storleken på vektorn garanterat inte mindre än n. Exempel:
#inkludera <vektor> int main () { std :: vektor < int > v ( 1 ); // Skapa en vektor som består av ett enda element av typen int vars värde är 0 v . reserv ( 10 ); // Reservera utrymme int & first = * v . börja (); // Skapa en länk till det första elementet v . infoga ( v . slut (), 5 , 0 ); // Lägga till element till vektorn int i = first ; // OK eftersom det inte fanns någon omfördelning av minne }En vektor bibehåller en specifik ordning av sina element, så att när ett nytt element infogas i början eller i mitten av vektorn, flyttas efterföljande element bakåt vad gäller deras tilldelningsoperator och kopieringskonstruktor. Därför ogiltigförklaras elementreferenser och iteratorer efter insättningspunkten. Exempel:
#inkludera <vektor> int main () { std :: vektor < int > v ( 2 ); // Skapa en vektor som består av två element av typen Int // Skapa referenser till båda elementen int & first = v . front (); int & last = v . tillbaka (); v . infoga ( v . börja () + 1 , 1 , 1 ); // Lägg till nya element i mitten av vektorn int i = first ; // Odefinierat beteende om en infogning orsakade en omallokering int j = last ; // Odefinierat beteende, enligt C++-standarden, §23.2.4.3/1 }C++-standardbiblioteket definierar en vektormallspecialisering för bool. Enligt specialiseringen måste vektorn packa elementen så att varje element av typen bооlbara använder en bit minne [3] . Detta kallas en bugg av många [4] [5] eftersom det inte överensstämmer med kraven för C++ Standard Library-vector<bool> behållaren . Till exempel måste behållaren vara sann för typ T. Detta är inte fallet med c , som är en platshållare som kan konverteras till [6] . Ger dessutom inte vid hänvisning. Det finns en överenskommelse mellan C++-standardiseringskommittén och biblioteksutvecklingsteamet om att det ska fasas ut och sedan tas bort från standardbiblioteket och funktionaliteten kommer att återställas, men under ett annat namn. [7]<T>::referencelvaluevector<bool>::referenceboolvector<bool>::iteratorbool&vector<bool>
C++- program som använder en vektor måste inkludera en rubrikfil <vector>:
#inkludera <vektor> // Efter det kan du initiera variabeln std :: vector < T > myVector ;Här T - typen av data som kommer att lagras i behållaren, och myVector - variabeln som kommer att användas. Tkan vara vilken datatyp som helst, inklusive en användardefinierad datatyp.
I C och C++ är en array data i angränsande minnesblock. Varje block tilldelas sedan ett index, och innehållet i varje block kan hittas genom att känna till dess index. Alla element i en array måste vara av samma typ.
En vektor liknar en dynamisk array, men en vektor kan ändra storlek på sig själv. Dessutom finns det inget behov av att manuellt frigöra minne.
Eftersom elementen i en vektor lagras angränsande, kan adressen för det första elementet i vektorn skickas till funktionen som en array (pekare till det första elementet). Följande exempel illustrerar hur en vektor kan användas med C-standardbiblioteksfunktionerna memcpyoch printf:
#include <cstring> // memcpy #inkludera <vektor> #include <cstdio> // printf int main () { använder namnutrymme std ; const char arr [] = "1234567890" ; // Skapa en vektor med 11 '\0' vektor < char > vec ( sizeof arr ); // Kopiera 11 element av typen 'char' till en vektor memcpy ( vec . data (), arr , sizeof arr ); // Skriver ut "1234567890" printf ( "%s" , vec . data ()); }Observera att användningen av memcpyoch printfavråds, till förmån för säkrare alternativ från C++ Standard Library
Följande exempel visar olika tekniker som involverar en vektor och C++-standardbiblioteksalgoritmer , som att blanda, sortera, hitta det största elementet och ta bort från en vektor med radera-ta bort idiomet.
#include <iostream> #inkludera <vektor> #inkludera <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound #include <functional> // greater, bind2nd // Används för bekvämlighet. I riktiga program använd med försiktighet genom att använda namnrymden std ; int main () { int arr [ 4 ] = { 1 , 2 , 3 , 4 }; // Initiera en vektor med hjälp av en arrayvektor < int > numbers ( arr , arr + 4 ) ; // Lägg till tal till talvektorn . push_back ( 5 ); siffror . push_back ( 6 ); siffror . push_back ( 7 ); siffror . push_back ( 8 ); // Nu ser vektorn ut så här: {1, 2, 3, 4, 5, 6, 7, 8} // Blanda slumpmässigt elementen random_shuffle ( nummer . börjar (), tal . slut ()); // Få det maximala elementet, komplexitet O(n) vektor < int >:: const_iterator största = max_element ( tal . börjar (), tal . slut () ); cout << "största elementet" << * största << endl ; cout << "Index för detta element" << största - siffror . börja () << endl ; // Sortera elementen, komplexitet O(n log n) sortera ( siffror . börjar (), siffror . slut ()); // Hitta positionen för talet 5 i vektorn, komplexitet O(log n) vektor < int >:: const_iterator fem = nedre_gräns ( tal . börjar (), tal . slut (), 5 ); cout << "Siffran 5 är vid index" << fem - siffror . börja () << endl ; // Ta bort alla element som är större än 4 siffror . radera ( remove_if ( siffror . börjar (), siffror . slut (), bind2nd ( större < int > (), 4 )), siffror . slut () ); // Skriv ut resten för ( vektor < int >:: const_iterator it = tal . börja (); it != tal . slut (); ++ it ) { cout << * it << ' ' ; } returnera 0 ; }Utgången kommer att innehålla:
Största element 8
Indexet för detta element är 6 (implementeringsberoende)
Siffran 5 finns under index 4
1 2 3 4
Ett exempel på en 2-dimensionell dynamisk vektor, samt ett exempel på att komma åt och ändra den
typedef std :: vektor < std :: vektor < int > > pxMP ; void funktion () { int sizeX , sizeY ; // ange storleken i farten. pxMP pxMap ( sizeX , std :: vektor < int > ( sizeY )); // array av storlek X/Y pixlar 0,1. pxMap [ 0 ][ 5 ] = 1 ; /* tillgång */ // ta bort vänster och höger kolumner i pxMap . pop_back (); pxMap . radera ( pxMap.begin ( ) ); // ta bort de övre och nedre raden från alla kolumner, skapa först några verktyg för detta: std :: vektor < std :: vektor < int > >:: iterator iterlvl2 ; // iterator för den andra dimensionen. std :: vektor < int >:: iterator iterlvl1 ; // iterator för den första dimensionen // Gå djupt för ( iterlvl2 = pxMap . begin (); iterlvl2 != pxMap . end (); iterlvl2 ++ ) { iterlvl1 = ( * iterlvl2 ). börja (); // Endast i demonstrationssyfte ( * iterlvl2 ). pop_back (); ( * iterlvl2 ). radera (( * iterlvl2 ) .begin ()); // Var är vi? storlekY = ( * iterlvl2 ). storlek (); // Ställ in storlek Y medan vi är på den här nivån. Då kommer vi inte att kunna göra det } }Ett exempel på en endimensionell dynamisk vektor som sorterar och tar bort dubbletter:
#inkludera <vektor> #inkludera <sträng> #include <algorithm> // För att använda std::sort, std::unika algoritmer int main () { std :: vektor < std :: sträng > v_str ; //Tom 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"} //Sortera alla element i vektorn std :: sort ( v_str . begin (), v_str . end ()); //Resultat av vektorsortering: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"} // Ta bort dubbletter v_str . radera ( std :: unik ( v_str . börjar (), v_str . slut () ), v_str . slut () ); //Resultat av att ta bort dubbletter: {"aa","bb","dd","xx","zz"} return 0 ; }