Vector ( std::vector<T>) este un model de programare generic standard C++ care implementează o matrice dinamică .
Șablonul vectorse află în fișierul antet <vector>. Ca toate componentele standard, se află în std . Această interfață emulează funcționarea unui tablou C standard (de exemplu, acces rapid aleatoriu la elemente), precum și unele caracteristici suplimentare, cum ar fi redimensionarea automată a unui vector atunci când elementele sunt inserate sau îndepărtate.
Toate elementele unui vector trebuie să fie de același tip. De exemplu, nu puteți stoca date char și int împreună în aceeași instanță vectorială. Clasa vector are un set standard de metode pentru accesarea elementelor, adăugarea și eliminarea elementelor și obținerea numărului de elemente de stocat.
Un vector poate fi inițializat cu orice tip care are un constructor de copiere și este definit operator=și îndeplinește următoarele condiții [1] :
| Expresie | tip de returnare | Condiție |
|---|---|---|
| t = u | T& | techivalentu |
| T(t) | techivalentT(t) | |
| T(u) | uechivalentT(u) | |
| &u | const T* | arata adresau |
| t.~T() |
Aici T , este tipul cu care vectorul este inițializat, t este o variabilă de tip T, u este o variabilă de tip (eventual const) T.
De exemplu:
vector < int > myVector ; // Un vector gol de elemente de tip int vector < float > myVector ( 10 ); // Un vector de 10 floats vector < char > myVector ( 5 , ' ' ); // Vector format din 5 spații clasa T { ... }; int n = 10 ; vector < T > myVector ( n ); // Vector de 10 elemente de tip personalizat TUn element individual al unui vector poate fi accesat folosind operațiunile descrise în tabelul de mai jos. Prin convenția C și C++ , primul element are index 0, iar ultimul element are index size() - 1[2] .
| Expresie | tip de returnare | Verificare la frontieră? |
|---|---|---|
| v.at(i) | T&sau const T&pentru elementul i | Aruncarea unei excepții este posibilăout_of_range |
| v[i] | T&sau const T&pentru elementul i | Comportament nedefinit cândi >= v.size() |
| v.front() | T&sau const T&pentru primul element | Comportament nedefinit cândv.empty() == true |
| v.back() | T&sau const T&pentru ultimul element | Comportament nedefinit cândv.empty() == true |
Unde v este un obiect de tip (eventual const) vector<T>și i este indexul elementului necesar al vectorului.
O clasă vector este un container. Conform standardului C++, orice container trebuie să conțină metode begin(), end(), size(), max_size(), empty()și swap().
Mai jos este o listă scurtă a metodelor disponibile cu o descriere și o indicație a complexității .
| Metodă | Descriere | Complexitate | |
|---|---|---|---|
| Constructorii | vector::vector | Constructorul implicit. Nu acceptă argumente, creează o nouă instanță vectorială | O(1)(funcționează în timp constant) |
| vector::vector(const vector& c) | Constructorul de copiere implicit. Creează o copie a vectoruluic | O(n)(funcționează în timp liniar proporțional cu dimensiunea vectorului c) | |
| vector::vector(size_type n, const T& val = T()) | Creează un vector cu nobiecte. Dacă este valdeclarat, atunci fiecare dintre aceste obiecte va fi inițializat cu valoarea sa; în caz contrar, obiectele vor primi o valoare implicită de constructor de tip T. | O(n) | |
| vector::vector(input_iterator start, input_iterator end) | Creează un vector de elemente între startșiend | O(n) | |
| Destructor | vector::~vector | Distruge vectorul și elementele acestuia | |
| Operatori | vector::operator= | Copiază valoarea unui vector în altul. | O(n) |
| vector::operator== | Comparația a doi vectori | O(n) | |
| Acces la elemente |
vector::at | Accesarea unui element cu verificare în afara limitelor | O(1) |
| vector::operator[] | Accesarea unui anumit element | O(1) | |
| vector::front | Accesarea primului element | O(1) | |
| vector::back | Accesarea ultimului element | O(1) | |
| Iteratori | vector::begin | Returnează un iterator la primul element al vectorului | O(1) |
| vector::end | Returnează un iterator după ultimul element al vectorului | O(1) | |
| vector::rbegin | Revine reverse_iteratorla sfârșitul vectorului curent. | O(1) | |
| vector::rend | Revine reverse_iteratorla începutul vectorului. | O(1) | |
| Lucrul cu dimensiunea vectorului |
vector::empty | Returnează truedacă vectorul este gol | O(1) |
| vector::size | Returnează numărul de elemente din vector | O(1) | |
| vector::max_size | Returnează numărul maxim posibil de elemente dintr-un vector | O(1) | |
| vector::reserve | Setează numărul minim posibil de elemente într-un vector | O(n) | |
| vector::capacity | Returnează numărul de elemente pe care vectorul le poate conține înainte de a avea nevoie să aloce mai mult spațiu. | O(1) | |
| vector::shrink_to_fit | Reduce cantitatea de memorie utilizată prin eliberarea memoriei nefolosite ( C++11 ) | O(1) | |
| Modificatori | vector::clear | Îndepărtează toate elementele vectorului | O(n) |
| vector::insert | Inserarea elementelor într-un vector | Inserarea la sfarsit, cu conditia ca memoria sa nu fie realocata - O(1), intr-un loc arbitrar -O(n) | |
| vector::erase | Elimină elementele vectoriale specificate (unul sau mai multe) | O(n) | |
| vector::push_back | Inserarea unui element la sfârșitul unui vector | O(1) | |
| vector::pop_back | Eliminați ultimul element al vectorului | O(1) | |
| vector::resize | Modifică dimensiunea vectorului cu cantitatea dată | O(n) | |
| vector::swap | Schimbați conținutul a doi vectori | O(1) | |
| Alte Metode | vector::assign | Asociază valorile date cu un vector | O(n), dacă dimensiunea vectorului dorită este setată, O(n*log(n))la realocarea memoriei |
| vector::get_allocator | Returnează alocatorul folosit pentru a aloca memorie | O(1) |
În plus față de funcțiile de acces direct la elemente descrise mai sus, elementele unui vector pot fi accesate folosind iteratoare .
Iteratoarele sunt de obicei folosite în perechi, dintre care unul este folosit pentru a indica iterația curentă, iar al doilea este folosit pentru a indica sfârșitul containerului. Iteratoarele sunt create folosind metode standard, cum ar begin()fi end(). Funcția begin()returnează un pointer către primul element și returnează un pointer către un end() element imaginar inexistent după ultimul.
Vectorul folosește cel mai bogat tip de iterator, RandomAccessIterator (iterator cu acces aleatoriu), care vă permite să traversați containerul în orice ordine, precum și să modificați conținutul vectorului în procesul de parcurgere. Cu toate acestea, dacă vectorul se modifică, iteratorul poate deveni invalid.
Un exemplu de calcul al sumei elementelor vectoriale folosind iteratoare:
#include <iostream> #include <vector> #include <iterator> folosind namespace std ; int main () { vector < int > vectorul_ ; vector < int >:: iterator the_iterator ; pentru ( int i = 0 ; i < 10 ; i ++ ) { vectorul . push_back ( i ); } int total = 0 ; the_iterator = the_vector . începe (); while ( iteratorul != vectorul . sfârşitul ()) { total += * the_iterator ++ ; } cout << "summa= " << total << endl ; returnează 0 ; } vector < int > vectorul_ ; vector < int >:: iterator the_iterator ; pentru ( int i = 0 ; i < 10 ; i ++ ) { vectorul . push_back ( i ); } int total = 0 ; the_iterator = the_vector . începe (); while ( iteratorul != vectorul . sfârşitul ()) { total += * the_iterator ; /* Rețineți că elementul poate fi accesat prin dereferențierea iteratorului */ ++ the_iterator ; } cout << "Total=" << total << endl ;Rezultat:
Total=45
O implementare tipică vectorială este un pointer către o matrice dinamică. Dimensiunea unui vector este numărul real de elemente, iar dimensiunea este cantitatea de memorie pe care o folosește.
Dacă, la inserarea unor elemente noi într-un vector, dimensiunea acestuia devine mai mare decât volumul său, memoria este realocata. De obicei, acest lucru va determina vectorul să aloce o nouă zonă de stocare, mutând elementele și eliberând zonele vechi în noua locație de memorie.
Deoarece adresele elementelor se modifică în timpul acestui proces, orice referință sau iteratoare de elemente din vector poate deveni invalidă. Utilizarea referințelor nevalide are ca rezultat un comportament nedefinit. Exemplu:
#include <vector> int main () { std :: vector < int > v ( 1 ); // Creați un vector cu un element int a cărui valoare este 0 int & first = * v . începe (); // Creați o legătură către primul element v . insert ( v . end (), v . capacitate (), 0 ); // Adăugați elemente noi int i = first ; // Comportament nedefinit. Este posibil ca linkul să nu fie valid }Metoda reserve()este folosită pentru a preveni realocările inutile ale memoriei. După apel reserve(n), dimensiunea vectorului este garantată să nu fie mai mică decât n. Exemplu:
#include <vector> int main () { std :: vector < int > v ( 1 ); // Creați un vector format dintr-un singur element de tip int a cărui valoare este 0 v . rezerva ( 10 ); // Rezervă spațiu int & first = * v . începe (); // Creați o legătură către primul element v . insert ( v . sfârşit (), 5 , 0 ); // Adăugarea elementelor la vector int i = first ; // OK deoarece nu a existat nicio realocare a memoriei }Un vector menține o ordine specifică a elementelor sale, astfel încât atunci când un nou element este inserat la începutul sau la mijlocul vectorului, elementele ulterioare sunt mutate înapoi în ceea ce privește operatorul de atribuire și constructorul de copiere. Prin urmare, referințele la elemente și iteratorii după punctul de inserare sunt invalidate. Exemplu:
#include <vector> int main () { std :: vector < int > v ( 2 ); // Creați un vector format din două elemente de tip Int // Creați referințe la ambele elemente int & first = v . fata (); int & last = v . spate (); v . insert ( v . începe () + 1 , 1 , 1 ); // Adăugați elemente noi la mijlocul vectorului int i = first ; // Comportament nedefinit dacă o inserare a cauzat o realocare int j = last ; // Comportament nedefinit, conform standardului C++, §23.2.4.3/1 }Biblioteca standard C++ definește o specializare de șablon vectorial pentru bool. Conform specializării, vectorul trebuie să împacheteze elementele astfel încât fiecare element de tip bооlsă folosească doar un bit de memorie [3] . Acest lucru este numit de mulți o eroare [4] [5] deoarece nu este conformă cu cerințele vector<bool>containerului C++ Standard Library . De exemplu, containerul <T>::referencetrebuie să fie adevărat lvaluepentru tipul T. Acesta nu este cazul cu c vector<bool>::reference, care este un substituent convertibil în bool[6] . În plus, vector<bool>::iteratornu dă bool&la dereferință. Există un acord între comitetul de standardizare C++ și echipa de dezvoltare a bibliotecii că vector<bool>ar trebui să fie depreciat și apoi eliminat din biblioteca standard, iar funcționalitatea va fi restaurată, dar sub un alt nume. [7]
Programele C++ care folosesc un vector trebuie să includă un fișier antet <vector>:
#include <vector> // După aceea, puteți inițializa variabila std :: vector < T > myVector ;Aici T - tipul de date care vor fi stocate în container și myVector - variabila care va fi utilizată. Tpoate fi orice tip de date, inclusiv un tip de date definit de utilizator.
În C și C++ , o matrice este date în blocuri adiacente de memorie. Fiecărui bloc i se atribuie apoi un index, iar conținutul fiecărui bloc poate fi găsit cunoscând indexul acestuia. Toate elementele unui tablou trebuie să fie de același tip.
Un vector este similar cu o matrice dinamică, dar un vector se poate redimensiona singur. De asemenea, nu este nevoie să eliberați manual memoria.
Deoarece elementele unui vector sunt stocate contigu, adresa primului element al vectorului poate fi transmisă funcției ca un tablou (pointer la primul element). Următorul exemplu ilustrează modul în care un vector poate fi utilizat cu funcțiile bibliotecii standard C memcpyși printf:
#include <cstring> // memcpy #include <vector> #include <cstdio> // printf int main () { folosind namespace std ; const char arr [] = "1234567890" ; // Creați un vector cu 11 '\0' vector < char > vec ( sizeof arr ); // Copiați 11 elemente de tip 'char' într-un vector memcpy ( vec . data (), arr , sizeof arr ); // Imprimă „1234567890” printf ( „%s” , vec . date ()); }Rețineți că utilizarea memcpyși printfeste descurajată, în favoarea unor alternative mai sigure din biblioteca standard C++
Următorul exemplu demonstrează diferite tehnici care implică un vector și algoritmi de bibliotecă standard C++ , cum ar fi amestecarea, sortarea, găsirea celui mai mare element și ștergerea dintr-un vector folosind expresia ștergere-eliminare.
#include <iostream> #include <vector> #include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound #include <functional> // mai mare, bind2nd // Folosit pentru comoditate. În programele reale, utilizați cu grijă folosind namespace std ; int main () { int arr [ 4 ] = { 1 , 2 , 3 , 4 }; // Initializeaza un vector folosind un vector matrice < int > numere ( arr , arr + 4 ); // Adăugați numere la vectorul numere . push_back ( 5 ); numere . push_back ( 6 ); numere . push_back ( 7 ); numere . push_back ( 8 ); // Acum vectorul arată astfel: {1, 2, 3, 4, 5, 6, 7, 8} // Amestecă aleatoriu elementele random_shuffle ( numere . început (), numere . sfârşit ()); // Obține elementul maxim, complexitatea O(n) vector < int >:: const_iterator cel mai mare = max_element ( numere . început (), numere . sfârșit () ); cout << "cel mai mare element" << * cel mai mare << endl ; cout << "Indexul acestui element" << cele mai mari - numere . începe () << endl ; // Sortare elemente, complexitate O(n log n) sortare ( numere . început (), numere . sfârşit ()); // Aflați poziția numărului 5 în vector, complexitatea O(log n) vector < int >:: const_iterator five = limita_inferioară ( numere . început (), numere . sfârșit (), 5 ); cout << "Numărul 5 este la index " << cinci numere . începe () << endl ; // Eliminați toate elementele mai mari de 4 numere . șterge ( șterge_dacă ( numere . început (), numere . sfârșit (), bind2nd ( mai mare < int > (), 4 )), numere . sfârșit () ); // Tipăriți restul pentru ( vector < int >:: const_iterator it = numere . begin (); it != numere . end (); ++ it ) { cout << * it << ' ' ; } returnează 0 ; }Ieșirea va conține:
Cel mai mare element 8
Indicele acestui element este 6 (dependent de implementare)
Numărul 5 este situat sub indexul 4
1 2 3 4
Un exemplu de vector dinamic bidimensional, precum și un exemplu de accesare și modificare
typedef std :: vector < std :: vector < int > > pxMP ; funcția void () { int sizeX , sizeY ; // specificam dimensiunea din zbor. pxMP pxMap ( sizeX , std :: vector < int > ( sizeY )); // matrice de dimensiune X/Y pixeli 0.1. pxMap [ 0 ][ 5 ] = 1 ; /* acces */ // eliminați coloanele din stânga și din dreapta ale pxMap . pop_back (); pxMap . șterge ( pxMap.begin ( ) ); // eliminați rândurile de sus și de jos din toate coloanele, creați mai întâi câteva instrumente pentru aceasta: std :: vector < std :: vector < int > >:: iterator iterlvl2 ; // iterator pentru a doua dimensiune. std :: vector < int >:: iterator iterlvl1 ; // iterator pentru prima dimensiune // Aprofundează pentru ( iterlvl2 = pxMap . begin (); iterlvl2 != pxMap . end (); iterlvl2 ++ ) { iterlvl1 = ( * iterlvl2 ). începe (); // Numai în scop demonstrativ ( * iterlvl2 ). pop_back (); ( * iterlvl2 ). șterge (( * iterlvl2 ) .begin ()); // Unde suntem? mărimeaY = ( * iterlvl2 ). dimensiune (); // Setați dimensiunea Y cât suntem la acest nivel. Atunci nu vom putea face asta } }Un exemplu de vector dinamic unidimensional, sortând și eliminând duplicatele:
#include <vector> #include <șir> #include <algoritm> // Pentru a utiliza algoritmi std::sort, std::unique int main () { std :: vector < std :: string > v_str ; //Vector gol 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"} //Sortează toate elementele vectorului std :: sort ( v_str . begin (), v_str . end ()); //Rezultatul sortării vectoriale: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"} // Eliminați duplicatele v_str . erase ( std :: unique ( v_str . begin (), v_str . end () ), v_str . end () ); //Rezultatul eliminării duplicatelor: {"aa","bb","dd","xx","zz"} returnează 0 ; }