Obiektowe programowanie w języku C++
Kurs podstawowy
Dr inż. Lucjan Miękina
upel.agh.edu.pl/wimir/login/
Katedra Robotyki i Mechatroniki
April 17, 2013
1/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
vector wskazników do obiektów
1 # include < iostream > 30 int main ( int argc , char * argv []) {
2 # include < vector > 31 vector < Complex *> v;
3 # include " ../ Complex / Complex .h" 32 Complex * c;
4 using namespace std ; 33 v. push_back ( new Complex ("1" ,1. ,1.));
5 void print ( vector < Complex * >& v) { 34 c = new Complex ("2" ,2. ,2.);
6 // declaration of a suitable iterator 35 v. push_back (c );
7 vector < Complex * >:: const_iterator it ; 36 v. push_back ( new Complex ("3" ,3. ,3.));
8 cout << endl << " vector contains " 37 print (v );
9 << v. size () << " elements :"; 38 erase (v , 1); // remove the 2 nd element
10 for ( it =v. begin (); it != v. end (); it ++) 39 print (v );
11 cout << endl << ** it ; 40 erase (v ); // remove all elements
12 } 41 print (v );
13 void erase ( vector < Complex * >& v , int i) 42 return 0;
14 { 43 }
15 vector < Complex * >:: iterator it ;
16 it =v. begin ()+ i; 1 1: 0 xd96010 , (1.0 , 1.0) created
17 if ( it != v. end ()) { 2 2: 0 xd96060 , (2.0 , 2.0) created
18 delete * it ; 3 3: 0 xd960b0 , (3.0 , 3.0) created
19 v. erase ( it ); 4 vector contains 3 elements :
20 } 5 Re =1 , Im =1
21 } 6 Re =2 , Im =2
22 void erase ( vector < Complex * >& v) { 7 Re =3 , Im =3
23 while (v. size ()) { 8 2: 0 xd96060 , (2.0 , 2.0) deleted
24 Complex * c = v. back (); 9 vector contains 2 elements :
25 if (c) 10 Re =1 , Im =1
26 delete c; 11 Re =3 , Im =3
27 v. pop_back (); 12 3: 0 xd960b0 , (3.0 , 3.0) deleted
28 } 13 1: 0 xd96010 , (1.0 , 1.0) deleted
29 } 14 vector contains 0 elements :
2/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
vector obiektów
1 # include < iostream > 30 erase (v , 1); // remove the 2 nd element
2 # include < vector > 31 print (v );
3 # include " ../ Complex / Complex .h" 32 v. clear (); // remove all elements
4 using namespace std ; 33 print (v );
5 void print ( vector < Complex >& v) { 34 return 0;
6 // declaration of a suitable iterator 35 }
7 vector < Complex >:: const_iterator it ;
8 cout << endl << " vector contains " 1 1: 0 x7fffa13c2d60 , (1.0 , 1.0) created
9 << v. size () << " elements :"; 2 1: 0 x1e8f010 , (1.0 , 1.0) created
10 for ( it =v. begin (); it != v. end (); it ++) 3 2: 0 x1e8f060 , (2.0 , 2.0) created
11 cout << endl << * it ; 4 1: 0 x1e8f040 , (1.0 , 1.0) created
12 } 5 1: 0 x1e8f010 , (1.0 , 1.0) deleted
13 void erase ( vector < Complex >& v , int i) 6 3: 0 x1e8f0d0 , (3.0 , 3.0) created
14 { 7 1: 0 x1e8f090 , (1.0 , 1.0) created
15 vector < Complex >:: iterator it ; 8 2: 0 x1e8f0b0 , (2.0 , 2.0) created
16 it =v. begin ()+ i; 9 1: 0 x1e8f040 , (1.0 , 1.0) deleted
17 if ( it != v. end ()) { 10 2: 0 x1e8f060 , (2.0 , 2.0) deleted
18 v. erase ( it ); 11 vector contains 3 elements :
19 } 12 Re =1 , Im =1
20 } 13 Re =2 , Im =2
21 int main ( int argc , char * argv []) { 14 Re =3 , Im =3
22 vector < Complex > v; 15 3: 0 x1e8f0d0 , (3.0 , 3.0) deleted
23 Complex c("1" ,1. ,1.); 16 vector contains 2 elements :
24 v. push_back (c ); 17 Re =1 , Im =1
25 c. Set ("2" , 2. , 2.); 18 Re =3 , Im =3
26 v. push_back (c ); 19 1: 0 x1e8f090 , (1.0 , 1.0) deleted
27 c. Set ("3" , 3. , 3.); 20 2: 0 x1e8f0b0 , (3.0 , 3.0) deleted
28 v. push_back (c ); 21 vector contains 0 elements :
29 print (v ); 22 3: 0 x7fffa13c2d60 , (3.0 , 3.0) deleted
3/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
vector jako przykład kompletnego standardowego pojemnika
Dalej dyskutowana jest klasa vector: typy wbudowane, iteratory, dostęp do elementów,
konstruktory, operacje naśladujące stos i listę. Klasa vector jest szablonem
zdefiniowanym w przestrzeni nazw std w pliku
.
Typy wbudowane w klasę vector
W pierwszej kolejności zdefiniowano zbiór standardowych nazw typów:
1 template < class T , class A = allocator >
2 class std :: vector {
3 public :
4 // types :
5 typedef T value_type ; // type of element
6 typedef A allocator_type ; // type of memory manager
7 typedef typename A :: size_type size_type ;
8 typedef typename A :: difference_type difference_type ;
9 typedef implementation_dependent1 iterator ; // T*
10 typedef implementation_dependent2 const_iterator ; // const T*
11 typedef std :: reverse_iterator < iterator > reverse_iterator ;
12 typedef std :: reverse_iterator < const_iterator > const_reverse_iterator ;
13 typedef typename A :: pointer pointer ; // pointer to element
14 typedef typename A :: const_pointer const_pointer ;
15 typedef typename A :: reference reference ; // reference to element
16 typedef typename A :: const_reference const_reference ;
17 // ...
18 };
Każdy standardowy pojemnik definiuje te nazwy typów w specyficzny, najbardziej
odpowiedni do implementacji sposób. Typ elementów pojemnika jest pierwszym
parametrem szablonu i ma nazwę value_type.
4/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Wbudowane nazwy typów pozwalają pisać kod wykorzystujący pojemniki bez
znajomości aktualnych typów elementów. W szczególności, można pisać kod
poprawnie współdziałający z każdym pojemnikiem. Na przykład, poniżej zdefiniowana
metoda sum może służyć do obliczania sumy elementów dowolnego pojemnika:
1 # include < iostream > 20 int main () {
2 # include < vector > 21 vector < int > vec ; // vector of ints
3 # include 22 // Insert an element 1 at the end
4 using namespace std ; 23 vec . push_back (1);
5 24 // Insert 2 other elements
6 template < class C > 25 vec . push_back (2);
7 typename C :: value_type sum ( const C& c) { 26 vec . push_back (3);
8 typename C :: value_type s = 0; 27 cout << endl << " sum of VECTOR : "
9 typename C :: const_iterator p; 28 << sum ( vec );
10 // start at the beginning 29 // LIST
11 p = c. begin (); 30 list < int > lst ; // list of ints
12 // continue until the end 31 lst . push_back (1);
13 while (p != c. end ()) { 32 lst . push_back (2);
14 s += *p; // get value of element 33 lst . push_back (3);
15 ++ p; // make p point to next element 34 cout << endl << " sum of LIST : "
16 } 35 << sum ( lst );
17 return s; 36 return 0;
18 } 37 }
1 sum of VECTOR : 6
2 sum of LIST : 6
5/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Iteratory klasy vector
Iteratory są używane do nawigacji między elementami pojemnika bez znajomości
typów przechowywanych w nim elementów. Klasy pojemników posiadają metody
pozwalające uzyskać dostęp do elementów na końcach sekwencji:
1 template < class T , class A = allocator >
2 class std :: vector {
3 public :
4 // iterators :
5 iterator begin (); // points to first element
6 const_iterator begin () const ;
7 iterator end (); // points to one - past - last element
8 const_iterator end () const ;
9 reverse_iterator rbegin (); // points to first element of reverse sequence
10 const_reverse_iterator rbegin () const ;
11 reverse_iterator rend (); // points to one - past - last element of reverse sequence
12 const_reverse_iterator rend () const ;
13 // ...
14 };
Para metod begin()/end() pozwala udostępnić ele-
menty pojemnika w naturalnej kolejności. Tzn., ele-
ment 0, element 1, element 2, itd.
Para metod rbegin()/rend() pozwala udostępnić el-
ementy pojemnika w odwrotnej kolejności. Tzn., el-
ement n-1, element n-2, element n-3, itd.
6/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Konstruktory klasy vector
vector posiada kompletny zestaw konstruktorów, destruktor, i operacji kopiowania:
1 template < class T , class A = allocator >
2 class std :: vector {
3 public :
4 // ...
5 // constructors , etc .:
6 explicit vector ( const A& = A ());
7 explicit vector ( size_type n , const T& val = T () , const A& = A ()); // n copies of val
8 template < class In > // In must be an input iterator
9 vector ( In first , In last , const A& = A ()); // copy from [ first : last )
10 vector ( const vector & x );
11 ~ vector () ;
12 vector & operator =( const vector & x );
13 template < class In > // In must be an input iterator
14 void assign ( In first , In last ); // copy from [ first : last )
15 void assign ( size_type n , const T& val ); // n copies of val
16 // ...
17 };
vector zapewnia szybki dostęp do wybranego elementu, ale zmiana ilości elementów
jest kosztowna. W konsekwencji, dobrze jest ustalić ilość elementów w trakcie
tworzenia wektora, na przykład:
1 vector < Record > vr (1024);
Każdy element wektora utwor-
2 void f( int n1 , int n2 ) {
zonego w ten sposób jest zainicjal-
3 vector < int > vi ( n1 );
izowany konstruktorem domyślnym
4 vector < double >* p = new vector < double >( n2 );
5 } dla typu elementu.
7/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Konstruktory klasy vector
Inicjalizacja oznacza że każdy z 1024 elementów wektora vr jest zainicjalizowany
wywołaniem Record(), a każdy z n1 elementów wektora vi jest zainicjalizowany
wywołaniem int (). UWAGA: domyślny konstruktor dla typów standardowych
wykonuje inicjalizację wartością 0 odpowiedniego typu.
Jeśli typ nie posiada domyślnego konstruktora, nie można utworzyć wektora złożonego
z elementów tego typu bez jawnego podania wartości elementów. Na przykład:
1 class Num { // infinite precision
2 public :
3 Num ( long );
4 // no default constructor
5 // ...
6 };
7 vector < Num > v1 (10000); // error : no default Num
8 vector < Num > v2 (1000 , Num (0)); // ok
Rozmiar obiektu typu vector może być ustalony domyślnie, na podstawie zbioru
elementów. Odbywa się to poprzez wywołanie konstruktora z argumentem
zawierającym sekwencję wartości, stanowiących elementy tworzonego wektora. Na
przykład:
1 void f( const list & lst ) {
2 vector v1 ( lst . begin () , lst . end ()); // copy elements from list
3 char p [] = " STL ";
4 vector < char > v2 (p , &p[ sizeof (p ) -1]); // copy characters from C - style string
5 }
W obu przypadkach, konstruktor klasy vector ustala rozmiar wektora w trakcie
kopiowania elementów z sekwencji wejściowej.
8/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Funkcja assign
Funkcje assign zapewniają alternatywę w stosunku do konstruktorów z wieloma
argumentami. Są one potrzebne, gdyż operator= ma jeden argument, więc assign()
jest używany w sytuacjach, gdy należy przekazać argument domyślny lub zakres
wartości. Na przykład:
1 class Book {
2 // ...
3 };
4 void f( vector < Num >& vn , vector < char r >& vc , vector < Book >& vb , list < Book >& lb ) {
5 vn . assign (1000 , Num (0)); // assign vector of 10 copies of Num (0) to vn
6 char s [] = " literal ";
7 vc . assign (s , &s[ sizeof (s ) -1]); // assign " literal " to vc
8 vb . assign ( lb . begin () ,lb . end ()); // assign list elements
9 // ...
10 }
Użycie assign () kompletnie zmienia elementy wektora. Wszystkie istniejące elementy
zostają usunięte i nowe są utworzone. Po wykonaniu funkcji, rozmiar wektora jest
równy ilości utworzonych elementów. Na przykład:
1 void f{
2 vector < char > v (20 , z ); // v. size ()==20 , each element has the value z
3 v. assign (10 , a ); // v. size ()==10 , each element has the value a
4 }
9/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Operacje naśladujące stos
Zwykle rozumiemy vector jako zwartą strukturę danych, która pozwala na
indeksowanie w celu dostępu do elementów, - jak w tablicach.
Można jednak traktować vector jako bardziej uniwersalny pojemnik. Biorąc pod uwagę
typowe przypadki użycia pojemnika, dostrzegamy użyteczność operacji naśladujących
działanie stosu:
1 template < class T , class A = allocator >
2 class std :: vector {
3 public :
4 // ...
5 // stack operations :
6 void push_back ( const T& x ); // add to end
7 void pop_back (); // remove last element
8 // ...
9 };
Funkcje te pozwalają uzyskać dostęp do pojemnika poprzez ostatni element (w celu
dołączenia lub usunięcia elementu). Na przykład:
1 void f( vector < char >& s) {
2 s. push_back ( a );
3 s. push_back ( b );
4 s. push_back ( c );
5 s. pop_back ();
6 if (s[s. size () -1] != b )
7 error (" impossible !") ;
8 s. pop_back ();
9 if (s[s. size () -1] != a )
10 error (" impossible !") ;
11 }
10/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Operacje naśladujące stos
Skąd potrzeba operacji naśladujących stos w klasie vector ?
Po pierwsze - by zaimplementować stos - często wykorzystywany mechanizm.
Po drugie - by móc stopniowo, w razie potrzeby, uzupełniać wektor danymi. Na
przykład, wczytując dane punktów z pewnego zródła, które udostępnia je w
przypadkowy sposób. Nie można wtedy utworzyć od razu całego wektora, trzeba
wprowadzać dane nowych punktów interaktywnie.
W takiej sytuacji można użyć kodu:
1 vector < Punkt > miasta ;
2
3 void add_points ( Punkt koniec ) {
4 Punkt buf ;
5 while ( cin >> buf ) {
6 if ( buf == koniec )
7 return ;
8 // wstaw nowy punkt
9 miasta . push_back ( buf ) ;
10 }
11 }
11/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Operacje naśladujące listę
Często trzeba dodać elementy w środku obiektu typu vector lub usunąć elementy z
dowolnej lokalizacji w obrębie obiektu typu vector:
1 template < class T , class A = allocator >
2 class std :: vector {
3 public :
4 // ...
5 // list operations :
6 iterator insert ( iterator pos , const T& x ); // add x before pos
7 void insert ( iterator pos , size_type n , const T& x );
8 template < class In > // In must be an input iterator
9 void insert ( iterator pos , In first , In last ); // insert elements from sequence
10 iterator erase ( iterator pos ); // remove element at pos
11 iterator erase ( iterator first , iterator last ); // erase sequence
12 void clear (); // erase all elements
13 // ...
14 };
1 int main ( int argc , char * argv []) {
2 vector < string > owoce ;
3 owoce . insert ( owoce . end () , " gruszka " );
4 owoce . insert ( owoce . end () , " porzeczka " );
5 vector < string > fruits ;
6 fruits . insert ( fruits . end () , " peach " );
7 fruits . insert ( fruits . end () , " orange " );
8 fruits . insert ( fruits . end () , " grape " );
9 sort ( fruits . begin () , fruits . end ());
10 fruits . insert ( fruits . end () , 2, " apple " );
11 fruits . insert ( fruits . end () , owoce . begin () , owoce . end ());
12 }
12/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Klasa list
list implementuje listę dwukierunkową doubly linked list. Znaczy to, że możliwe jest
przechodzenie do następnego lub poprzedniego elementu, wstawianie i usuwanie
elementów z dowolnej pozycji. Wymienione operacje mają złożoność O(1) - wykonują
się w stałym czasie.
Dodatkowo STL wspiera listy jednokierunkowe (za pomocą klasy slist), zapewniające
jedynie nawigację w przód. W takich sytuacjach slist jest bardziej efektywny niż list.
1 # include < string >
2 # include
3 # include < iostream >
4 using namespace std ;
5 void print ( list < string >& l) {
6 list < string >:: iterator it ;
7 cout << " list :";
8 for ( it =l. begin (); it != l. end (); it ++)
9 cout << " " << * it ;
10 cout << endl ;
11 }
12 int main ( int argc , char * argv []) {
13 list < string > lst ; // a list of strings
14 lst . insert ( lst . end () , " one " );
15 lst . insert ( lst . end () , " three " );
16 print ( lst ); 16 list : one three
17 list < string >:: iterator it = lst . begin (); 17
18 ++ it ; // it points now to number 2 18
19 it = lst . insert (it , " two " ); print ( lst ); 19 list : one two three
20 lst . insert (it , 3, " new " ); print ( lst ); 20 list : one new new new two three
21 lst . remove (" new " ); print ( lst ); 21 list : one two three
22 } 22 .
13/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Klasa stack
Klasa stack umożliwia wstawianie, usuwanie i inspekcję elementu znajdującego się na
szczycie stosu. stack jest strukturą typu last-in-first-out (LIFO): element na szczycie
jest tym, który został jako ostatni dołączony do pojemnika.
1 # include < stack >
2 # include < iostream >
3 using namespace std ;
4 void print ( stack < int >& s) {
5 cout << " top : " << s. top () << endl ;
6 }
7 int main ( int argc , char * argv []) {
8 stack < int > st ; // stack of ints
9 st . push (1); print ( st ); 9 top : 1
10 st . push (2); print ( st ); 10 top : 2
11 st . push (3); print ( st ); 11 top : 3
12 // Modify the top ( to become 4) 12
13 st . top ()=4; print ( st ); 13 top : 4
14 // Repeat until is empty 14
15 while (! st . empty ()) { 15
16 print ( st ); 16 top : 4
17 st . pop (); 17 top : 2
18 } 18 top : 1
19 } 19 .
14/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Klasa queue
Klasa queue implementuje pojemnik, specjalnie zaprojektowany do działania w trybie
FIFO (first-in first-out). Elementy są wstawiane przez koniec pojemnika (back) i mogą
być pobierane z jego początku (front).
1 # include < iostream >
2 # include < string >
3 # include < queue >
4 using namespace std ;
5
6 int main () {
7 queue < string > q;
8
9 q. push (" first " );
10 q. push (" second " );
11 q. push (" next " );
12 q. push (" last " );
13
14 cout << " front ( oldest ): " << q. front () << endl ; 14 front ( oldest ): first
15 cout << " back ( newest ): " << q. back () << endl ; 15 back ( newest ): last
16 q. pop (); // Remove the oldest element 16
17 cout << " front ( oldest ): " << q. front () << endl ; 17 front ( oldest ): second
18 cout << " back ( newest ): " << q. back () << endl ; 18 back ( newest ): last
19 q. push (" new " ); // Insert a new element 19
20 cout << " front ( oldest ): " << q. front () << endl ; 20 front ( oldest ): second
21 cout << " back ( newest ): " << q. back () << endl ; 21 back ( newest ): new
22 22
23 return 0; 23
24 } 24 .
15/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Klasa priority_queue
Klasa priority_queue implementuje pojemnik działający tak, że pierwszy dostępny
element jest zawsze największy ze wszystkich, zgodnie z wybranym warunkiem
uporządkowania.
1 # include < iostream >
2 # include < queue >
3 using namespace std ;
4
5 int main () {
6 priority_queue < int > q;
7
8 q. push (2);
9 q. push (0);
10 q. push (1);
11
12 cout << " top ( greatest ): " << q. top () << endl ; 12 top ( greatest ): 2
13 q. pop (); // Remove the greatest element 13
14 cout << " top ( greatest ): " << q. top () << endl ; 14 top ( greatest ): 1
15 q. push (1111); // Insert a new element 15
16 cout << " top ( greatest ): " << q. top () << endl ; 16 top ( greatest ): 1111
17 17
18 return 0; 18
19 } 19 .
16/1
Obiektowe programowanie w języku C++
Dynamiczne struktury danych
Klasa map
Klasa map jest sortowanym pojemnikiem asocjacyjnym, w którym klucz identyfikuje
dane (obiekty). Powiązania między kluczami i danymi są reprezentowane przez pary
typu pair .
map ma cechę
1 # include < iostream >
unikalności, tzn. że
2 # include < string >
3 # include