2.7 Złożone typy danych

Tablice

Zanim poznamy tablice, poznajmy ogólne zasady operowania zbiornikami w C++. Co to jest takiego zbiornik? Jest to po prostu taki obiekt, który może w sobie zawierać inne obiekty. Oczywiście jeśli chodzi o elementy wbudowane w C++ to mamy do dyspozycji tylko tablice, wiec nie ma się rozdrabniać, ale za jakiś czas poznamy i inne zbiorniki (oczywiście zdefiniowane bibliotecznie), zatem warto poznać te ogólne reguły.

Tablice deklaruje się w następujący sposób:


<typ> <nazwa zmiennej>[<wielkość tablicy>];


Jeżeli chodzi o inne szczegóły deklaracji, zostanie to omówione później (w podrozdziale "Deklaratory").

Zasady posługiwania się zbiornikami w C++ (ogólne!) są następujące: każdy zbiornik zawiera jakieś elementy (może być również pusty, choć akurat puste tablice nie są dozwolone przez standard). Z kolei do każdego dowolnego elementu możemy się dobrać poprzez specjalną wartość, zwaną ITERATOREM. Wartość ta pozwala nam na poruszanie się po zbiorniku. Jeśli mamy zbiornik, to możemy pobrać odpowiednie wartości iteratorów stanowiące początek i koniec zbiornika. W każdym razie, załóżmy że pobraliśmy iterator, który stanowi początek zbiornika. Wyłuskanie takiego iteratora daje referencje do pierwszego elementu zbiornika. Jak się oczywiście można domyślać, iterator to (w tym przypadku) po prostu wskaźnik.

Tzn. nie należy dokładnie tak o nim myśleć. Własności iteratora i wskaźnika trochę się od siebie różnią. Iterator służy do iteracji, tzn. "jechania po zbiorniku". Na iteratorze można zawsze wykonać operację pobrania NASTĘPNEGO (kategoria "iterator postępowy"), na niektórych innych również POPRZEDNIEGO (kategoria "iterator odwracalny"), na innych operację AWANSU iteratora (kategoria już tylko "iterator swobodnego dostępu"), tzn. przesunięcia się w zbiorniku o kilka elementów do przodu lub do tyłu. Kategoria "iterator swobodnego dostępu" łączy w sobie wszystkie te kategorie i tej właśnie kategorii jest wskaźnik (potraktowany jako iterator do surowej tablicy).

