C++/Vector

Z Wikibooks, biblioteki wolnych podręczników.

[edytuj] Vector

Klasa vector reprezentuje tablicę standardową. Dzięki niej możemy tworzyć tablice dowolnych typów. Tak jak int a[10] jest tablicą dziesięciu elementów typu int tak vector może być dowolną tablicą, dowolnego elementu i dowolnej jej liczby. Aby łatwiej sobie przyswoić klasę vector porównam ją do działań wykonywanych na normalnej tablicy znaków.

char tab[10];
tab[0] = 'a';
for (short i = 1; i < 10; i++)
	tab[i] = 'b';

Tak to by wyglądało w stylu języka C, a tak używając klasy vector. Musimy jeszcze tylko dołączyć plik nagłówkowy <vector>. Korzystając z możliwości tej klasy teraz stworzymy tablice elementów typu string a nie char, ponieważ ten typ nas bardzo ogranicza.

vector< string > tab(10);
tab[0] = "a";
for (vector< string >::size_type i = 1; i < tab.size(); ++i)
	tab[i] = "dluzsze napisy";

Składowa vector<T>::size_type jest aliasem do typu właściwego dla indeksowania elementów wektora - gwarantuje, że typ będzie miał wystarczający zakres, żeby obsłużyć całą długość wektora. Innymi słowy - rozmiar wektora (vector<T>::size()) jest właśnie typu size_type. Użycie size() zamiast stałej gwarantuje nam, że zmieniając rozmiar bufora zawsze przeiterujemy go do końca.

Obiekt vector ma kilka odmian konstruktorów. Możemy stworzyć wektor pusty, a później dodawać do niego elementy. Wtedy wektor sam będzie sie powiększał. Nie musimy znać rozmiaru podczas tworzenia obiektu.

vector < typ_elemetow > nazwa_tablicy;

Możemy też podać wielkość, co wcale nas nie ogranicza do tej wielkości. Jeżeli zabraknie miejsca obiekt sam sie powiększy.

vector < int > tab(20);

Myślę że może sie przydać jeszcze wersja konstruktora która podaje liczbę elementów i wartość jaką ma mieć każdy z nich.

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

Ta tablica będzie miała dwadzieścia elementów z czego wszystkie mają wartość: "przykladowy tekst dla kazdego elementu". Jeżeli podamy ilość elementów wtedy należy do nich odwoływać sie za pomocą operatora indeksowego [], lub czuwającą żeby nie wyjść poza zakres elementów metodą at(). Natomiast jeżeli nie podamy ilości wtedy trzeba najpierw utworzyć każdy kolejny element, czynimy to metodą push_back(). Ta metoda dodaje nowy element na koniec tablicy. Po dodaniu nowych elementów możemy sie do nich odwoływać indeksowo []. Możemy też sprawdzić ile obecnie jest elementów metodą size(), a metoda empty() powie nam czy przypadkiem wektor nie jest pusty. Dalsze wnikanie w możliwości klasy vector wymaga poznania iteratorów – inaczej wskaźniki. Jak wiemy do poruszania sie po elementach tablicy takich jak int a[10] można używać wskaźnika jakim jest a. Tak samo operacje na obiektach wektora można dokonać używając iteratorów i algorytmów uogólnionych. Rzućmy wiec okiem na te iteratory. Deklaracja iteratora wygląda podobnie do deklaracji wektora. Zadeklarujemy wektor 10 elementów typu string i dwa iteratory do niego. Pierwszy będzie wskazywał na pierwszy element, a drugi na pierwszy po ostatnim. Do uzyskania takich iteratorów służą metody begin() i end(), które zwracają iterator odpowiednio do pierwszego i następnego po ostatnim (nie ostatniego) elementu.

vector<string> tabStr(10,"0");

vector<string>::iterator iter1;
vector<string>::iterator iter2;

iter1 = tabStr.begin();
iter2 = tabStr.end();

Mając takie iteratory możemy sie nimi posługiwać na wzór standardowych wskaźników. Można go wyłuskać, używać operatorów arytmetycznych ++, -- i logicznych. Poniższy program to ilustruje.

#include <string>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[])
{
    vector<string> tabStr(10,"0");
    vector<string>::iterator iter1;
    vector<string>::iterator iter2;
    
    iter1 = tabStr.begin();
    iter2 = tabStr.end();
    
    for (int a = 0; iter1 != iter2; ++iter1, ++a )
    {
        if (a % 2 == 0)
           *iter1 = "1";
        
        cout << *iter1 << endl;
    }
    
    cin.get();
    return 0;
}

Wynik działania:

1
0
1
0
1
0
1
0
1
0

Ale iteratory są o wiele bardziej skomplikowane niż tu zostało to przedstawione. Jest pięć rodzajów iteratorów ogólnych, bo każda klasa taka jak vector ma w sobie zdefiniowany iterator. Iteratory będziemy wykorzystywać prawie w każdym kontenerze (struktura do przechowywania danych) jakim jest np. vector. Teraz, kiedy już wiemy, co to są iteratory, możemy przejść do metod klasy vector i algorytmów uogólnionych, które działają najlepiej na tych iteratorach. Klasa vector nie ma sama w sobie zbyt wiele metod do ciekawych operacji, ale tego braku uzupełnieniem jest zbiór algorytmów uogólnionych, o których będę pisał później.

[edytuj] Metody

Lista metod klasy vector (gdzie iterator to vector<T>::iterator - podmiana dla czytelności):

prototyp	opis działania
void swap(vector vec)	zamienia zawartości dwóch wektorów miejscami (wykonywane szybko, w stałym czasie)
size_t size()	zwraca obecną ilość 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
void push_back(const T obj)	dodaje na końcu wektora kopię przekazanego argumentu
void pop_back()	usuwa ostatni element z wektora (wykonywane w stałym czasie)
void clear()	usuwa wszystkie elementy z wektora
void assign(size_t n, const T obj)	czyści wektor i wypełnia go n kopiami argumentu obj
iterator assign(iterator poczatek, iterator koniec)	czyści wektor i wypełnia go elementami z innego wektora z przedziału <poczatek;koniec>
iterator insert(iterator pos, T obj)	wstawia element obj przed wskazywaną przez iterator pos pozycją i zwraca iterator do dostawionego elementu (powolna funkcja)
void insert(iterator pos, size_t n, const T obj)	wstawia n kopii argumentu obj przed pozycją wskazywaną przez iterator pos
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)
iterator erase(iterator pos)	usuwa element wskazywany przez pos i zwraca iterator do następnego elementu
iterator erase(iterator poczatek, iterator koniec)	usuwa elementy z przedziału <poczatek;koniec> i zwraca iterator do elementu za nimi
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

Uwaga! Przenoszenie wektora w pamięci spowodowane przekroczeniem capacity() jest powolnym procesem, zwłaszcza przy dużych wektorach. Jeśli to możliwe, należy przed przystąpieniem do korzystania z wektora, zarezerwować metodą reserve(size_t n) ilość elementów, która powinna wystarczyć. Często jednak jest to nieuniknione, więc należy starać się o przechowywanie jak najmniejszych elementów (np. zamiast obszernych obiektów, przechowywać w wektorze same wskaźniki na nie). Po przeniesieniu wektora w pamięci wszystkie elementy posiadają inny adres, dlatego nie należy wskazywać na nie wskaźnikami, gdyż mogą stracić ważność.