Vector

edytuj

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

edytuj

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?

edytuj

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

edytuj

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

edytuj

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

Modyfikacja

edytuj
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

edytuj
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
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