W C++ istnieją różne rodzaje zbiorników o różnych właściwościach, ale ten jedyny z nich wbudowany, czyli "surowa" tablica jest to "zbiornik swobodnego dostępu". Zbiornik taki wyróżnia się tym, że można go indeksować pewną wartością i w ten sposób uzyskiwać dostęp do elementu o określonym numerze w kolejności. Iteratorem takiego zbiornika (którym jest wskaźnik) jest również iterator swobodnego dostępu. Iterator taki, poza tym, że pozwala uzyskać iterator NASTĘPNY i POPRZEDNI, to można również taki iterator AWANSOWAĆ, tzn. przesunąć go o kilka elementów do przodu lub do tylu. Ludzie nie lubiący C++ – ewentualnie też inni mający długi kontakt z C, np. Bjarne Stroustrup (: – nazywają to "arytmetyką wskaźników", gdyż owe operacje wykonuje się na iteratorach za pomocą operatorów odpowiednio "++", "--" oraz "+". Istnieje także operacja DYSTANSU. Dystans liczy się miedzy dwoma iteratorami (i jak się można domyślać wykonuje się to operatorem "–") i jest to wartość, o którą należy awansować ten drugi iterator (w operacji dystansowania), żeby otrzymać pierwszy (inaczej mówiąc, jest to odległość między elementami).

Ta tzw. "arytmetyka wskaźników" jest czymś, za co C++ od różnych purystów językowych (jak również np. wielbicieli Javy) zbiera "bencki". Właściwie to należą się one językowi C, ale w języku C jest to dla nich jakoś "normalne". Zastrzeżenia do tej "arytmetyki wskaźników" są jak najbardziej słuszne, jeśli traktujemy to rzeczywiście jako arytmetykę wskaźników. Bo też tak w C++ – niestety! – się da. Jeśli mamy wskaźnik, to zawsze wolno nam użyć operatorów ++, --, + i -, nawet jeśli dany wskaźnik nie jest iteratorem do żadnej tablicy. Oczywiście tak robić absolutnie nie należy (podobnie jak "nie należy" używać obleśnego rzutowania). Ale wolno. Jest to – niestety! – nawet dość często wykorzystywane wespół z rzutowaniem, np.

 int* x = *++(int*)v; 

co bezpieczniej jest zrobić (zakładając, że v jest unsigned char*) przez:

int* x = reinterpret_cast<int*>( v );
v += sizeof *x;

W C++ są zresztą lepsze metody na zorganizowanie "arbitralności" argumentów, a na takiej konstrukcji można tylko dostarczyć mnóstwo potencjalnych bugów. Zapamiętajmy zatem, że nie ma czegoś takiego jak "arytmetyka wskaźników", a operatory ++ -- + i - służą tylko i wyłącznie do wykonywania operacji następnego, poprzedniego, awansu i dystansu na ITERATORACH. A nie na wskaźnikach jako-takich.

Przedstawiam zatem ów sposób operowania tablicami:


int main()
{
	int tab[20]; // deklaracja tablicy o elementach typu int rozmiaru 20
	int* x = tab; // pobranie do iteratora 'x' początku tablicy
	while ( x != tab + 20 ) // porównanie bieżącego iteratora z końcem tablicy
		*x = 1; // wyłuskanie
	
	for ( int i = 0; i < 20; ++i ) // od 0 do wielkości tablicy
		tab[i] = 2; // indeksowanie
}


To, co pokazałem to wszystkie operacje, które można wykonać na tablicy. Uważni na pewno zwrócili uwagę, że tablica jest indeksowana od zera do wartości o jeden mniejszej, niż jej długość. Podaliśmy w deklaracji "20", a tymczasem tablica jest indeksowana od 0 do 19. Wszystko to nawet wydaje się słuszne (i jest), ale jakie ogólnie mają znaczenie owe wartości "20" i "tab+20"? Jak widać oczywiście, tablica może być NIEJAWNIE KONWERTOWANA na iterator, który wskazuje jej początek. Może się to odbywać również podczas operacji awansu. Zatem "tab+20" to iterator wskazujący na początek tablicy, awansowany o wartość 20, czyli o wielkość tablicy. No dobrze, ale co w ten sposób uzyskujemy? Przecież tylko awansując go o wartość z przedziału od 0 do 19 uzyskujemy wskaźnik na konkretny element, a tab+20 wskazuje już gdzieś za tablicę!

Owszem, to wszystko prawda. Zauważ jednak, że dla takiej wartości nigdy nie następuje wyłuskanie. Podobnie z pętlą for: tam nigdy nie następuje indeksowanie wartościami spoza poprawnego zakresu. Są to właśnie żelazne reguły zbiorników i iteratorów w C++: wielkość tablicy (czyli ilość elementów zbiornika) jest pierwsza wartością, którą nie można tego zbiornika indeksować. Zaś wartość iteratora początku tablicy awansowana o tą wielkość jest to tzw. "wartość za-końcowa". Tzn. taka, która jest pierwszym iteratorem, którego już nie można interpretować jako wskaźnik, gdyż nie jest ona wyłuskiwalna (tzn. próba jej wyłuskania jest operacją niepoprawną). Jednak nie jest to wartość bez znaczenia. Jej interpretacja logiczna brzmi: wartość iteratora, z którą porównanie się powiodło oznacza, że iterator sterujący doszedł do końca zbiornika, oraz taka, której pobranie POPRZEDNIEGO iteratora da iterator wskazujący na ostatni element zbiornika (oczywiście ma znaczenie tylko dla iteratorów, od których można wziąć poprzedni, czyli tutaj jak najbardziej).

Tu tak przy okazji (na "marginesie") wspomnę, że swego czasu na pl.comp.lang.c odbyła się długa dyskusja pomiędzy najbardziej zasłużonymi dla owej grupy ludźmi, czyli mną i Qrczakiem (właśnie stąd to zasłużenie :))) na wiele tematów, m.in. takiego właśnie zgłoszonego swego czasu defektu w C++: Wedle standardu, dwa wskaźniki porównane ze sobą są równe gdy: wskazują na ten sam obiekt, wskazują na za-koniec tej samej tablicy lub oba są null. Ktoś widocznie pomyślał, że w pozostałych przypadkach nie są one równe i wpadł na pomysł porównania wskaźnika na początek jednej tablicy i wskaźnika na za-koniec drugiej (uważni na pewno dostrzegą, że w pewnych okolicznościach one mogą być sobie równe, w szczególności gdy kompilator rozmieści te obiekty jeden za drugim). Że operacja takiego porównania w C++ nie ma żadnej interpretacji logicznej, bo z za-końcem należy porównywać tylko iterator należący do tej tablicy, jakoś autorowi umknęło. Co smutniejsze, komitet standaryzacyjny autorowi przyklasnął i prawdopodobnie już wkrótce do standardu zostanie wniesiony wpis, że owszem, takie dwa wskaźniki mogą być sobie równe, jeśli wskazują na ten sam ADRES. Pozostawienie jednak tego wyniku jako nieokreślony było lepsze, gdyż lepiej nieco wskazuje, jak należy traktować wyniki operacji o nieistniejącej interpretacji logicznej. Co się dalej z tym stanie, nie wiem, aczkolwiek jeśli taka poprawka wejdzie do standardu, będzie to cofnięcie w rozwoju dla C++ – od dłuższego czasu język ten stara się skupić przede wszystkim na programowaniu w sposób logiczny, z wyraźnym oddzieleniem interfejsu (tu: iteratory) od implementacji (wskaźniki i adresy w pamięci), zwłaszcza że adresy są implementacją iteratorów tylko tych do surowych tablic, a nie są to jedyne iteratory w C++. Jest jednak nadzieja, że nic z tego nie wyjdzie, gdyż cały opis defektu bazuje na chybionym założeniu - definicji, którą autor uznał za definicję wyniku porównania wskaźników. Niestety wynik porównania wskaźników jest akurat dokładnie określony i uważny czytelnik na pewno ją zna. W ramach małego "hintu" jedynie napomknę, że wskaźnik też jest typem "POD"... Natomiast powyższa definicja określa jedynie jak należy interpretować fakt, że dwa wskaźniki są sobie równe lub nie - ale oczywiście w tym celu należy najpierw wykonać operację, która posiada interpretację logiczną :).

