Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2009 mgr Jerzy Wałaszek I LO w Tarnowie

Biblioteka STL - klasa vector

Praktycznie każda współczesna dystrybucja języka C++ zawiera moduł biblioteki STL (ang. Standard Template Library - biblioteka standardowych szablonów). Opis STL znajdziesz w Wikipedii. My przejdziemy od razu do praktycznych zastosowań. Pierwszą klasą szablonową, którą omówimy będzie klasa vector. Klasa ta przypomina tablicę z języka C++ - składa sie z ciagu elementów tego samego typu, które są umieszczone obok siebie w jednym bloku pamięci. W stosunku do zwykłej tablicy klasa vector zawiera wiele ulepszeń.

Dostęp do klasy szablonowej vector

Aby korzystać z tej klasy, musisz na początku swojego programu dodać wpis:

...
#include <vector>
...

Tworzenie zmiennej typu vector

Zmienną typu vector tworzy się w specyficzny sposób. Klasa szablonowa jest jakby pojemnikiem (kontenerem), który przechowuje dane pożądanego typu. Dlatego w trakcie tworzenia zmiennej musimy określić typ elementów zawartych w wektorze. Robimy to w sposób następujący:

vector<nazwa_typu_elementów> nazwa_zmiennej;

Przykłady:

Wstawianie elementów na koniec wektora

Zmienna utworzona w powyższy sposób jest pustym wektorem - tzn. nie zawierającym żadnego elementu. Elementy dodajemy do wektora przy pomocy funkcji składowej:

wektor.push_back(wartość_nowego_elementu);

Dodany element zostaje umieszczony na końcu wektora. Rozmiar wektora rośnie o 1. Informacje o aktualnym rozmiarze otrzymujemy za pomocą funkcji:

wektor.size();

Informację o tym, czy wektor coś zawiera otrzymasz przy pomocy funkcji logicznej:

wektor.empty();

Zwraca ona false, jeśli w wektorze znajduje się jakiś element, a true w przypadku pustego wektora.

Możesz się zastanawiać w jaki sposób zachowana jest ciągłość obszaru pamięci zajmowanej przez wektor, skoro zwiększa on swój rozmiar. Otóż klasa rezerwuje na potrzeby przechowywania elementów pewien obszar pamięci - np. o pojemności 1000 elementów. Dopóki elementy wstawiane do wektora mieszczą się w tym obszarze, operacja push_back() przebiega bardzo szybko. Natomiast jeśli okaże się, iż nowy element już nie mieści się w starym obszarze, to klasa zarezerwuje w pamięci nowy obszar o takiej wielkości, aby pomieścił wszystkie stare elementy oraz rezerwę 1000 następnych. Stare elementy są przepisywane do nowego obszaru, a obszar poprzedni zostaje zwolniony do systemu.

Dostęp do elementów przechowywanych w wektorze

Dostęp do elementów wektora uzyskujemy poprzez operator indeksowania [ ]:

wektor[numer_elementu]

lub przy pomocy funkcji składowej:

wektor.at(numer_elementu)

Operator [ ] nie sprawdza, czy podany indeks określa element leżący faktycznie w wektorze. Funkcja at() w przypadku wyjścia indeksu poza dozwoloną wartość dla danego wektora generuje wyjątek i zatrzymuje wykonywanie programu.

Poniższy program tworzy wektor dla liczb całkowitych typu int, umieszcza w nim dwadzieścia przypadkowych liczb z zakresu od 0 do 9 i wypisuje zawartość wektora po dodaniu każdej liczby. Liczby dodawane są na koniec wektora.

#include <iostream>
#include <vector>

using namespace std;

main()
{
  vector<int> V;  // tworzymy pusty wektor

  // inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));

  // dodajemy 20 liczb pseudolosowych

  while(V.size() < 20)
  {
    // dodajemy na koniec wektora nową liczbę pseudolosową

    V.push_back(rand() % 10);

    // wypisujemy zawartość wektora

    for(int i = 0; i < V.size(); i++)
      cout << V[i] << " ";
    cout << endl;
  }
  cout << endl;

  system("PAUSE");
}

Tworzenie wektora o zadanej liczbie elementów

Wektor możemy tworzyć od razu określając liczbę zawartych w nim elementów. W tym celu przy definicji zmiennej wykorzystujemy odpowiedni konstruktor wektora:

