C++/Vector

Z Wikibooks, biblioteki wolnych podręczników.
< C++

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

Inne[edytuj]

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