Typ elementów tablicy oczywiście może być dowolny. Może być nim również inny typ tablicowy, np.:


        int mac[20][20];


W ten właśnie sposób tworzy się tablice dwuwymiarowe. Jak widać zresztą, drugi wymiar nie jest górną granica wymiarów.

Tablice możemy inicjalizować odpowiednim wyrażeniem ("w stylu C"). Np.


        int tab[3] = { 0, 3, 1 };


Proszę jednak pamiętać, że jest to inicjalizacja, a nie przypisanie, można więc podać to podczas deklaracji, ale nie jako instrukcję w programie. Tak przy okazji – referencje tutaj też maja znaczenie i możemy je tworzyć. Do takiej tablicy np.:


int (&rtab)[3] = tab;


I oczywiście, jak każda referencja, musi być ona zainicjalizowana inną referencją. Podeprzyjmy się może jeszcze jednym przykładem:


#include <iostream>

using namespace std;

int main()
{
        int tab[] = { 4, 3, 2, 1 }; // rozmiar tablicy dobrany automatycznie

        cout << "tab[1] = " << tab[1]
                << "\ntab[3] = " << tab[3] << endl;
}


Wspomniałem na początku przy omawianiu typu string, że jest to typ biblioteczny i w C go nie było. Tam bowiem napisy realizuje się jako tablicę o elementach typu char. Tablicę taką możemy inicjalizować stałą napisową:


        char napis [20] = "Tolek"; // równoważne { 'T','o','l','e','k','\0' }


Zwróć uwagę na ostatni znak w tablicy! Jest to istota tzw. C stringów, zwanych też inaczej "null-terminated strings". Cała kwestia polega na tym, że używa się specjalnej wartości znaku, która jest wartością "kończącą napis". Ta implementacja bezwzględnie króluje w C i C++; wielu ludzi narzeka na tą implementację twierdząc, że jest bardzo errorogenna (i po części mają rację). Jednakże w C++ klasa string zapewnia nam większe bezpieczeństwo (np. nie da się wstawić znaku na którejś pozycji w środku napisu i w ten sposób "uciąć" string - bedzie on takim samym znakiem, jak każdy inny).

