PROGRAMOWANIE I ALGORYTMY

vector - ulepszona tablica


vector jest strukturą, która na pierwszy rzut oka wygląda jak zwykła tablica. Oprócz funkcjonalności zwykłej tablicy vectory posiadają wiele przydatnych funkcji i ulepszeń.

Przypomnijmy więc, jakie zastosowanie w programowaniu ma tablica. Załóżmy, że musisz przechować milion liczb całkowitych. Przygotuj więc milion pudełek, gdzie w każdym pudełku może znajdować się jedna taka liczba i ponumeruj je od 0 do milion - 1. Pudełka te znajdują się w pokoju o ustalonej nazwie — tą nazwą jest nazwa tablicy. Teraz jedynie co musisz wiedzieć, to jak jej używać. Wystarczy, że podasz nazwę pokoju (nazwę tablicy), a w nawiasie kwadratowym podasz numer pudełka (numer komórki tablicy).

W praktyce wektory działają na tej samej zasadzie, tylko że nie musisz z góry określać liczby pudełek, możesz je dokładać i usuwać w dowolnym momencie. Co więcej, od razu możesz przypisać do każdego pudełka ustaloną liczbę. Nie musisz przejmować się alokacją pamięci, ponieważ dodając kolejne elementy, pamięć będzie rozszerzana automatycznie. Aby korzystać z wektorów, należy w nagłówku programu dołączyć bibliotekę

#include <vector>

Tworzenie vectora

Możesz utworzyć pusty wektor, bez przypisanej liczby elementów (sam pokój, bez pudełek). W miarę potrzeb możesz dokładać elementy na koniec wektora (dokładać kolejne pudełka do pokoju).

vector <typ elementów wektora> nazwa_wektora;

Np.:

vector <int > tab;

Jeśli jednak potrzebujesz na początku określić liczbę elementów wektora, możesz to zrobić w następujący sposób:

vector <typ elementów wektora> nazwa_wektora(liczba_elementów);

Np.:

vector <int > tab(1000000);

W sytuacji, gdy określasz liczbę elementów w wektorze, możesz od razu przypisać do każdego z nich ustaloną wartość:

vector <typ elementów wektora> nazwa_wektora(liczba_elementów, ustalona_wartość);

Np.:

vector <int > tab(1000000, 1);

Podczas inicjacji wektora możesz zdefiniować zwoje wartości, które chcesz, aby były przypisane do kolejnych pozycji:

//algorytm.edu.pl
#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector <int> liczby = {1, 2, 3, 4, 5};
	
	//wypisanie elementów wektora
	for(int i=0; i<liczby.size(); i++)
		cout<<liczby[i]<<' ';
	
	return 0;
}

Dodawanie kolejnych elementów do wektora

Aby dodać nowy element na koniec wektora, należy użyć metody push_back(element);. Aby użyć tej metody, musisz podać nazwę wektora, a następnie po kropce wpisać push_back(element) i w nawiasie podać wartość elementu np.:

vector <int > tab;
tab.push_back(3);
int a = 4;
tab.push_back(a);

W pierwszym pudełku o numerze 0 będzie przechowywana liczba 3, natomiast w pudełku o numerze 1 będzie liczba 4.

Odwoływanie się do elementów wektora

Aby sprawdzić, jaka wartość znajduje się w pudełku o zadanym numerze (indeksie), należy użyć operatora [ ]— nawiasu kwadratowego, a wewnątrz niego należy wpisać numer komórki (musi istnieć komórka o zadanym indeksie).

vector <int > tab;
tab.push_back(3);
int a = 4;
tab.push_back(a);
cout<<tab[0]<<' '<<tab[1]; //3 4
cin>>tab[0]; //przypisanie nowej wartości do komórki o numerze 0

Przykład 1

Napisz program, który będzie pobierał liczby całkowite do momentu napotkania wartości zero, a następnie wypisze te liczby (bez zera) w odwróconej kolejności

//algorytm.edu.pl
#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector <int> tab;
	int a;
	
	cin>>a;
	while(a != 0)
	{
		//dodanie elementu do wektora
		tab.push_back(a); //np. 1 2 3 0
		cin>>a;
	}
	
	//wypisanie liczb w odwróconej kolejności
	for(int i = tab.size()-1; i >= 0; i--)
		cout<<tab[i]<<' '; //3 2 1
		
	//sposób II wpisania liczb w odwróconej kolejności
	while(!tab.empty()) //dopóki są jakieś elementy w wektorze
	{
		cout<<tab.back()<<' ';//wypisanie elementu stojącego na końcu wektora
		tab.pop_back();			//usunięcie ostatniego elementu w wektorze
	}
	return 0;
}

Uwaga! Metoda size() zwraca liczbę elementów w wektorze.

Porządkowanie elementów

//algorytm.edu.pl
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
	vector <int> tab;
	int a;
	
	cout<<<"Wczytaj 5 liczb całkowitych: ";
	for(int i=0; i<5; i++) //np. 4 3 5 6 2
	{
		cin>>a;
		tab.push_back(a);
	}
	
	sort(tab.begin(), tab.end()); //sortowanie elementów rosnąco
	
	/*
		//sortowanie elementów malejąco
		sort(tab.begin(), tab.end(), greater  ()); 
	*/
	
	/*
		//sortowanie podzbioru — pierwsze dwa nie będą uczestniczyły w sortowaniu
		sort(tab.begin() + 2, tab.end(), greater  ()); 
	*/
	
	for(int i=0; i<5; i++) //2 3 4 5 6
		cout<<tab[i]<<' ';
		
	return 0;
}

Tablica wektorów

Wyobraź sobie, że potrzebujesz przechowywać dane w 100 pokojach, a w każdym z nich jest pewna liczba pudełek. Zarówno pokoje, jak i pudełka indeksujemy od zera. W ten sposób tworzymy tablicę wektorów:

vector <int> tab [100];
tab[10].push_back(199); //do pokoju o numerze 10 dodaję liczbę 199 do pudełka o numerze 0
tab[10].push_back(1); //do pokoju o numerze 10 dodaję liczbę 1 do pudełka o numerze 1
tab[0].push_back(99); //do pokoju o numerze 0 dodaję liczbę 99 do pudełka o numerze 1
cout<<tab[10][1]; //wypisuję zawartość pudełka o numerze 1 w pokoju o numerze 10: 1

vektor wektorów

Jeśli nie wiesz ile będziesz potrzebował pokoi oraz ile w każdym z nich będziesz umieszczał pudełek, warto stworzyć vektor wektorów. Inaczej mówiąc, typ każdego z elementów wektora będzie wektorem:

vector < vector<int> > tab;
vector <int> pom;

pom.push_back(1);
pom.push_back(2);
pom.push_back(3);

tab.push_back(pom); //wrzuć do komórki wektora o numerze 0 (do pokoju o numerze 0) wektor z liczbami 1, 2 i 3 (pudełka z liczbami 1, 2 i 3
tab.push_back(pom); //wrzuć do komórki wektora o numerze 1 wektor z liczbami 1, 2 i 3

cout<<tab[1][2]; //wypisuję zawartość pudełka o numerze 2 w pokoju o numerze 1: 3

Przydatne metody