A vektor ( std::vector<T>) egy szabványos C++ általános programozási minta, amely dinamikus tömböt valósít meg .
A sablon vectora fejlécfájlban található <vector>. Mint minden szabványos alkatrész, ez is a std . Ez az interfész egy szabványos C tömb működését emulálja (például gyors véletlenszerű hozzáférést az elemekhez), valamint néhány további szolgáltatást, például egy vektor automatikus átméretezését elemek beszúrásakor vagy eltávolításakor.
Egy vektor minden elemének azonos típusúnak kell lennie. Például nem tárolhat char és int adatokat együtt ugyanabban a vektorpéldányban. Az osztály vector szabványos metóduskészlettel rendelkezik az elemek elérésére, az elemek hozzáadására és eltávolítására, valamint a tárolandó elemek számának lekérésére.
Egy vektor inicializálható bármilyen másoláskonstruktorral rendelkező típussal, amely meghatározott operator=és megfelel a következő feltételeknek [1] :
| Kifejezés | visszatérési típus | Állapot |
|---|---|---|
| t = u | T& | tegyenértékűu |
| T(t) | tegyenértékűT(t) | |
| T(u) | uegyenértékűT(u) | |
| &u | const T* | címet mutatjau |
| t.~T() |
Itt T a típus, amellyel a vektor inicializálva van, t egy típusú változó T, u egy típusú változó (esetleg const) T.
Például:
vektor < int > myVector ; // Üres vektor int típusú elemekből vector < float > myVector ( 10 ); // A 10- es vektor lebegteti a vektort < char > myVector ( 5 , ' ' ); // 5 szóközből álló vektor osztály T { ... }; int n = 10 ; vektor < T > myVector ( n ); // 10 egyedi T típusú elem vektoraA vektor egyes elemei az alábbi táblázatban leírt műveletekkel érhetők el. C és C++ megegyezés szerint az első elem indexe 0, az utolsó elem pedig size() - 1[2] indexszel .
| Kifejezés | visszatérési típus | Határellenőrzés? |
|---|---|---|
| v.at(i) | T&vagy const T&az i elemre | Kivétel dobása lehetségesout_of_range |
| v[i] | T&vagy const T&az i elemre | Meghatározatlan viselkedés mikori >= v.size() |
| v.front() | T&vagy const T&az első elemhez | Meghatározatlan viselkedés mikorv.empty() == true |
| v.back() | T&vagy const T&az utolsó elemre | Meghatározatlan viselkedés mikorv.empty() == true |
Ahol v egy (esetleg const) típusú objektum vector<T>, és i a vektor szükséges elemének indexe.
Az osztály vector egy konténer. A C++ szabvány szerint minden tárolónak tartalmaznia kell a begin(), end(), size(), max_size(), empty(), és metódusokat swap().
Az alábbiakban az elérhető módszerek rövid listája található leírással és a bonyolultság jelzésével.
| Módszer | Leírás | Bonyolultság | |
|---|---|---|---|
| Konstruktorok | vector::vector | Az alapértelmezett konstruktor. Nem vesz fel argumentumokat, új vektorpéldányt hoz létre | O(1)(állandó időben működik) |
| vector::vector(const vector& c) | Az alapértelmezett másoláskonstruktor. Létrehoz egy másolatot a vektorrólc | O(n)(a vektor méretével arányos lineáris időben hajtja végre c) | |
| vector::vector(size_type n, const T& val = T()) | Létrehoz egy vektort nobjektumokkal. Ha valdeklarálva van, akkor ezen objektumok mindegyike inicializálódik az értékével; ellenkező esetben az objektumok egy alapértelmezett típusú konstruktor értéket kapnak T. | O(n) | |
| vector::vector(input_iterator start, input_iterator end) | startLétrehoz egy vektort a és közötti elemekbőlend | O(n) | |
| Pusztító | vector::~vector | Megsemmisíti a vektort és elemeit | |
| Üzemeltetők | vector::operator= | Egy vektor értékét másolja a másikba. | O(n) |
| vector::operator== | Két vektor összehasonlítása | O(n) | |
| Hozzáférés az elemekhez |
vector::at | Elem elérése határon túli ellenőrzéssel | O(1) |
| vector::operator[] | Hozzáférés egy adott elemhez | O(1) | |
| vector::front | Az első elem elérése | O(1) | |
| vector::back | Hozzáférés az utolsó elemhez | O(1) | |
| Iterátorok | vector::begin | Egy iterátort ad vissza a vektor első eleméhez | O(1) |
| vector::end | Egy iterátort ad vissza a vektor utolsó eleme után | O(1) | |
| vector::rbegin | Visszatér reverse_iteratoraz aktuális vektor végére. | O(1) | |
| vector::rend | Visszatér reverse_iteratora vektor elejére. | O(1) | |
| Vektormérettel dolgozik |
vector::empty | Visszatér true, ha a vektor üres | O(1) |
| vector::size | A vektor elemeinek számát adja vissza | O(1) | |
| vector::max_size | Egy vektor elemeinek maximális lehetséges számát adja eredményül | O(1) | |
| vector::reserve | Beállítja a vektor elemeinek minimális lehetséges számát | O(n) | |
| vector::capacity | A vektor által tartalmazható elemek számát adja vissza, mielőtt több helyet kellene lefoglalnia. | O(1) | |
| vector::shrink_to_fit | Csökkenti a használt memória mennyiségét a fel nem használt memória felszabadításával ( C++11 ) | O(1) | |
| Módosítók | vector::clear | Eltávolítja a vektor összes elemét | O(n) |
| vector::insert | Elemek beszúrása vektorba | Beszúrás a végén, feltéve, hogy a memória nem kerül átcsoportosításra - O(1), tetszőleges helyre -O(n) | |
| vector::erase | Eltávolítja a megadott vektorelemeket (egy vagy több) | O(n) | |
| vector::push_back | Elem beszúrása a vektor végére | O(1) | |
| vector::pop_back | A vektor utolsó elemének eltávolítása | O(1) | |
| vector::resize | Megváltoztatja a vektor méretét a megadott értékkel | O(n) | |
| vector::swap | Cserélje fel két vektor tartalmát | O(1) | |
| Egyéb módszerek | vector::assign | Adott értékeket vektorral társítja | O(n), ha a kívánt vektorméret be van állítva, a O(n*log(n))memória újraelosztása során |
| vector::get_allocator | A memória lefoglalásához használt lefoglalót adja vissza | O(1) |
A fent leírt közvetlen elemelérési funkciókon kívül egy vektor elemei iterátorokkal is elérhetők .
Az iterátorokat általában párban használják, amelyek közül az egyik az aktuális iterációt, a második pedig a tároló végét jelzi. Az iterátorok szabványos módszerekkel, begin()például end(). A függvény begin()visszaad egy mutatót az első elemre, és egy mutatót ad vissza egy end() képzeletbeli nem létező elemre, amely az utolsó után következik.
A vektor a leginkább funkciókban gazdag iterátortípust, a RandomAccessIterator-t (random access iterator) használja, amely lehetővé teszi a konténer tetszőleges sorrendben történő bejárását, valamint a bejárás során a vektor tartalmának megváltoztatását. Ha azonban a vektor megváltozik, az iterátor érvénytelenné válhat.
Példa a vektorelemek összegének kiszámítására iterátorok segítségével:
#include <iostream> #include <vektor> #include <iterátor> névtér használata std ; int main () { vektor < int > a_vektor ; vektor < int >:: iterátor the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { a_vektor . push_back ( i ); } int összesen = 0 ; the_iterator = the_vector . kezdődik (); while ( the_iterator != the_vector . end ()) { összesen += * the_iterator ++ ; } cout << "summa= " << összesen << endl ; return 0 ; } vektor < int > a_vektor ; vektor < int >:: iterátor the_iterator ; for ( int i = 0 ; i < 10 ; i ++ ) { a_vektor . push_back ( i ); } int összesen = 0 ; the_iterator = the_vector . kezdődik (); while ( the_iterator != the_vector . end ()) { összesen += * the_iterator ; /* Vegye figyelembe, hogy az elem az iterátor hivatkozásának megszüntetésével érhető el */ ++ the_iterator ; } cout << "Összesen=" << összesen << endl ;Eredmény:
Összesen=45
Egy tipikus vektor megvalósítás egy dinamikus tömbre mutató mutató. Egy vektor mérete az elemek tényleges száma, a mérete pedig az általa használt memória mennyisége.
Ha egy vektorba új elemek beillesztésekor a mérete nagyobb lesz, mint a térfogata, akkor a memória átcsoportosításra kerül. Általában ez azt eredményezi, hogy a vektor új tárolóterületet foglal le, áthelyezi az elemeket és felszabadítja a régi területeket az új memóriahelyre.
Mivel a folyamat során az elemek címe megváltozik, a vektorban lévő elemekre vonatkozó hivatkozások vagy iterátorok érvénytelenek lehetnek. Az érvénytelen hivatkozások használata meghatározatlan viselkedést eredményez. Példa:
#include <vektor> int main () { std :: vektor < int > v ( 1 ); // Hozzon létre egy vektort egy int elemmel, amelynek értéke 0 int & first = * v . kezdődik (); // Hivatkozás létrehozása az első elemre v . beszúr ( v . vége (), v . kapacitás (), 0 ); // Új elemek hozzáadása int i = first ; // Meghatározatlan viselkedés. Lehet, hogy a link nem érvényes }A módszer reserve()a szükségtelen memória-újrafoglalások megelőzésére szolgál. Hívás után reserve(n)a vektor mérete garantáltan nem kisebb, mint n. Példa:
#include <vektor> int main () { std :: vektor < int > v ( 1 ); // Hozzon létre egy vektort, amely egyetlen int típusú elemből áll, amelynek értéke 0 v . tartalék ( 10 ); // Helyfoglalás int & first = * v . kezdődik (); // Hivatkozás létrehozása az első elemre v . beszúr ( v . vége (), 5 , 0 ); // Elemek hozzáadása a vektorhoz int i = first ; // OK, mivel nem történt memória újrafoglalás }Egy vektor megtartja az elemeinek meghatározott sorrendjét, így amikor egy új elemet beszúrunk a vektor elejére vagy közepére, a következő elemek visszafelé mozognak hozzárendelési operátoruk és másoláskonstruktoruk szempontjából. Ezért a beszúrási pont utáni elemhivatkozások és iterátorok érvénytelenek. Példa:
#include <vektor> int main () { std :: vektor < int > v ( 2 ); // Két Int típusú elemből álló vektor létrehozása // Hivatkozások létrehozása mindkét elemre int & first = v . elöl (); int & last = v . vissza (); v . beszúr ( v . kezdődik () + 1 , 1 , 1 ); // Új elemek hozzáadása a vektor közepéhez int i = first ; // Nem definiált viselkedés, ha egy beszúrás újraelosztást okozott int j = last ; // Nem definiált viselkedés a C++ szabvány szerint, §23.2.4.3/1 }A C++ Standard Library vektorsablon specializációt határoz meg a bool. A specializáció szerint a vektornak úgy kell csomagolnia az elemeket, hogy a típus minden eleme bооlcsak egy bit memóriát használjon [3] . Ezt sokan hibának nevezik [4] [5] , mert nem felel meg a C++ Standard Libraryvector<bool> tároló követelményeinek . Például a tárolónak igaznak kell lennie T típusúnak. Nem ez a helyzet c -vel , amely egy helyőrző , amely [6] -ra konvertálható . Különben is, nem ad hivatkozással. Megállapodás van a C++ szabványosítási bizottság és a könyvtárfejlesztő csapat között, miszerint elavulttá kell tenni, majd el kell távolítani a szabványos könyvtárból , és a funkcionalitás visszaáll, de más néven. [7]<T>::referencelvaluevector<bool>::referenceboolvector<bool>::iteratorbool&vector<bool>
A vektort használó C++ programoknak tartalmazniuk kell egy fejlécfájlt <vector>:
#include <vektor> // Ezt követően inicializálhatjuk az std :: vector < T > myVector változót ;Itt T - a tárolóban tárolt adatok típusa és myVector - a használt változó. Tbármilyen adattípus lehet, beleértve a felhasználó által meghatározott adattípust is.
A C és C++ nyelvekben egy tömb a memória összefüggő blokkjaiban lévő adatok. Ezután minden blokkhoz hozzárendelnek egy indexet, és az egyes blokkok tartalma az index ismeretében megtalálható. Egy tömb minden elemének azonos típusúnak kell lennie.
A vektor hasonló a dinamikus tömbhöz, de egy vektor átméretezheti magát. Ezenkívül nincs szükség a memória manuális felszabadítására.
Mivel egy vektor elemei egymás mellett vannak tárolva, a vektor első elemének címe tömbként (az első elemre mutató mutató) átadható a függvénynek. A következő példa bemutatja, hogyan lehet egy vektort használni a C szabványos könyvtári függvényekkel memcpyés printf:
#include <cstring> // memcpy #include <vektor> #include <cstdio> // printf int main () { névtér használata std ; const char arr [] = "1234567890" ; // Vektor létrehozása 11 '\0' vektorral < char > vec ( sizeof arr ); // 11 'char' típusú elem másolása egy vektormemcpy -be ( vec . data (), arr , sizeof arr ); // Kiírja a "1234567890" printf ( "%s" , vec . data ()); }Vegye figyelembe, hogy a memcpyés a használata nem javasolt, a C++ Standard Libraryprintf biztonságosabb alternatívái mellett
A következő példa különböző technikákat mutat be vektorral és C++ szabványos könyvtári algoritmusokkal , mint például a keverés, a rendezés, a legnagyobb elem megkeresése és a törlés-eltávolítás idióma használatával a vektorból való törlés.
#include <iostream> #include <vektor> #include <algoritmus> // rendezés, max_element, random_shuffle, remove_if, alsó_korlát #include <functional> // nagyobb, bind2nd // A kényelem kedvéért használjuk. A valós programokban óvatosan használja a névteret std ; int main () { int arr [ 4 ] = { 1 , 2 , 3 , 4 }; // Vektor inicializálása tömbvektor segítségével < int > numbers ( arr , arr + 4 ) ; // Számok hozzáadása a számvektorhoz . push_back ( 5 ); számok . push_back ( 6 ); számok . push_back ( 7 ); számok . push_back ( 8 ); // Most a vektor így néz ki: {1, 2, 3, 4, 5, 6, 7, 8} // Az elemek véletlenszerű keverése random_shuffle ( számok . kezd (), számok . vége ()); // Szerezd meg a maximális elemet, komplexitás O(n) vektor < int >:: const_iterator legnagyobb = max_elem ( számok . kezdete (), számok . vége () ); cout << "legnagyobb elem" << * legnagyobb << endl ; cout << "Ennek az elemnek az indexe" << legnagyobb - számok . kezdődik () << endl ; // Elemek rendezése, összetettség O(n log n) rendezés ( számok . kezdete (), számok . vége ()); // Keresse meg az 5-ös szám helyzetét a vektorban, összetettség O(log n) vektor < int >:: const_iterator five = alsó_korlát ( számok . kezd (), számok . vége (), 5 ); cout << "Az 5-ös szám az indexnél van" << öt szám . kezdődik () << endl ; // Minden 4 számnál nagyobb elem eltávolítása . erase ( remove_if ( számok . kezdete (), számok . vége (), bind2nd ( nagyobb < int > (), 4 )), számok . vége () ); // A többi kinyomtatása for ( vektor < int >:: const_iterator it = számok . kezdődik (); it != számok . vége (); ++ it ) { cout << * it << ' ' ; } return 0 ; }A kimenet a következőket tartalmazza majd:
Legnagyobb elem 8
Ennek az elemnek az indexe 6 (megvalósításfüggő)
Az 5-ös szám a 4-es index alatt található
1 2 3 4
Példa egy 2-dimenziós dinamikus vektorra, valamint egy példa a hozzáférésére és módosítására
typedef std :: vektor < std :: vektor < int > > pxMP ; void function () { int X méret , Y méret ; // menet közben adja meg a méretet. pxMP pxMap ( sizeX , std :: vektor < int > ( sizeY )); // X/Y pixel méretű tömb 0.1. pxMap [ 0 ][ 5 ] = 1 ; /* hozzáférés */ // távolítsa el a pxMap bal és jobb oszlopát . pop_back (); pxMap . törlés ( pxMap.begin ( ) ); // távolítsd el az összes oszlopból a felső és alsó sort, először készíts ehhez néhány eszközt: std :: vector < std :: vector < int > >:: iterator iterlvl2 ; // iterátor a második dimenzióhoz. std :: vektor < int >:: iterator iterlvl1 ; // iterátor az első dimenzióhoz // Menjen mélyre a következőhöz: ( iterlvl2 = pxMap . begin (); iterlvl2 != pxMap . end (); iterlvl2 ++ ) { iterlvl1 = ( * iterlvl2 ). kezdődik (); // Csak bemutató célból ( * iterlvl2 ). pop_back (); ( * iterlvl2 ). törlés (( * iterlvl2 ) .begin ()); // Hol vagyunk? sizeY = ( * iterlvl2 ). méret (); // Állítsa be az Y méretet, amíg ezen a szinten vagyunk. Akkor nem fogjuk tudni megtenni } }Példa egy egydimenziós dinamikus vektorra, a másolatok rendezésére és eltávolítására:
#include <vektor> #include <karakterlánc> #include <algoritmus> // Std::sort, std::unique algoritmusok használata int main () { std :: vektor < std :: string > v_str ; //Üres 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"} //A vektor összes elemének rendezése std :: sort ( v_str . begin (), v_st.vége ( ) ); //A vektorrendezés eredménye: {"aa", "aa", "bb", "dd", "xx", "xx", "zz"} // Duplikátumok eltávolítása v_str . törlés ( std :: egyedi ( v_str . begin (), v_str . end () ), v_str . end () ); //Az ismétlődések eltávolításának eredménye: {"aa","bb","dd","xx","zz"} return 0 ; }