Do takiej tablicy musimy wpisywać inne napisy literka po literce (używa się do tego odpowiednich funkcji, o czym będzie mowa dalej, przy omawianiu biblioteki standardowej C). Możemy też nie deklarować rozmiaru tablicy i wtedy kompilator dobierze go sam, jak pokazano w przykładzie:


        char napis [ ] = "Tolek";


Zauważ, że długość powyższej tablicy nie jest 5, lecz 6. Podobnie należy bezwzględnie pamiętać, że minimalna wielkość tablicy, w której chcemy przechowywać napis to długość tego napisu powiększona o 1!

C++ bezwzględnie wymaga znaku `\0' terminującego napis, w związku z czym nie zaakceptuje deklaracji tablicy z wartością początkową, która będzie "za długim" napisem w stosunku do podanej wielkości tablicy. Jest to nowość w stosunku do C, który C takich wymagań nie stawiał. Dopuściłby w powyższym przykładzie napisanie: char napis[5] = "Tolek"; co w C++ byłoby błędne (i odrzucone przez kompilator).

Nie udało mi się dotychczas wspomnieć o tym, jaki typ ma literał napisowy, ale nie przedstawiłem wówczas dostatecznych informacji. Dlatego teraz wyjaśniam: literał napisowy jest typu tablicy znaków o rozmiarze takim jak ilość zawartych między cudzysłowami znaków (proszę pamiętać o interpretacji znaków zaczynających się `\'!) + 1 (na bajt zerowy). Zatem stała "Tolek" jest typu char [6].

Jeżeli jednak w programie używamy napisów, które nie będą zmieniane, tzn. nie będziemy zmieniać żadnego z elementów tablicy znaków, wówczas możemy zamiast tablicą posłużyć się jedynie wskaźnikiem na taką tablicę (kompilator sam ją utworzy w pamięci i będzie obsługiwał jako obiekt globalny, a my mamy tylko adres jej początku):


const char* tolek = "Tolek dzisiaj zapił i nie zjawi się na zajęciach";


Jak widzieliśmy wcześniej, napis nie musi zapełniać całej tablicy. Nie zapominajmy, że to są tablice C, całkiem surowe, że się tak wyrażę, nie można ich więc rozciągać (właśnie dlatego istnieją takie typy jak string, czy vector). Jest ona zadeklarowana raz i taka, jak zadeklarowana musi trwać do końca swojego istnienia. Mało tego: jej wielkość musi być wartością stałą! Co prawda g++ ma takie małe niestandardowe rozszerzenie... ale jeśli już chcemy deklarować tablice o nieznanej wielkości (czy zależnej od jakichś wartości), to lepiej się jednak trzymać standardów (omówię to dalej). W związku z tym, wielkość tablicy char jest wielkością w pewnym sensie zapasową. Biblioteka standardowa C posiada odpowiednie funkcje do obsługi tablic napisowych (opisane w 7.h.).

Struktury i unie

Struktura jest to typ podobny do tablicy, gdyż może się składać z kilku elementów, ale każdy z nich może być dowolnego typu. Elementy te nazywamy POLAMI. Deklaracja struktury ma następującą postać:


struct <nazwa>
{
	<typ1> <pole1>;
	<typ2> <pole2>;
	<typ3> <pole3>;
	<...>
} <deklaracja_zmiennej>;


Deklaracja pól przypomina deklaracje zmiennych (mogą być też podobnie łączone w listy deklaracyjne), nie mogą być jednak inicjalizowane. Element <deklaracja_zmiennej> jest nieobowiązkowy i umożliwia zadeklarowanie zmiennej typu tej struktury w bieżącym zasięgu. Taka deklaracja tworzy typ o nazwie `<nazwa>'. Element <deklaracja_zmiennej> jest opcjonalny. Jeśli występuje w deklaracji, to element <nazwa> jest również nieobowiązkowy (aczkolwiek typ jako taki nie jest wówczas dostępny).

UWAGA: W języku C typ taki nosił nazwę `struct <nazwa>'. Często więc można tam spotkać takie konstrukcje:


        typedef struct klocek_tag
        {
                int jeden;
                int dwa;
        } KLOCEK;