vector<typ_elementów> nazwa_zmiennej(liczba_elementów);

lub

vector<typ_elementów> nazwa_zmiennej(liczba_elementów,wartość_elementów);

Przykład:

vector<double> V(100);       // zostanie utworzony wektor V 100 liczb typu double
                             // o początkowej wartości 0.0

vector<double> V(100,15.25); // zostanie utworzony wektor V 100 liczb typu double
                             // każda o wartości 15.25

#include <iostream>
#include <vector>

using namespace std;

main()
{
  vector<int> V(10);  // tworzymy wektor 10 liczb

  // wyświetlamy zawartość wektora

  for(int i = 0; i < V.size(); i++)
    cout << V[i] << " ";

  cout << endl << endl;

  system("PAUSE");
}

#include <iostream>
#include <vector>

using namespace std;

main()
{
  vector<int> V(10,15);  // tworzymy wektor 10 liczb o wartości 15

  // wyświetlamy zawartość wektora

  for(int i = 0; i < V.size(); i++)
    cout << V[i] << " ";

  cout << endl << endl;

  system("PAUSE");
}

Pierwszy i ostatni element wektora

Dostęp do pierwszego elementu wektora uzyskujemy przy pomocy:

wektor[0]      // wykorzystujemy operator indeksowania
wektor.at(0)   // wykorzystujemy funkcję indeksową
wektor.front() // wykorzystujemy funkcję składową

Dostęp do ostatniego elementu wektora uzyskujemy przy pomocy:

wektor[wektor.size()-1]      // wykorzystujemy operator indeksowania
wektor.at(wektor.size()-1)   // wykorzystujemy funkcję indeksową
wektor.back()                // wykorzystujemy funkcję składową

Poniższy program tworzy wektor 10 elementowy. Umieszcza w nim liczby losowe z przedziału od 0 do 9999. Wypisuje zawartość wektora oraz pierwszy i ostatni element.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

main()
{
  vector<int> V;  // tworzymy wektor

  // inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));

  // wektor wypełniamy 10 liczbami pseudolosowymi od 0 do 9999

  while(V.size() < 10) V.push_back(rand() % 10000);

  // wyświetlamy zawartość wektora

  for(int i = 0; i < V.size(); i++)
    cout << setw(5) << V[i];

  // wyświetlamy pierwszy i ostatni element wektora

  cout << endl << endl
       << "Pierwszy: " << setw(5) << V.front() << endl
       << "Ostatni : " << setw(5) << V.back()  << endl << endl;

  system("PAUSE");
}

Iterator wektora

Iterator jest obiektem wskazującym kolejne elementy przechowywane w kontenerze klasy. Możemy go przyrównać do wskaźnika, czyli zmiennej przechowującej adres danej docelowej. Jednakże, w porównaniu ze wskaźnikiem, iterator posiada dużo większą funkcjonalność. Iterator klasy vector tworzymy następująco:

vector<typ_elementów>::iterator nazwa_zmiennej;

Przykład:

vector<int>::iterator it_int;  // tworzymy iterator elementów typu int w kontenerze typu vector

Tak utworzony iterator nie wskazuje jeszcze żadnego elementu wektora. Musimy go odpowiednio zainicjować za pomocą funkcji składowych:

iterator = wektor.begin();  // ustawienie iteratora na pierwszy element wektora

Na iteratorach wektora można wykonywać następujące działania:

* iterator              // dostęp do elementu wskazywanego przez iterator

Poniższy program tworzy wektor 10 elementowy, wypełnia go liczbami pseudolosowymi z zakresu od 0 do 99, a następnie wypisuje zawartość wektora. Dostęp do elementów poprzez iterator.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

main()
{
  vector<int> V(10);       // tworzymy wektor 10 elementowy
  vector<int>::iterator i; // tworzymy iterator do elementów wektora

  // inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));

  // wektor wypełniamy 10 liczbami pseudolosowymi od 0 do 99

  for(i = V.begin(); i != V.end(); i++)
    * i = rand() % 100;

  // wyświetlamy zawartość wektora

  for(i = V.begin(); i != V.end(); i++)
    cout << setw(3) << * i;

  cout << endl << endl;

  system("PAUSE");
}

Usuwanie elementów z wektora

Z końca wektora usuwamy elementy za pomocą funkcji:

wektor.pop_back();

