C++/Vector

Vector

Przed zanurzeniem się głęboko w wektorach przeczytaj różnicę między vector and array

Klasa vector reprezentuje obudowaną, zwykłą tablicę znaną z C, wyposażoną w kilka dodatkowych mechanizmów. Elementy wektora mogą być dowolnego typu.

Obiekt vector ma kilka odmian konstruktorów. Z reguły będziemy tworzyć wektor pusty.

vector<typ_elementow> nazwa_tablicy;

Możemy też podać wielkość, co wcale nas nie ogranicza do tej wielkości, aby zarezerwować pamięć na kilka elementów od razu. Może to być zabieg optymalizacyjny.

 vector<int> tab(20);

Dodatkowo istnieje konstruktor przyjmujący liczbę elementów oraz wartość, jaką ma mieć każdy z nich.

 vector<string> tablica( 20, "przykladowy tekst" );

Ta tablica będzie miała dwadzieścia elementów, z czego wszystkie mają wartość: "przykladowy tekst".

Dodawanie elementów

Dodawanie elementów umożliwia metoda push_back(). Dodaje ona nowy element na koniec tablicy. Po dodaniu nowych elementów możemy się do nich odwoływać indeksowo [] lub metodą at(). Możemy też sprawdzić ile obecnie jest elementów metodą size(), a metoda empty() powie nam czy wektor jest pusty.

include <iostream>
include <vector>
using namespace std;
int main(){
    vector<int> tab;
    int n;
    cin >> n;
    for( int i=0; i<n; ++i )
    {
       int element;
       cin >> element;
       tab.push_back(element);
    }
}

Jak działa powiększanie się tablicy vector?

Poniższy akapit dotyczy szczegółów technicznych, jeśli nie jesteś nimi zainteresowany, możesz go pominąć.

Metoda push_back() dodając nowy element do tablicy, dba o to, aby tablica była odpowiedniego rozmiaru. Za każdym razem, gdy brakuje miejsca, tablica jest powiększana - rezerwowana jest nowa, większa przestrzeń, stare elementy są kopiowane, aby do większej tablicy móc dodać dany element. Z reguły rezerwowana jest pamięć dwa razy większa od poprzedniej. W skrajnej sytuacji, może się zdarzyć, że zarezerwowana pamięć jest prawie dwa razy większa niż ilość elementów znajdujących się w niej!

Jeśli zależy nam na szybkości działania, powinniśmy zarezerwować przy pomocy odpowiedniego konstruktora pamięć na pewną ilość elementów. Przykładowo, jeśli wiemy że w tablicy będzie około 50 elementów, możemy konstruować wektor o wielkości 50, dzięki czemu unikniemy kilku kopiowań całej tablicy podczas dodawania elementów. Warto też szukać złotego środka, aby przypadkiem nie marnować pamięci. Na przykład, aby nie stworzyć wektora o rozmiarze 100, jeśli dodane do niego będą tylko 2 elementy.

Ręczne zarezerwowanie pamięci dla wektora jest możliwe dzięki metodzie reserve(size_t n), natomiast metoda capacity() zwróci nam wielkość aktualnie zarezerwowanego miejsca.

Ponieważ kopiowanie tablicy jest powolnym procesem, w przypadku tablicy dużych struktur, na przykład klas, warto zastanowić się nad utworzeniem tablicy wskaźników na te struktury.

Iteratory

Jak wiemy, do poruszania się po elementach zwykłej tablicy takiej jak int a[10] można używać wskaźnika. Podobnie, operacje na obiekcie vector można dokonać używając iteratorów działających podobnie jak wskaźniki. Więcej o iteratorach znajduje się w dalszych rozdziałach.

Metody

Lista metod klasy vector. Użyte słowo iterator zastępuje poprawne vector<T>::iterator, podmienione zostało dla zwiększenia czytelności.

Modyfikacja

prototyp	opis działania	złożoność czasowa
void swap(vector<T>& vec)	zamienia zawartości dwóch wektorów miejscami	stała
void push_back(const T obj)	dodaje na końcu wektora kopię przekazanego argumentu	stała, czasem liniowa*
void pop_back()	usuwa ostatni element z wektora	stała
void clear()	usuwa wszystkie elementy z wektora	liniowa (destruktory)
void assign(size_t n, const T obj)	czyści wektor i wypełnia go n kopiami argumentu obj	liniowa (jak clear) + liniowa względem wstawianych elementów
void assign(iterator poczatek, iterator koniec)	czyści wektor i wypełnia go elementami z innego wektora z przedziału <poczatek;koniec>	jw.
iterator insert(iterator pos, T obj)	wstawia element obj przed wskazywaną przez iterator pos pozycją i zwraca iterator do dostawionego elementu	liniowa (przenoszenie elementów między pos a ostatnim elementem tablicy)
void insert(iterator pos, size_t n, const T obj)	wstawia n kopii argumentu obj przed pozycją wskazywaną przez iterator pos	jw. + liniowa względem ilości dodanych elementów
void insert(iterator pos, iterator poczatek, iterator koniec)	wstawia przed pozycją wskazywaną przez iterator pos elementy między iteratorami początek i koniec (włącznie)	jw.**
iterator erase(iterator pos)	usuwa element wskazywany przez pos i zwraca iterator do następnego elementu	liniowa względem ilości elementów za usuwanym elementem
iterator erase(iterator poczatek, iterator koniec)	usuwa elementy z przedziału <poczatek;koniec> i zwraca iterator do elementu za nimi	liniowa względem ilości usuwanych elementów + przenoszenie elementów za końcem

* może występować kopiowanie wektora, gdy rozmiar jest zbyt mały
** w rzadkim przypadku (dla iteratorów najniższego typu w hierarchi: Input lub Output) złożoność bliższa kwadratowej (ilość wstawianych elementów razy ilość elementów od pozycji do końca tablicy)

Dostęp

prototyp	opis działania
T& front()	zwraca referencję do pierwszego elementu wektora
T& back()	zwraca referencję do ostatniego elementu wektora
iterator begin()	zwraca iterator do pierwszego elementu wektora (często mylone z front())
iterator end()	zwraca iterator ustawiony za ostatnim elementem wektora
iterator rbegin()	zwraca odwrócony iterator do pierwszego elementu
iterator rend()	zwraca odwrócony iterator do ostatniego elementu

Inne

prototyp	opis działania
size_t size()	zwraca obecną liczbę elementów wektora.
size_t capacity()	zwraca ilość elementów, którą wektor jest w stanie pomieścić przed przeniesieniem go do większego obszaru pamięci.
size_t max_size()	zwraca ilość elementów, którą maksymalnie może pomieścić wektor
bool empty()	zwraca true jeśli wektor nie przechowuje żadnych zmiennych
void reserve(size_t n)	rezerwuje pamięć na n elementów, co zapobiega przenoszeniu wektora w pamięci przed osiągnięciem tej liczby
void resize(size_t n, T obj)	zmienia rozmiar wektora do n; jeśli jest większy od obecnego, dodawane są nowe elementy będące kopiami obj
void resize(size_t n)	zmienia rozmiar wektora do n; jeśli jest większy od obecnego, dodawane są nowe elementy o przypadkowych wartościach