albo:


typedef struct klocek_tag KLOCEK;
...
struct klocek_tag
{
        int jeden;
        int dwa;
};


i wtedy takim sprytnym hackerskim obejściem programiści pozbywali się konieczności umieszczania słowa `struct' przed nazwą typu (nie wiem dlaczego, ale również dość powszechne było nazywanie tych typów dużymi literami; domniemam, że pierwotnie takie rzeczy obchodziło się przez #define). W C++ już takiej konieczności nie ma, choć można nadal używać słowa kluczowego struct przed nazwą typu (zasada ta dotyczy nie tylko słowa struct, ale również union, enum i class, o których później). Ta właściwość spowodowała lekką niekompatybilność z C, bowiem deklaracja typu strukturalnego w C++ już zajmuje identyfikator, a w C jest on nadal wolny. W C++ oczywiście można ten identyfikator przesłonić nazwą zmiennej, funkcji itd., dla wstecznej zgodności (dzieje sie tak np. z funkcją stat, która jako argument dostaje wskaźnik do struktury o takiej samej nazwie). Jednak bywają przypadki kiedy nadmierne wykorzystywanie w C tej właściwości, że deklaracja struktury NIE zajmuje identyfikatora, powoduje niewypowiedziane wręcz zamieszanie przy próbie adoptowania tego w C++.

Do pól odwołujemy się za pomocą kropki: <zmienna>.<pole>, np. z powyższej deklaracji można uzyskać:


        Klocek k;
        k.jeden = 1;
        k.dwa = 2;


Kropka oczywiście nie jest też takim sobie znaczkiem, lecz jest jednym z operatorów. Po lewej stronie owego operatora musi stać referencja do obiektu typu strukturalnego, a po prawej nazwa pola (to drugie jest już elementem typowo składniowym, ale to pierwsze nie – wymaga się tutaj WYRAŻENIA odpowiedniego typu). Istnieje również operator -> (kreska i znak większości), który oznacza to samo, tylko że po jego lewej stronie musi być wartość wskaźnikowa (czyli (*w).pole jest tym samym, co w->pole). Takie wyrażenie zwraca z kolei referencje do pola, a typ tego wyrażenia jest taki, jak w deklaracji pola (plus referencja oczywiście). No dobrze, ale co z wariancją?

No cóż, nie jest to wszystko takie proste. Oczywiście wiadomo, że te deklaracje są prywatną sprawą struktury i użytkownik może z zewnątrz zrobić wszystko w taki sposób, w jaki mu na to pozwoli referencja do struktury. Jeśli przy deklaracjach tych zmiennych nie podano modyfikatora wariancji (standard C++ nazywa to, jak wiemy, cv-qualification i deklaracja, w której nie użyto modyfikatora wariancji tworzy referencje, która jest cv-unqualified), to podczas dostępu z zewnątrz, jako pole, posiada ono taką wariancję, jak obiekt typu strukturalnego, w którym zawarto ową deklarację. Jeśli jednak jakiś modyfikator posiada, to niestety efektywna wariancja takiego pola będzie inna. Wygląda to dokładnie w ten sposób:

Znaczenie modyfikatora static objaśnię przy omawianiu właściwości dodatkowych, na razie nie będzie nam to potrzebne. Struktury możemy inicjalizować również tak, jak tablice, np.:


Klocek k = { 1, 2 };


Zwracam jednak uwagę, że jest to przestarzały sposób inicjalizowania struktury. Jest on dozwolony tylko pod warunkiem, że w strukturze nie umieścimy żadnej właściwości C++, w takim bowiem przypadku należy zdefiniować dla struktury konstruktor (patrz dalej). Do takich właściwości należy również np. umieszczenie statycznego pola.

Unia jest typem podobnym do struktury, z tym tylko, że wszystkie pola mają to samo (zerowe) przesunięcie względem początku struktury (czyli efektywnie wszystkie pola unii współdzielą swoją wewnętrzną reprezentację). Przykładowa deklaracja unii:


        union Podzial
        {
                long l;
                char c[4];
        };


daje możliwość podglądania każdego bajtu zmiennej l, np.:


        Podzial h;
        h.l = -1;
        char c = h.c[1];


Zalecam umiar w używaniu unii. Większość zastosowań unii jest nieprzenośna, a często jest poprawna tylko w obrębie jednego komputera (jak niektórzy mogą zauważyć, jej użycie jest bliskie reinterpret_cast). Jedynym wyjątkiem jest implementacja zmiennych wariancyjnych w celu oszczędzenia miejsca (konkretnie nigdy nie następuje odczyt wartości spod innego pola, niż był w nim zapis). Kolejność bajtów w słowie (dwa bajty) i długim słowie (cztery bajty) jest różna na różnych komputerach i dlatego ten sam program może podać zupełnie odmienne wyniki na innych maszynach.

Dość ciekawą właściwością struktur jest możliwość tworzenia pól bitowych. Są to takie pola, na które przeznacza się odpowiednią ilość bitów, dzięki czemu można zaoszczędzić miejsce (ta sztuczka ma też parę innych, ciekawych zastosowań, niestety trudnych do wykorzystania i najczęściej poprawnych tylko w obrębie jednego komputera). Przykład podam razem z unią:


#include <iostream>

using namespace std;

union HexCiphers
{
        unsigned char b;
        struct
        {
                unsigned left:4;
                unsigned right:4;
        }c;
}h;

int main()
{
        h.b = 125;
        if ( h.c.left > 9 )
                cout.put( h.c.left + 'A' - 9 );
        else
                cout.put( h.c.left + '0' );

        if ( h.c.right > 9 )
                cout.put( h.c.right + 'A' - 9 );
        else
                cout.put( h.c.right + '0' );

        return 0;
}


Oczywiście dostęp do zmiennej `upakowanej' jest wolniejszy, niż normalnej, ale to już zależy od sposobu upakowania i samego procesora.