Funkcja nie zwraca żadnej wartości. Jeśli chcesz pobrać element z końca wektora, to najpierw należy użyć funkcji wektor.back(), która udostępni ostatni element, a po jego przetworzeniu dopiero stosuje się wektor.pop_back(). Poniższy program tworzy wektor. Wypełnia go 10-cioma liczbami pseudolosowymi, a następnie usuwa kolejne elementy od końca.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

main()
{
  vector<int> V;  // tworzymy wektor  

  // inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));

  // wektor wypełniamy 10 liczbami pseudolosowymi od 0 do 9999  

  while(V.size() < 10) V.push_back(rand() % 10000);

  // wyświetlamy zawartość wektora i usuwamy kolejne od końca elementy

  while(!V.empty())
  {
    for(int i = 0; i < V.size(); i++) cout << setw(5) << V[i];
    cout << endl;
    V.pop_back();
  }

  cout << endl << endl;

  system("PAUSE");
}

Jeśli usuwany element znajduje się wewnątrz wektora, to używamy funkcji:

wektor.erase(iterator);              // usuwa element na pozycji wskazywanej przez iterator
wektor.erase(i_początek, i_koniec);  // usuwa elementy od pozycji iteratorów i_początek do elementu
                                     // poprzedzającego pozycję i_koniec 

Funkcja erase() zwraca iterator do elementu, który w wektorze znajdował się bezpośrednio za usuniętym elementem.

Poniższy program tworzy wektor. Wypełnia go 10-cioma liczbami pseudolosowymi, a następnie usuwa kolejne elementy od początku wektora.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

main()
{
  vector<int> V;  // tworzymy wektor

  // inicjujemy generator liczb pseudolosowych

  srand((unsigned)time(NULL));  

  // wektor wypełniamy 10 liczbami pseudolosowymi od 0 do 9999

  while(V.size() < 10) V.push_back(rand() % 10000);

  vector<int>::iterator i;  // tworzymy iterator

  i = V.begin();            // iterator ustawiamy na pierwszy element

  // wyświetlamy zawartość wektora
  // i usuwamy kolejne od początku elementy

  while(!V.empty())
  {
    for(int j = 0; j < V.size(); j++) cout << setw(5) << V[j];
    cout << endl;
    V.erase(i);
  }  

  cout << endl << endl;

  system("PAUSE");
}

Zawartość całego wektora usuwamy przy pomocy funkcji:

wektor.clear();

Wstawianie elementów do wektora

Wstawianie nowych elementów do wnętrza wektora realizujemy przy pomocy funkcji składowej:

wektor.insert(iterator,wartość);       // na pozycji iteratora zostaje umieszczona wartość

Tylko pierwsza z wersji funkcji wektor.insert() zwraca iterator wskazujący wstawiony do wektora element. Pozostałe nie zwracają żadnej wartości.

Sposób wykorzystania funkcji wektor.insert(). Tworzy on wektor 10 elementowy, a następnie wstawia do niego jeden element, pięć elementów oraz 8 elementów z innego wektora.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

main()
{
  vector<int> V1(10,5);  // tworzymy wektor 10 elementowy
  vector<int> V2(10);    // tworzymy wektor 10 elementowy

  vector<int>::iterator i_od,i_do;
      
  // inicjujemy V2 kolejnymi liczbami od 0 do 9
  
  for(int i = 0; i < V2.size(); i++) V2[i] = i;
  
  // wyświetlamy zawartość wektora V1
  
  for(int i = 0; i < V1.size(); i++) cout << setw(2) << V1[i];
  cout << endl << endl;
  
  // wstawiamy element 2 na pozycji 5 w V1
  
  V1.insert(V1.begin() + 5,2);
  for(int i = 0; i < V1.size(); i++) cout << setw(2) << V1[i];
  cout << endl << endl;
  
  // wstawiamy 5 elementów 1 od pozycji 3 w V1
  
  V1.insert(V1.begin() + 3,5,1);
  for(int i = 0; i < V1.size(); i++) cout << setw(2) << V1[i];
  cout << endl << endl;

  // wstawiamy 8 pierwszych elementów V2 do V1 od pozycji 2
  
  i_od = V2.begin();
  i_do = i_od + 8;
  V1.insert(V1.begin() + 2,i_od,i_do);
  for(int i = 0; i < V1.size(); i++) cout << setw(2) << V1[i];
  cout << endl << endl;
  
  system("PAUSE");
}