Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2013 mgr
Jerzy Wałaszek
|
Dane dodajemy do tablicy za pomocą wybranej funkcji. Dodanie danych polega zawsze na zwiększeniu o 1 wartości c. Dlatego przed dodaniem nowego elementu sprawdzamy, czy c jest mniejsze od n. Jeśli tak, to w tablicy jest miejsce na dodatkowy element. Wstawiamy go i zwiększamy c o 1.
Jeśli natomiast c jest równe n, to tablica została już w całości zapełniona. W takim przypadku należy utworzyć nową tablicę, np. o rozmiarze n + DT (gdzie DT oznacza pewien zapas komórek, np. 5, 10, 100 – zależy to od przewidywanej intensywności dodawania elementów do tablicy), przepisać do niej zawartość starej tablicy, starą tablicę usunąć z pamięci i adres nowej tablicy zapamiętać w T, zwiększając równocześnie n o DT. Po tych operacjach T wskazuje nową, większą tablicę, która zawiera informację przechowywaną przez poprzednią tablicę dynamiczną. Możemy zatem dodać dane do tablicy.
Dane możemy również usuwać z tablicy. W tym przypadku maleje jej rozmiar c. Możemy się umówić, że jeśli po wykonaniem operacji zmniejszenia c = n - 2DT, to, podobnie jak przy zwiększaniu, tworzymy nową tablicę o rozmiarze n - DT, przepisujemy do niej starą, starą usuwamy, a za n przyjmujemy n - DT. W ten sposób tablica będzie przechowywała zawsze co najwyżej DT elementów więcej niż wynosi liczba wprowadzonych do niej danych.
W podejściu funkcyjnym problem ten rozwiązujemy przy pomocy kilku funkcji. Funkcje te muszą posiadać dostęp do T, n i c. Najlepiej zatem będzie umieścić te dane w strukturze, a do funkcji przekazywać referencję do tej struktury. Umówmy się, że referencja ta będzie przekazywana w pierwszym parametrze każdej funkcji. Oto elementy, które będą nam potrzebne (nazwy zostały dobrane w specjalny sposób, co zrozumiesz później – nie zmieniaj ich):
struct Vector { int * T,n,c; }; |
– | struktura zawierająca tablicę dynamiczną T, jej rozmiar n oraz aktualnie przechowywaną liczbę elementów c. |
V_init(Vector & v) |
– | funkcja inicjuje strukturę v. Tworzy tablicę dynamiczną T o DT elementach, wpisuje DT do n i 0 do c. |
V_empty(Vector & v) |
– | zwraca true, jeśli tablica T jest pusta, czyli nie zawiera żadnego elementu. |
V_size(Vector & v) |
– | zwraca c. |
V_enlarge(Vector & v) |
– | zwiększa o DT aktualny rozmiar tablicy T, jeśli c = n. |
V_shrink(Vector & v) |
– | zmniejsza o DT aktualny rozmiar tablicy T, jeśli c = n - 2DT. |
V_push_back(Vector & v, int x) |
– | dodaje do końca tablicy wartość x. |
V_push_front(Vector & v, int x) |
– | dodaje x na początku tablicy. |
V_pop_back(Vector & v) |
– | usuwa ostatni element tablicy. |
V_pop_front(Vector & v) |
– | usuwa pierwszy element tablicy. |
V_back(Vector & v) |
– | zwraca referencję do ostatniego elementu tablicy. |
V_front(Vector & v) |
– | zwraca referencję do pierwszego elementu tablicy. |
V_at(Vector & v, int i) |
– | zwraca referencję do elementu T[i]. |
V_erase(Vector & v, int i) |
– | usuwa element na pozycji i-tej. |
V_insert(Vector & v, int i, int x) |
– | wstawia element x na pozycję i-tą. |
V_print(Vector & v) |
– | wypisuje aktualną zawartość tablicy w czytelny sposób. |
V_destroy(Vector & v) |
– | usuwa tablicę dynamiczną T. |
Program jest następujący:
// Koło Informatyczne I LO w Tarnowie // (C)2013 mgr Jerzy Wałaszek // Tablica o dynamicznym rozmiarze // PRG_001 //----------------------------------- #include <iostream> using namespace std; // Struktura tablicy dynamicznej //------------------------------ struct Vector { int *T,n,c; }; // Funkcje obsługujące strukturę Vector //------------------------------------- const int DT = 5; // Zapas elementów w tablicy // Inicjuje strukturę Vector //-------------------------- void V_init(Vector & v) { v.n = DT; // Początkowy rozmiar v.c = 0; // Początkowa liczba elementów v.T = new int[v.n]; // Tworzymy dynamicznie tablicę } // Zwraca true, jeśli tablica jest pusta //-------------------------------------- bool V_empty(Vector & v) { return !v.c; } // Zwraca liczbę elementów w tablicy //---------------------------------- int V_size(Vector & v) { return v.c; } // Zwiększa o DT rozmiar tablicy T //-------------------------------- void V_enlarge(Vector & v) { if(v.c == v.n) { int *p,i; v.n += DT; // Zwiększamy rozmiar o DT p = new int [v.n]; // Tworzymy nową tablicę o zwiększonym rozmiarze for(i = 0; i < v.c; i++) // Starą tablicę przenosimy do nowej p[i] = v.T[i]; delete [] v.T; // Usuwamy starą tablicę v.T = p; // Nowa tablica staje się tablicą T } } // Zmniejsza o DT rozmiar tablict T //--------------------------------- void V_shrink(Vector & v) { if(v.c == v.n - DT - DT) { int * p,i; v.n -= DT; // Zmniejszamy rozmiar o DT p = new int [v.n]; // Tworzymy nową tablicę o zmniejszonym rozmiarze for(i = 0; i < v.c; i++) // Starą tablicę przenosimy do nowej p[i] = v.T[i]; delete [] v.T; // Usuwamy starą tablicę v.T = p; // Nowa tablica staje się tablicą T } } // Dodaje element na koniec tablicy //--------------------------------- void V_push_back(Vector & v, int x) { V_enlarge(v); // W razie potrzeby zwiększamy rozmiar T v.T[v.c++] = x; // x umieszczamy w tablicy } // Dodaje element na początek tablicy //----------------------------------- void V_push_front(Vector & v, int x) { V_enlarge(v); // W razie potrzeby zwiększamy rozmiar T for(int i = v.c; i > 0; i--) v.T[i] = v.T[i-1]; // Przesuwamy elementy v.T[0] = x; // W zwolnione miejsce wstawiamy x v.c++; // Tablica zawiera więcej elementów } // Usuwa z tablicy T ostatni element //---------------------------------- void V_pop_back(Vector & v) { if(v.c) // Jeśli w tablicy T są jakieś elementy { v.c--; // Usuwamy ostatni V_shrink(v); // W razie potrzeby zmniejszamy rozmiar T } } // Usuwa z tablicy T pierwszy element //----------------------------------- void V_pop_front(Vector & v) { if(v.c) // Jeśli w tablicy T są jakieś elementy { v.c--; // Usuwamy pierwszy for(int i = 0; i < v.c; i++) v.T[i] = v.T[i + 1]; V_shrink(v); // W razie potrzeby zmniejszamy rozmiar T } } // Zwraca referencję do pierwszego elementu tablicy //------------------------------------------------- int & V_front(Vector & v) { return v.T[0]; } // Zwraca referencję do ostatniego elementu tablicy //------------------------------------------------- int & V_back(Vector & v) { return v.T[v.c-1]; } // Zwraca referencję do i-tego elementu tablicy //--------------------------------------------- int & V_at(Vector & v, int i) { return v.T[i]; } // Usuwa i-ty element tablicy T //----------------------------- void V_erase(Vector & v, int i) { if(v.c && (i < v.c)) { v.c--; // Zmniejszamy rozmiar T for(int j = i; j < v.c; j++) v.T[j] = v.T[j + 1]; V_shrink(v); } } // Wstawia x na pozycję i-tą //-------------------------- void V_insert(Vector & v, int i, int x) { if(i < v.c) { V_enlarge(v); for(int j = v.c; j > i; j--) v.T[j] = v.T[j - 1]; v.T[i] = x; v.c++; } } // Wyświetla zawartość tablicy T //------------------------------ void V_print(Vector & v) { for(int i = 0; i < v.c; i++) cout << "T[" << i << "] = " << v.T[i] << endl; cout << endl; } // Usuwa tablicę dynamiczną //------------------------- void V_destroy(Vector & v) { delete [] v.T; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { Vector a; // Tworzymy strukturę tablicy V_init(a); // Inicjujemy tę strukturę for(int i = 0; i < 5; i++) V_push_back(a,i+1); // Wstawiamy 5 elementów V_print(a); // Wyświetlamy tablicę V_push_back(a,10); // Na koniec wstawiamy 10 V_push_front(a,20); // Na początek wstawiamy 20 V_print(a); V_pop_back(a); // Usuwamy ostatni element V_pop_front(a); // Usuwamy pierwszy element V_insert(a,3,100); // Na pozycję 3 wstawiamy kolejno 100, 200 i 300 V_insert(a,3,200); V_insert(a,3,300); V_print(a); V_erase(a,4); // Usuwamy elementy 4 i 1 V_erase(a,1); V_print(a); V_destroy(a); // Usuwamy tablicę dynamiczną system("pause"); return 0; } |
Zwróć uwagę na to, że funkcje obsługujące strukturę Vector otrzymują referencję do niej w pierwszym parametrze. Dzięki temu mają pełny dostęp do pól tej struktury. Zamiast referencji można również przekazywać wskaźnik do struktury. Wtedy dostęp do jej pól odbywa się poprzez operator strzałki ->.
Teraz to samo zaprogramujemy, wykorzystując programowanie obiektowe.
// Koło Informatyczne I LO w Tarnowie // (C)2013 mgr Jerzy Wałaszek // Tablica o dynamicznym rozmiarze // PRG_002 //----------------------------------- #include <iostream> using namespace std; // Definicja klasy //---------------- class Vector { protected: int *T,n,c; void enlarge(); void shrink(); public: Vector(); ~Vector() { delete [] T; } bool empty() { return !c; } int size() { return c; } void push_back(int x); void push_front(int x); void pop_back(); void pop_front(); int & back() { return T[c-1]; } int & front() { return T[0]; } int & at(int i) { return T[i]; } void erase(int i); void insert(int i, int x); void print(); }; // Metody klasy Vector //------------------------------------- const int DT = 5; // Zapas elementów w tablicy // Konstruktor //------------ Vector::Vector() { n = DT; // Początkowy rozmiar c = 0; // Początkowa liczba elementów T = new int[n]; // Tworzymy dynamicznie tablicę } // Zwiększa o DT rozmiar tablicy T //-------------------------------- void Vector::enlarge() { if(c == n) { int *p,i; n += DT; // Zwiększamy rozmiar o DT p = new int [n]; // Tworzymy nową tablicę o zwiększonym rozmiarze for(i = 0; i < c; i++) // Starą tablicę przenosimy do nowej p[i] = T[i]; delete [] T; // Usuwamy starą tablicę T = p; // Nowa tablica staje się tablicą T } } // Zmniejsza o DT rozmiar tablict T //--------------------------------- void Vector::shrink() { if(c == n - DT - DT) { int * p,i; n -= DT; // Zmniejszamy rozmiar o DT p = new int [n]; // Tworzymy nową tablicę o zmniejszonym rozmiarze for(i = 0; i < c; i++) // Starą tablicę przenosimy do nowej p[i] = T[i]; delete [] T; // Usuwamy starą tablicę T = p; // Nowa tablica staje się tablicą T } } // Dodaje element na koniec tablicy //--------------------------------- void Vector::push_back(int x) { enlarge(); // W razie potrzeby zwiększamy rozmiar T T[c++] = x; // x umieszczamy w tablicy } // Dodaje element na początek tablicy //----------------------------------- void Vector::push_front(int x) { enlarge(); // W razie potrzeby zwiększamy rozmiar T for(int i = c; i > 0; i--) T[i] = T[i-1]; // Przesuwamy elementy T[0] = x; // W zwolnione miejsce wstawiamy x c++; // Tablica zawiera więcej elementów } // Usuwa z tablicy T ostatni element //---------------------------------- void Vector::pop_back() { if(c) // Jeśli w tablicy T są jakieś elementy { c--; // Usuwamy ostatni shrink(); // W razie potrzeby zmniejszamy rozmiar T } } // Usuwa z tablicy T pierwszy element //----------------------------------- void Vector::pop_front() { if(c) // Jeśli w tablicy T są jakieś elementy { c--; // Usuwamy pierwszy for(int i = 0; i < c; i++) T[i] = T[i + 1]; shrink(); // W razie potrzeby zmniejszamy rozmiar T } } // Usuwa i-ty element tablicy T //----------------------------- void Vector::erase(int i) { if(c && (i < c)) { c--; // Zmniejszamy rozmiar T for(int j = i; j < c; j++) T[j] = T[j + 1]; shrink(); } } // Wstawia x na pozycję i-tą //-------------------------- void Vector::insert(int i, int x) { if(i < c) { enlarge(); for(int j = c; j > i; j--) T[j] = T[j - 1]; T[i] = x; c++; } } // Wyświetla zawartość tablicy T //------------------------------ void Vector::print() { for(int i = 0; i < c; i++) cout << "T[" << i << "] = " << T[i] << endl; cout << endl; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { Vector a; // Tworzymy klasę for(int i = 0; i < 5; i++) a.push_back(i+1); // Wstawiamy 5 elementów a.print(); // Wyświetlamy tablicę a.push_back(10); // Na koniec wstawiamy 10 a.push_front(20); // Na początek wstawiamy 20 a.print(); a.pop_back(); // Usuwamy ostatni element a.pop_front(); // Usuwamy pierwszy element a.insert(3,100); // Na pozycję 3 wstawiamy kolejno 100, 200 i 300 a.insert(3,200); a.insert(3,300); a.print(); a.erase(4); // Usuwamy elementy 4 i 1 a.erase(1); a.print(); a.front() = a.back(); a.at(1) = a.at(a.size()-2); a.print(); system("pause"); return 0; } |
Przyglądnijmy się różnicom w obu programach.
Wersja funkcyjna | Wersja obiektowa | |||
|
|
W strukturze Vector mamy jedynie pola danych. W klasie Vector, oprócz pól danych, mamy również definicje funkcji, które z tą klasą współpracują. Funkcje takie nazywamy metodami (ang. methods) lub funkcjami składowymi (ang. member functions).
Dalej widzimy w klasie Vector dwa słowa kluczowe:
Jeśli metoda klasy jest krótka, to jej część wykonawczą możemy umieścić bezpośrednio w definicji klasy. U nas zrobiliśmy tak z metodami:
~Vector() { delete [] T;} bool empty() { return !c; } int size() { return c; } int & front() { return T[0]; } int & back() { return T[c-1]; } int & at(int i) {return T[i]; } |
Tak zdefiniowane metody tworzą tzw. funkcje inline. Różnią się one tym od innych funkcji, że kompilator przy każdym odwołaniu do nich wstawia do programu ich kod. Dzięki temu wykonują się szybciej, ale program zajmuje oczywiście więcej miejsca. Z tego powodu funkcje inline powinny być krótkie.
Klasa posiada dwie metody specjalne, które nazywamy konstruktorem i destruktorem. Cechą charakterystyczną tych metod jest to, iż mają one taką samą nazwę jak nazwa klasy.
Zadaniem konstruktora jest budowa klasy. Jest on zawsze wywoływany przez program wtedy, gdy klasa jest tworzona w pamięci, gdy rozpoczyna swoje istnienie. W przypadku naszej klasy konstruktor inicjuje jej pola n i c oraz przydziela wstępnie DT komórek tablicy dynamicznej T:
// Konstruktor //------------ Vector::Vector() { n = DT; // Początkowy rozmiar c = 0; // Początkowa liczba elementów T = new int[n]; // Tworzymy dynamicznie tablicę } |
W wersji funkcyjnej musieliśmy osobiście wywołać funkcję V_init()
do zainicjowania pól struktury Vector. W wersji obiektowej klasa sama dba o
swoją inicjalizację – jeśli zdefiniujesz dla niej odpowiedni konstruktor, to
użyje go ona na początku swojego życia w pamięci.
Destruktor ma z kolei za zadanie czysto usunąć klasę z pamięci, gdy przestaje ona istnieć. Ponieważ nasza klasa rezerwuje obszar dla tablicy dynamicznej T, to destruktor zwraca ten obszar z powrotem do systemu. Gdyby tego nie robił, to mógłby powstać wyciek pamięci (ang. memory leak) (jeśli program się kończy, jak w tym przypadku, to cała zarezerwowana przez niego pamięć i tak trafia do systemu, jednakże przy tworzeniu klas lokalnych w funkcjach zawsze należy zwracać zarezerwowane zasoby, a destruktory dbają o to automatycznie).
~Vector() { delete [] T;}
Kolejna różnica dotyczy samych funkcji i metod. Weźmy dla przykładu funkcję wstawiającą element na początek tablicy:
Wersja funkcyjna | Wersja obiektowa | |||
|
|
Nazwa metody jest poprzedzona nazwą klasy Vector oraz operatorem :: (operator czterokropek, operator zakresu). Informuje to kompilator, że definicja dotyczy metody należącej do klasy Vector.
Kolejna różnica, to brak na liście parametrów metody referencji do obiektu zmiennej. W wersji funkcyjnej parametr ten musi zostać jawnie podany, aby funkcja miała dostęp do pól struktury, na których ma przeprowadzić jakieś działania. W przypadku klasy wszystkie jej metody dostają automatycznie tę referencję w ukrytym pierwszym parametrze. Parametr ten nazywa się this i jest wskaźnikiem aktualnej zmiennej klasy, na której operuje metoda. Zwykle nie musimy z niego jawnie korzystać.
W wersji funkcyjnej dostęp do pól struktury odbywa się zawsze poprzez parametr, który funkcja otrzymała przy wywołaniu. U nas parametr ten nazywa się v. W wersji obiektowej zmienna klasy jest domyślna i pól oraz funkcji składowych nie musimy jawnie niczym poprzedzać. Oczywiście, na upartego moglibyśmy skorzystać z tego ukrytego parametru this w sposób następujący:
void Vector::push_front(int x) { if(this->c == this->n) enlarge(); // W razie potrzeby zwiększamy rozmiar T for(int i = this->c; i > 0; i--) this->T[i] = this->T[i-1]; // Przesuwamy elementy this->T[0] = x; // W zwolnione miejsce wstawiamy x this->c++; // Tablica zawiera więcej elementów } |
Ale i tak robi to automatycznie kompilator, więc tutaj nie ma to specjalnie sensu.
void pisz(int a) { cout << "LICZBA CALKOWITA : " << a << endl; } void pisz(double a) { cout << "LICZBA RZECZYWISTA : " << a << endl; } |
Jeśli wywołamy funkcję pisz() z argumentem typu int, to zostanie wykonana pierwsza funkcja. Jeśli natomiast argument będzie typu zmiennoprzecinkowego, to wywołana zostanie funkcja druga:
pisz(2); // LICZBA CALKOWITA : 2 pisz(3.5); // LICZBA RZECZYWISTA : 3.5 |
Drugą ciekawą cechą języka C++ są tzw. parametry domyślne. Jeśli stworzymy następującą definicję funkcji:
void zwieksz(int & a, int ile=1) { a += ile; } |
To wywołanie zwieksz(x)
spowoduje dodanie do x
1, ponieważ pominięty parametr ile w wywołaniu otrzyma wartość
domyślną 1. Natomiast wywołanie zwiększ(x,2)
spowoduje
zwiększenie x o 2, ponieważ parametr ile został
podany jawnie.
Wykorzystamy teraz tę wiedzę do dodania do naszej klasy dodatkowego konstruktora, który tworzy wstępnie tablicę o zadanej ilości elementów i wypełnia ją podaną wartością lub zerami. W tym celu dopisz do definicji klasy drugi konstruktor:
// Definicja klasy //---------------- class Vector { protected: int *T,n,c; void enlarge(); void shrink(); public: Vector(); // Konstruktor standardowy Vector(int nn, int vv=0); // Konstruktor przeładowany ~Vector() { delete [] T; } bool empty() { return !c; } int size() { return c; } void push_back(int x); void push_front(int x); void pop_back(); void pop_front(); int & back() { return T[c-1]; } int & front() { return T[0]; } int & at(int i) { return T[i]; } void erase(int i); void insert(int i, int x); void print(); }; |
Poniżej dopisz do programu definicję tego dodatkowego konstruktora:
// Konstruktor przeładowany //------------------------- Vector::Vector(int nn, int vv) { c = nn; // Liczba komórek z danymi n = nn + DT; // Rozmiar tablicy z zapasem T = new int[n]; // Tworzymy tablicę i wypełniamy ją vv for(int i = 0; i < c; i++) T[i] = vv; } |
Teraz możemy tworzyć zmienną klasy na kilka sposobów:
Vector a; |
– | standardowo, pusta tablica |
Vector a(100); |
– | tablica ze 100 elementami o wartości 0 |
Vector a(100,5) |
– | tablica ze 100 elementami o wartości 5 |
Operatory w języku C++ również są funkcjami i możemy je przeciążać. Nazwami tych funkcji są symbole operatorów. Dla przykładu przeciążmy operator [ ]. Operator ten stosowany jest przy dostępie do elementu tablicy. Zwraca on referencję do elementu o podanym indeksie. Dopisz w definicji klasy:
// Definicja klasy //---------------- class Vector { protected: int *T,n,c; void enlarge(); void shrink(); public: Vector(); // Konstruktor standardowy Vector(int nn, int vv=0); // Konstruktor przeładowany ~Vector() { delete [] T; } bool empty() { return !c; } int size() { return c; } void push_back(int x); void push_front(int x); void pop_back(); void pop_front(); int & back() { return T[c-1]; } int & front() { return T[0]; } int & at(int i) { return T[i]; } void erase(int i); void insert(int i, int x); void print(); int & operator [](int i) { return T[i]; } }; |
Funkcja obsługi operatora [ ] jest tutaj bardzo prosta, zatem uczyniliśmy ją funkcją inline. Przykładowy program:
// ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { Vector a(20); a[0] = 0; a[1] = 1; for(int i = 2; i < 20; i++) a[i] = a[i-2] + a[i-1]; a.print(); system("pause"); return 0; } |
Uwaga: Operator [ ] nie sprawdza, czy indeks faktycznie wskazuje element tablicy. Jeśli nie, może wystąpić błąd dostępu do pamięci lub inne dziwne zachowania.
Kolejnym krokiem będzie zastosowanie tzw. szablonów (ang. templates). Chodzi o to, że nasza klasa tworzy tablicę o elementach typu int. A jeśli potrzebowalibyśmy tablicy o elementach char, bool, double lub innych? Cóż, należałoby odpowiednio pozmieniać typy danych w wielu metodach klasy. Na szczęście C++ pozwala programiście zrobić to automatycznie.
Co to jest klasa szablonowa (ang. template class) w C++? Otóż jest to klasa, w której operujemy typem ogólnym zamiast typu konkretnego. Typ ogólny wprowadza się za pomocą słowa kluczowego:
template <class nazwa_typu_ogólnego>
Od tego momentu w obiekcie, który następuje bezpośrednio dalej, możemy używać wprowadzonej nazwy jako nazwy typu. Na przykład stwórzmy prostą klasę szablonową:
template <class T> class Szablon { protected: T a; // Pole typu T public: T dodaj(T x) { return x += a; } }; |
Aby teraz utworzyć zmienną klasy, musisz podać typ, który zastąpi typ ogólny:
Szablon <int> k_int; // powstanie klasa, gdzie T = int Szablon <double> k_dbl; // powstanie klasa, gdzie T = double |
Dzięki temu rozwiązaniu nie musimy ręcznie zmieniać typu danej w klasie – po prostu kompilator utworzy klasę, gdzie każde wystąpienie typu ogólnego zostanie zastąpione przez typ podany w definicji zmiennej.
Przeróbmy teraz naszą klasę na klasę szablonową:
// Koło Informatyczne I LO w Tarnowie // (C)2013 mgr Jerzy Wałaszek // Tablica o dynamicznym rozmiarze // PRG_003 //----------------------------------- #include <iostream> using namespace std; // Definicja klasy szablonowej // X - typ ogólny //---------------------------- template <class X> class Vector { protected: X * T; // szablonowa tablica dynamiczna int n,c; void enlarge(); void shrink(); public: Vector(); // Konstruktor standardowy Vector(int nn, X vv=0); // Konstruktor przeładowany ~Vector() { delete [] T; } bool empty() { return !c; } int size() { return c; } void push_back(X x); void push_front(X x); void pop_back(); void pop_front(); X & back() { return T[c-1]; } X & front() { return T[0]; } X & at(int i) { return T[i]; } void erase(int i); void insert(int i, X x); void print(); X & operator [](int i) { return T[i]; } }; // Metody klasy Vector //------------------------------------- const int DT = 5; // Zapas elementów w tablicy // Konstruktor //------------ template <class X> Vector<X>::Vector() { n = DT; // Początkowy rozmiar c = 0; // Początkowa liczba elementów T = new X [n]; // Tworzymy dynamicznie tablicę } // Konstruktor przeładowany //------------------------- template <class X> Vector<X>::Vector(int nn, X vv) { c = nn; // Liczba komórek z danymi n = nn + DT; // Rozmiar tablicy z zapasem T = new X [n]; // Tworzymy tablicę i wypełniamy ją vv for(int i = 0; i < c; i++) T[i] = vv; } // Zwiększa o DT rozmiar tablicy T //-------------------------------- template <class X> void Vector<X>::enlarge() { if(c == n) { X *p; int i; n += DT; // Zwiększamy rozmiar o DT p = new X [n]; // Tworzymy nową tablicę o zwiększonym rozmiarze for(i = 0; i < c; i++) // Starą tablicę przenosimy do nowej p[i] = T[i]; delete [] T; // Usuwamy starą tablicę T = p; // Nowa tablica staje się tablicą T } } // Zmniejsza o DT rozmiar tablict T //--------------------------------- template <class X> void Vector<X>::shrink() { if(c == n - DT - DT) { X * p; int i; n -= DT; // Zmniejszamy rozmiar o DT p = new X [n]; // Tworzymy nową tablicę o zmniejszonym rozmiarze for(i = 0; i < c; i++) // Starą tablicę przenosimy do nowej p[i] = T[i]; delete [] T; // Usuwamy starą tablicę T = p; // Nowa tablica staje się tablicą T } } // Dodaje element na koniec tablicy //--------------------------------- template <class X> void Vector<X>::push_back(X x) { enlarge(); // W razie potrzeby zwiększamy rozmiar T T[c++] = x; // x umieszczamy w tablicy } // Dodaje element na początek tablicy //----------------------------------- template <class X> void Vector<X>::push_front(X x) { enlarge(); // W razie potrzeby zwiększamy rozmiar T for(int i = c; i > 0; i--) T[i] = T[i-1]; // Przesuwamy elementy T[0] = x; // W zwolnione miejsce wstawiamy x c++; // Tablica zawiera więcej elementów } // Usuwa z tablicy T ostatni element //---------------------------------- template <class X> void Vector<X>::pop_back() { if(c) // Jeśli w tablicy T są jakieś elementy { c--; // Usuwamy ostatni shrink(); // W razie potrzeby zmniejszamy rozmiar T } } // Usuwa z tablicy T pierwszy element //----------------------------------- template <class X> void Vector<X>::pop_front() { if(c) // Jeśli w tablicy T są jakieś elementy { c--; // Usuwamy pierwszy for(int i = 0; i < c; i++) T[i] = T[i + 1]; shrink(); // W razie potrzeby zmniejszamy rozmiar T } } // Usuwa i-ty element tablicy T //----------------------------- template <class X> void Vector<X>::erase(int i) { if(c && (i < c)) { c--; // Zmniejszamy rozmiar T for(int j = i; j < c; j++) T[j] = T[j + 1]; shrink(); } } // Wstawia x na pozycję i-tą //-------------------------- template <class X> void Vector<X>::insert(int i, X x) { if(i < c) { enlarge(); for(int j = c; j > i; j--) T[j] = T[j - 1]; T[i] = x; c++; } } // Wyświetla zawartość tablicy T //------------------------------ template <class X> void Vector<X>::print() { for(int i = 0; i < c; i++) cout << "T[" << i << "] = " << T[i] << endl; cout << endl; } // ********************** // *** PROGRAM GŁÓWNY *** // ********************** int main() { Vector<double> a; // Tworzymy klasę z elementami double for(int i = 0; i < 5; i++) a.push_back(i+1.5); // Wstawiamy 5 elementów a.print(); // Wyświetlamy tablicę a.push_back(10.3); // Na koniec wstawiamy 10 a.push_front(20.7); // Na początek wstawiamy 20 a.print(); a.pop_back(); // Usuwamy ostatni element a.pop_front(); // Usuwamy pierwszy element a.insert(3,100.8); // Na pozycję 3 wstawiamy 3 liczby a.insert(3,200.6); a.insert(3,300.4); a.print(); a.erase(4); // Usuwamy elementy 4 i 1 a.erase(1); a.print(); a.front() = a.back(); a.at(1) = a[a.size()-2]; a.print(); system("pause"); return 0; } |
Porównajmy teraz klasę zwykłą z klasą szablonową. Najpierw definicje klas:
Klasa zwykła | Klasa szablonowa | |||
|
|
W klasie szablonowej mamy słowo kluczowe template oraz definicję typu ogólnego, który u nas nazwaliśmy sobie X. Następnie wszędzie tam, gdzie w naszej klasie był typ elementów tablicy, wstawiliśmy zamiast niego nazwę typu ogólnego X. Gdy program będzie kompilowany, kompilator automatycznie zastąpi ten typ X przez typ podany w definicji zmiennej obiektowej. W ten sposób z klasy szablonowej o typie X powstanie klasa o typie konkretnym. Zatem szablon jest jakby makrodefinicją, która później jest rozwijana w klasę o pożądanym typie danych.
Dalsze różnice dotyczą definicji metod. Weźmy dla porównania metodę insert() obu klas:
Zwykła metoda | Metoda szablonowa | |||
|
|
Znów widzimy przed metodą szablonową słowo kluczowe template oraz definicję typu ogólnego X. Kolejna zmiana występuje w nazwie klasy. Zwróć uwagę, że teraz klasa nazywa się Vector<X>. Ma to sens, ponieważ w programie szablon ten zostanie przekształcony na metodę klasy dla konkretnego typu X (int, double, itp.). Dalej, wszystkie dane dla tablicy T mają w szablonie typ X. Uwagi te odnoszą się do wszystkich metod klasy szablonowej.
Na koniec program główny:
Klasa zwykła | Klasa szablonowa | |||
|
|
Jak widać, podstawowa różnica występuje tylko na początku, gdy tworzymy zmienną klasy. Przy klasie szablonowej musimy dodatkowo określić typ danych, które będzie przechowywała tablica dynamiczna. Typ wpisujemy w nawiasy trójkątne za nazwą klasy. Od tego momentu możemy operować w tej klasie na danych typu double. Jeśli wpiszemy inny typ, to kompilator stworzy klasę przechowującą dane tego typu. W ten sposób w programie możesz z klasy szablonowej tworzyć dowolną liczbę klas konkretnych.
I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe