Vector ( std::vector<T>) je standardní obecný programovací vzor C++, který implementuje dynamické pole .
Šablona vectorse nachází v záhlaví souboru <vector>. Stejně jako všechny standardní komponenty je umístěn v std . Toto rozhraní emuluje činnost standardního pole C (například rychlý náhodný přístup k prvkům) a také některé další funkce, jako je automatická změna velikosti vektoru při vkládání nebo odstraňování prvků.
Všechny prvky vektoru musí být stejného typu. Nemůžete například ukládat data char a int společně ve stejné instanci vektoru. Třída vector má standardní sadu metod pro přístup k prvkům, přidávání a odebírání prvků a získávání počtu prvků k uložení.
Vektor lze inicializovat libovolným typem, který má kopírovací konstruktor a je definován operator=a splňuje následující podmínky [1] :
| Výraz | návratový typ | Stav |
|---|---|---|
| t = u | T& | tekvivalentu |
| T(t) | tekvivalentT(t) | |
| T(u) | uekvivalentT(u) | |
| &u | const T* | zobrazuje adresuu |
| t.~T() |
Zde T je typ, kterým je vektor inicializován, t je proměnná typu T, u je proměnná typu (možná const) T.
Například:
vector < int > myVector ; // Prázdný vektor prvků typu int vector < float > myVector ( 10 ); // Vektor 10 plave vektor < char > myVector ( 5 , ' ' ); // Vektor skládající se z 5 mezer třída T { ... }; int n = 10 ; vektor < T > myVector ( n ); // Vektor 10 prvků vlastního typu TK jednotlivému prvku vektoru lze přistupovat pomocí operací popsaných v tabulce níže. Podle konvence C a C++ má první prvek index 0a poslední prvek má index size() - 1[2] .
| Výraz | návratový typ | Kontrola na hranicích? |
|---|---|---|
| v.at(i) | T&nebo const T&pro prvek i | Vyhození výjimky je možnéout_of_range |
| v[i] | T&nebo const T&pro prvek i | Nedefinované chování přii >= v.size() |
| v.front() | T&nebo const T&pro první prvek | Nedefinované chování přiv.empty() == true |
| v.back() | T&nebo const T&pro poslední prvek | Nedefinované chování přiv.empty() == true |
Kde v je objekt typu (případně const) vector<T>a i je index požadovaného prvku vektoru.
Třída vector je kontejner. Podle standardu C++ musí každý kontejner obsahovat metody begin(), end(), size(), max_size(), empty()a swap().
Níže je uveden stručný seznam dostupných metod s popisem a uvedením složitosti .
| Metoda | Popis | Složitost | |
|---|---|---|---|
| Konstruktéři | vector::vector | Výchozí konstruktor. Nebere žádné argumenty, vytváří novou vektorovou instanci | O(1)(vystupuje v konstantním čase) |
| vector::vector(const vector& c) | Výchozí konstruktor kopírování. Vytvoří kopii vektoruc | O(n)(provádí se v lineárním čase úměrně velikosti vektoru c) | |
| vector::vector(size_type n, const T& val = T()) | Vytvoří vektor s nobjekty. Pokud valje deklarován, každý z těchto objektů bude inicializován svou hodnotou; jinak objekty získají výchozí hodnotu konstruktoru typu T. | O(n) | |
| vector::vector(input_iterator start, input_iterator end) | Vytvoří vektor prvků mezi startaend | O(n) | |
| Destruktor | vector::~vector | Ničí vektor a jeho prvky | |
| Operátoři | vector::operator= | Zkopíruje hodnotu jednoho vektoru do druhého. | O(n) |
| vector::operator== | Porovnání dvou vektorů | O(n) | |
| Přístup k prvkům |
vector::at | Přístup k prvku s kontrolou mimo hranice | O(1) |
| vector::operator[] | Přístup ke konkrétnímu prvku | O(1) | |
| vector::front | Přístup k prvnímu prvku | O(1) | |
| vector::back | Přístup k poslednímu prvku | O(1) | |
| Iterátory | vector::begin | Vrátí iterátor k prvnímu prvku vektoru | O(1) |
| vector::end | Vrátí iterátor za posledním prvkem vektoru | O(1) | |
| vector::rbegin | Vrátí reverse_iteratorse na konec aktuálního vektoru. | O(1) | |
| vector::rend | Vrátí reverse_iteratorse na začátek vektoru. | O(1) | |
| Práce s velikostí vektoru |
vector::empty | Vrátí true, pokud je vektor prázdný | O(1) |
| vector::size | Vrátí počet prvků ve vektoru | O(1) | |
| vector::max_size | Vrátí maximální možný počet prvků ve vektoru | O(1) | |
| vector::reserve | Nastaví minimální možný počet prvků ve vektoru | O(n) | |
| vector::capacity | Vrátí počet prvků, které může vektor obsahovat, než potřebuje alokovat více místa. | O(1) | |
| vector::shrink_to_fit | Snižuje množství použité paměti uvolněním nevyužité paměti ( C++11 ) | O(1) | |
| Modifikátory | vector::clear | Odebere všechny prvky vektoru | O(n) |
| vector::insert | Vkládání prvků do vektoru | Vložení na konec za předpokladu, že paměť nebude přemístěna - O(1), na libovolné místo -O(n) | |
| vector::erase | Odebere zadané vektorové prvky (jeden nebo více) | O(n) | |
| vector::push_back | Vložení prvku na konec vektoru | O(1) | |
| vector::pop_back | Odstraňte poslední prvek vektoru | O(1) | |
| vector::resize | Změní velikost vektoru o danou hodnotu | O(n) | |
| vector::swap | Prohoďte obsah dvou vektorů | O(1) | |
| Jiné metody | vector::assign | Přidruží dané hodnoty k vektoru | O(n), pokud je nastavena požadovaná velikost vektoru, O(n*log(n))při přerozdělování paměti |
| vector::get_allocator | Vrátí alokátor použitý k alokaci paměti | O(1) |
Kromě výše popsaných funkcí přímého přístupu k prvkům lze k prvkům vektoru přistupovat pomocí iterátorů .
Iterátory se obvykle používají ve dvojicích, z nichž jeden se používá k označení aktuální iterace a druhý k označení konce kontejneru. Iterátory jsou vytvářeny pomocí standardních metod, begin()jako je end(). Funkce begin()vrací ukazatel na první prvek a vrací ukazatel na end() imaginární neexistující prvek následující za posledním.
Vektor používá nejbohatší typ iterátoru, RandomAccessIterator ( iterátor s náhodným přístupem), který vám umožňuje procházet kontejnerem v libovolném pořadí a také měnit obsah vektoru v procesu procházení. Pokud se však vektor změní, iterátor se může stát neplatným.
Příklad výpočtu součtu vektorových prvků pomocí iterátorů:
#include <iostream> #include <vektor> #include <iterátor> pomocí jmenného prostoru std ; int main () { vector < int > the_vector ; vector < int >:: iterator the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { the_vector . push_back ( i ); } int celkem = 0 ; the_iterator = the_vector . začít (); while ( the_iterator != the_vector . end ()) { celkem += * iterátor ++ ; } cout << "summa= " << celkem << endl ; návrat 0 ; } vector < int > the_vector ; vector < int >:: iterator the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { the_vector . push_back ( i ); } int celkem = 0 ; the_iterator = the_vector . začít (); while ( the_iterator != the_vector . end ()) { celkem += * iterátor ; /* Všimněte si, že k prvku lze přistupovat dereferencováním iterátoru */ ++ the_iterator ; } cout << "Celkem=" << celkem << endl ;Výsledek:
Celkem=45
Typickou vektorovou implementací je ukazatel na dynamické pole. Velikost vektoru je skutečný počet prvků a velikost je množství paměti, kterou používá.
Pokud se při vkládání nových prvků do vektoru jeho velikost zvětší než jeho objem, dojde k přerozdělení paměti. Typicky to způsobí, že vektor alokuje novou paměťovou oblast, přesune prvky a uvolní staré oblasti na nové paměťové místo.
Protože se adresy prvků během tohoto procesu mění, mohou být jakékoli odkazy nebo iterátory prvků ve vektoru neplatné. Použití neplatných odkazů má za následek nedefinované chování. Příklad:
#include <vektor> int main () { std :: vektor < int > v ( 1 ); // Vytvořte vektor s jedním prvkem int, jehož hodnota je 0 int & first = * v . začít (); // Vytvoří odkaz na první prvek v . vložit ( v . konec (), v . kapacita (), 0 ); // Přidání nových prvků int i = first ; // Nedefinované chování. Odkaz nemusí být platný }Metoda reserve()se používá, aby se zabránilo zbytečnému přerozdělení paměti. Po zavolání reserve(n)je zaručeno, že velikost vektoru nebude menší než n. Příklad:
#include <vektor> int main () { std :: vektor < int > v ( 1 ); // Vytvoří vektor skládající se z jednoho prvku typu int, jehož hodnota je 0 v . rezerva ( 10 ); // Rezerva místa int & first = * v . začít (); // Vytvoří odkaz na první prvek v . vložit ( v . konec (), 5 , 0 ); // Přidání prvků do vektoru int i = first ; // OK, protože nedošlo k žádnému přerozdělení paměti }Vektor si zachovává specifické pořadí svých prvků, takže když je nový prvek vložen na začátek nebo doprostřed vektoru, následující prvky se posunou zpět ve smyslu jejich operátoru přiřazení a konstruktoru kopírování. Proto jsou odkazy na prvky a iterátory za kurzorem neplatné. Příklad:
#include <vektor> int main () { std :: vektor < int > v ( 2 ); // Vytvořte vektor sestávající ze dvou prvků typu Int // Vytvořte odkazy na oba prvky int & first = v . přední (); int & last = v . zpět (); v . vložit ( v . begin () + 1 , 1 , 1 ); // Přidání nových prvků doprostřed vektoru int i = first ; // Nedefinované chování, pokud vložení způsobilo přerozdělení int j = last ; // Nedefinované chování, podle standardu C++, §23.2.4.3/1 }Standardní knihovna C++ definuje specializaci vektorových šablon pro bool. Podle specializace musí vektor zabalit prvky tak, aby každý prvek typu bооlvyužíval pouze jeden bit paměti [3] . To je nazýváno chybou mnoha [4] [5] , protože neodpovídá požadavkům vector<bool>kontejneru C++ Standard Library . Například kontejner <T>::referencemusí lvalueodpovídat typu T. To není případ c vector<bool>::reference, což je zástupný symbol přeměnitelný na bool[6] . Kromě toho vector<bool>::iteratornedává bool&při dereference. Mezi výborem pro standardizaci C++ a vývojovým týmem knihovny existuje dohoda, že vector<bool>by měla být zastaralá a poté odstraněna ze standardní knihovny a funkčnost bude obnovena, ale pod jiným názvem. [7]
Programy C++ , které používají vektor, musí obsahovat soubor záhlaví <vector>:
#include <vektor> // Poté můžete inicializovat proměnnou std :: vector < T > myVector ;Zde T - typ dat, která budou uložena v kontejneru, a myVector - proměnná, která bude použita. Tmůže být libovolný datový typ, včetně uživatelem definovaného datového typu.
V C a C++ jsou pole data v souvislých blocích paměti. Každému bloku je pak přiřazen index a obsah každého bloku lze nalézt na základě znalosti jeho indexu. Všechny prvky pole musí být stejného typu.
Vektor je podobný dynamickému poli, ale vektor může sám měnit velikost. Také není nutné ručně uvolňovat paměť.
Protože prvky vektoru jsou uloženy souvisle, adresa prvního prvku vektoru může být předána funkci jako pole (ukazatel na první prvek). Následující příklad ukazuje, jak lze použít vektor s funkcemi standardní knihovny C memcpya printf:
#include <cstring> // memcpy #include <vektor> #include <cstdio> // printf int main () { pomocí jmenného prostoru std ; const char arr [] = "1234567890" ; // Vytvořte vektor s 11 '\0' vektorem < char > vec ( sizeof arr ); // Zkopírujte 11 prvků typu 'char' do vektorové memcpy ( vec . data (), arr , sizeof arr ); // Vytiskne "1234567890" printf ( "%s" , vec . data ()); }Všimněte si, že se nedoporučuje používat memcpya printfve prospěch bezpečnějších alternativ ze standardní knihovny C++
Následující příklad ukazuje různé techniky zahrnující vektor a algoritmy standardní knihovny C++ , jako je míchání, řazení, hledání největšího prvku a mazání z vektoru pomocí idiomu erase-remove.
#include <iostream> #include <vektor> #include <algorithm> // řazení, max_element, random_shuffle, remove_if, lower_bound #include <funkční> // větší, bind2nd // Používá se pro pohodlí. Ve skutečných programech používejte opatrně jmenný prostor std ; int main () { int arr [ 4 ] = { 1 , 2 , 3 , 4 }; // Inicializace vektoru pomocí vektoru pole < int > čísla ( arr , arr + 4 ); // Přidání čísel do vektoru čísel . push_back ( 5 ); čísla . push_back ( 6 ); čísla . push_back ( 7 ); čísla . push_back ( 8 ); // Nyní vektor vypadá takto: {1, 2, 3, 4, 5, 6, 7, 8} // Náhodně zamíchejte prvky random_shuffle ( čísla . begin (), čísla . konec ()); // Získání maximálního prvku, složitosti O(n) vector < int >:: const_iterator největší = max_element ( čísla . begin (), čísla . konec () ); cout << "nejvetsi prvek" << * nejvetsi << endl ; cout << "Index tohoto prvku " << největší čísla . begin () << endl ; // Seřadit prvky, složitost O(n log n) sort ( čísla . začátek (), čísla . konec ()); // Najděte pozici čísla 5 ve vektoru, složitost O(log n) vector < int >:: const_iterator pět = dolní_mez ( čísla . začátek (), čísla . konec (), 5 ); cout << "Číslo 5 je na indexu " << pět čísel . begin () << endl ; // Odstraňte všechny prvky větší než 4 čísla . erase ( remove_if ( čísla . begin (), čísla . end (), bind2nd ( větší < int > (), 4 )), čísla . end () ); // Vytiskne zbytek pro ( vector < int >:: const_iterator it = čísla . begin (); it != čísla . konec (); ++ it ) { cout << * it << ' ' ; } návrat 0 ; }Výstup bude obsahovat:
Největší prvek 8
Index tohoto prvku je 6 (závisí na implementaci)
Číslo 5 se nachází pod indexem 4
1 2 3 4
Příklad 2-rozměrného dynamického vektoru a také příklad přístupu k němu a jeho úprav
typedef std :: vector < std :: vector < int > > pxMP ; void function () { int velikostX , velikostY ; // určit velikost za běhu. pxMP pxMap ( sizeX , std :: vector < int > ( sizeY )); // pole velikosti X/Y pixelů 0,1. pxMap [ 0 ][ 5 ] = 1 ; /* přístup */ // odstraní levý a pravý sloupec pxMap . pop_back (); pxMap . vymazat ( pxMap.begin ( ) ); // odebereme horní a spodní řádky ze všech sloupců, nejprve k tomu vytvoříme nějaké nástroje: std :: vector < std :: vector < int > >:: iterator iterlvl2 ; // iterátor pro druhou dimenzi. std :: vector < int >:: iterator iterlvl1 ; // iterátor pro první dimenzi // Jděte do hloubky pro ( iterlvl2 = pxMap . begin (); iterlvl2 != pxMap . end (); iterlvl2 ++ ) { iterlvl1 = ( * iterlvl2 ). začít (); // Pouze pro demonstrační účely ( * iterlvl2 ). pop_back (); ( * iterlvl2 ). vymazat (( * iterlvl2 ) .začít ()); // Kde jsme? sizeY = ( * iterlvl2 ). velikost (); // Nastavíme velikost Y, když jsme na této úrovni. Pak to nebudeme moci udělat } }Příklad jednorozměrného dynamického vektoru, třídění a odstraňování duplikátů:
#include <vektor> #include <řetězec> #include <algorithm> // Použití std::sort, std::unikátních algoritmů int main () { std :: vektor < std :: řetězec > v_str ; //Prázdný 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"} //Seřadit všechny prvky vektoru std :: sort ( v_str . begin (), v_str . end ()); //Výsledek třídění vektorů: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"} // Odstranit duplikáty v_str . erase ( std :: unique ( v_str . begin (), v_str . end () ), v_str . end () ); //Výsledek odstranění duplicit: {"aa","bb","dd","xx","zz"} return 0 ; }