Niestety, powyższy program może okazać się bzdurny. Standard nikomu nie gwarantuje jakiejkolwiek kolejności układu pól w strukturze, a już na pewno niczego nie gwarantuje w przypadku pól bitowych. Nie jest więc powiedziane, że rzeczywiście bajty i bity tak zostaną ułożone (można co najwyżej dorabiać procedurę sprawdzającą, jak dokładnie kompilator co zrobił i żądać odpowiednich definicji dla kompilacji warunkowej). Od "endianu" zależy bowiem nie tylko kolejność bajtów w słowie, ale i kolejność bitów w bajcie (bitów przypisywanych polom bitowym). Endian to zresztą nie jedyny problem. Kompilatory często lubią dokonywać wyrównywania (ang. alignment) struktur, co powoduje, że rozmieszczenie pól w strukturach może różnić się nie tylko na maszynach, ale na różnych wersjach kompilatora, a nawet na tym samym kompilatorze w zależności od pewnych opcji. Wszelkie zastosowania unii inne, niż zmienne wariancyjne, są prawdę mówiąc poza konkursem i są już tylko pozostałością z zamierzchłych czasów C, kiedy był on wykorzystywany mniej więcej jako makro-asembler.

Jeszcze taka sprawa natury językowej: pola bitowe to nie są zmienne tych typów, na co opiewa deklaracja owych pól. Jest to zupełnie inny typ. Oczywiście jest też i referencja do tego pola bitowego, aczkolwiek użytkownik nie może jej tworzyć, ani nazwać owego typu. Może się ona niejawnie konwertować na WARTOŚĆ (NIE referencję!) do tego samego typu, co typ w deklaracji. Ale na tym się cały związek z tym typem kończy. Typ, jakiego jest pole bitowe, dysponuje własnym operatorem przypisania i dopuszcza po jego prawej stronie wartości zgodne (czyli tego samego typu lub konwertowalnego) z typem podanym w deklaracji pola.

Chciałbym jeszcze zwrócić uwagę na postać deklaracji struktury. Otóż, jak wspomniałem, dla struktury jest wymagana albo jej nazwa, albo nazwa tak utworzonej zmiennej. W unii z kolei nie wymaga się niczego. Na przykład następująca deklaracja jest prawidłowa:


struct
{
        int a;
        union {
                long l
                char c[4];
        };
} dzial;

Podobnie i ta:

union
{
        struct { char c1, c2; short s; } p;
        long l;
};


Pusta deklaracja union nie oznacza żadnego typu, a jedynie zastrzega, że zawarte wewnątrz niej pola dzielą pamięć.