Programowanie w języku C/C++

Tablice i wskaźniki, skomplikowana składnia

Tablice i wskazniki, skomplikowana skladnia


Słowem wstępu


Jedną z pierwszych lekcji jakie dostaje początkujący programista języka C/C++ jest tworzenie tablic. Ćwiczenia te zazwyczaj ograniczają się do najprostszej wersji, jednowymiarowej. Przyzwyczaja się, że tablica ma swoją ustaloną długość, że należy pilnować rozmiaru. Później, w trakcie rozwiązywania bardziej skomplikowanych zadań, np. wymagających zmiany rozmiaru tablic, poznaje zagadnienia wskaźników, dowiaduje się o tablicach dynamicznych i odkrywa się przed nim nowy świat "bez ograniczeń". Wskaźniki i tablice N-wymiarowe fomatu "int****..." wydają się rozwiązywać wszystko - można dowolnie regulować każdą długość każdego wymiaru każdej podtablicy na każdym poziomie..

Jakkolwiek doskonale ćwiczy się i poznaje dzięki temu różne zawiłości związane z zarządzaniem (tworzeniem, reużyciem, usuwaniem) owych dynamicznych fragmentów, to prowadzi to z kolei do pewnej przesady w stronę dynamizmu. Wedle popularnej zasady "mam młotek, więc każdy problem wygląda jak gwóźdź", absolutnie wszystko jest płynne. Nawet jeśli dokładnie wiadomo, że na samym dnie tablicy będą zawsze bloczki po 5 elementów, to i tak ten poziom często widzimy traktowany jako zmienny i zostaje do niego zastosowany ten sam schemat do do pozostałych pięter.

Nie ma nic w tym złego, czasem jest to wręcz wskazane - ponieważ menedżer pamięci ma dużo mniej problemów z poukładaniem dużej ilości małych bloczków, niż kilku dużych. Wprowadza to jednak dwa efekty uboczne:
  • wraz z każdą alokacją nowego fragmentu, niezależnie od jego wielkości, bezwzględnie trzeba zapamiętać gdzieś wskaźnik na niego. Oznacza to, że w pełni dynamiczna tablica 100x1 zajmie o wiele więcej miejsca niż analogiczna w pełni dynamiczna tablica 1x100. Dodatkowo, obie mają szansę zająć dużo więcej miejsca niż analogiczne sztywne tablice 100x1 i 1x100, które to zajmą po równo pamięci, najmniej jak jest to możliwe przy 100 elementach
  • komplikuje się i mnoży ilość kodu potrzebną na utworzenie i zwolnienie każdego z poziomów tablicy
Oczywiście, każdy choćby średniozaawansowany programista C/C++ rozumie te problemy i na pewno nierzadko zastanawiał się czy lepiej użyć tablicy o sztywnych wymiarach czy raczej o płynnych. Na pewno również kiedyś wpadł na pomysł napisania hybrydy, na przykład sztywnej tablicy wskaźników:
 int *tab[10];
rzadziej - na stworzenie dynamicznej tablicy tablic sztywnych:
int (*tab)[10];
Celem wyjasnienia: pierwsza z jest 'płynna' na najniższym poziomie ('zerowym'), pozwala aby tablice na najniższym poziomie miały dowolną długość, druga - jest płynna na najwyższym poziomie (tutaj: pierwszym) podczas gdy poziom najniższy będzie zawsze 10-elementowy.

Pierwszy przykład wygląda intuicyjnie. Drugi - dużo mniej. Być może własnie dlatego wielu programistów zamiast niego wybierze młotek i stworzy tablicę w pełni dynamiczną:
int** tab;
i potem ręcznie będzie zajmować się pilnowaniem, żeby najniższy poziom zawsze byl 10-elementowy. Często wprowadza się typedef'y upraszczające zapis. Poniższy zapis jest równoważny z przykładem drugim:
typedef   int   tab_intow[10];
tab_intow  *tab;
A przecież to tylko dwa wymiary! Z łatwością można wyobrazić sobie operacje na tablicy np. pięciowymiarowej:
tab[1][1][2][3][1] = 80;
ale sama myśl o stworzeniu takiej tablicy w inny sposób jak "młotkiem" przeraża. Pośród wielu panuje pogląd, że bez serii typedef'ów nie da rady w ogóle zapisać skomplikowanej hybrydy tablic sztywnych i zmiennych.


Osiem sposobów na tablicę 2x4x3


Celem tego artykułu jest ukazanie, że jest to jednak możliwe. Aby nazbyt nie komplikować i nie mnożyć przypadków, wybrano za cel utworzenie tablicy 3D. Pozwala on w pełni pokazać, jak złożonymi i zarazem dopasowanymi do zagadnienia konstrukcjami mogą być tablice w C++. Poniżej przedstawiono wszystkie możliwe konfiguracje tablicy 3D, od dobrze znanej całkowicie sztywnej, przez wszystkie możliwe mało znane i przerażające hybrydy, aż w końcu powrót do dobrze znanej wersji w pełni dynamicznej. Poza deklaracjami typów zmiennych podano od razu przykłady jak poprawnie stworzyć całą strukturę tablicy oraz jak ją później usuwać. Na pierwszą myśl może to sie wydawać banalne, jednak jak pokażą przykłady, składnia operatora new() potrafi być o wiele trudniejsza od dekaracji samego typu. [ciekawostka: nad przedostatnim przykładem spędziłem prawie godzinę zanim zapisałem 'new' poprawnie]

Ostrzeżenie: niektóre zapisy mogą przyprawiać o ból głowy, zwłaszcza typy podawane podczas tworzenia fragmentów poprzez operator new(). W takim wypadku proponuje się ich pominięcie i powtórną próbę po ochłonięciu. Warto je mimo wszystko zrozumieć.

We wszystkich przykładach stosowano konwencję:
- duże litery zmiennych (typowo: A, B, C..) oznaczają rozmiar wymiar sztywnego
- małe litery zmiennych (typowo: x, y, z..) oznaczają rozmiar wymiar dynamicznego (zmiennego, płynnego)



[SSS] sztywna tablica sztywnych tablic sztywnych tablic


int const A=2,B=4,C=3;
 
//deklaracja zmiennej
int tabl[A][B][C]={0,};
 
//tworzenie
//-juz jest stworzone
 
//usuwanie
//-zostanie calkowicie usuniete przy opuszczeniu scope'a



[DSS] zmienna tablica sztywnych tablic sztywnych tablic


int const B=4,C=3;
int x=2;
 
//deklaracja
int (*tabl)[B][C];
 
//tworzenie
tabl = new int[x][B][C];
 
//usuwanie
delete[] tabl;



[SDS] sztywna tablica zmiennych tablic sztywnych tablic


int const A=2,C=3;
int y=4;
 
//deklaracja
int (*tabl[A])[C];
 
//tworzenie
for(int i=0;i<A;++i)
    tabl[i] = new int[y][C];
 
//usuwanie
for(int i=0;i<A;++i)
    delete[] tabl[i];



[SSD] sztywna tablica sztywnych tablic zmiennych tablic


int const A=2,B=4;
int z=3;
 
//deklaracja
int *tabl[A][B];
 
//tworzenie
for(int i=0;i<A;++i)
    for(int j=0;j<B;++j)
        tabl[i][j] = new int[z];
 
//usuwanie
for(int i=0;i<A;++i)
    for(int j=0;j<B;++j)
        delete[] tabl[i][j];



[SDD] sztywna tablica zmiennych tablic zmiennych tablic


int const A=2;
int y=4,z=3;
 
//deklaracja
int **tabl[A];
 
//tworzenie
for(int i=0;i<A;++i)
    tabl[i] = new int*[y];
for(int i=0;i<A;++i)        //petle nie sa zlaczone, aby unaocznic "poziomy" tablicy
    for(int j=0;j<y;++j)    //oraz to, co sie na danym poziomie dzieje
        tabl[i][j]=new int [z];
 
//usuwanie
for(int i=0;i<A;++i)
    for(int j=0;j<y;++j)
        delete[] tabl[i][j];
for(int i=0;i<A;++i)
    delete[] tabl[i];



[DSD] zmienna tablica sztywnych tablic zmiennych tablic


int const B=4;
int x=2,z=3;
 
//deklaracja
int *(*tabl)[B];
 
//tworzenie
tabl = new int*[x][B];
for(int i=0;i<x;++i)
    for(int j=0;j<B;++j)
        tabl[i][j]=new int[z];
 
//usuwanie
for(int i=0;i<x;++i)
    for(int j=0;j<B;++j)
        delete[] tabl[i][j];
delete[] tabl;



[DDS] zmienna tablica zmiennych tablic sztywnych tablic


int const C=3;
int x=2,y=4;
 
//deklaracja
int (**tabl)[C];
 
//tworzenie
tabl = new (int(*)[x])[C];
for(int i=0;i<x;++i)
    tabl[i] = new int[y][C];
 
//usuwanie
for(int i=0;i<x;++i)
    delete[] tabl[i];
delete[] tabl;



[DDD] zmienna tablica zmiennych tablic zmiennych tablic


int x=2,y=4,z=3;
 
//deklaracja
int (***tabl);
 
//tworzenie
tabl = new (int**)[x];
for(int i=0;i<x;++i)
    tabl[i] = new (int*)[y];
for(int i=0;i<x;++i)
    for(int j=0;j<y;++j)
        tabl[i][j] = new int[z];
 
//usuwanie
for(int i=0;i<x;++i)
    for(int j=0;j<y;++j)
        delete[] tabl[i][j];
for(int i=0;i<x;++i)
    delete[] tabl[i];
delete[] tabl;



Zamiast zakończenia - zadanie domowe


  • jak wyglądałaby składnia deklaracji zmiennej oraz alokowania najwyższego poziomu dla każdej z możliwych konstrukcji tablicy 4D?
  • jak wyglądałaby powyższe przykłady, jeśliby wymiary dynamiczne zastąpić użyciem vector<int>?


Przykłady zostały napisane i sprawdzone z użyciem kompilatora g++. W razie problemów, literówek czy innych usterek proszę o kontakt na: quetzalcoatl[na]poczta.fm lub gg: 2785435
Q.

6 komentarzy

quetzalcoatl 2010-09-03 18:11

Nie "można", a "należy". Tak właśnie jest i tak to "się czyta".

Karolkens 2010-08-27 14:16

Czyli można powiedzieć, że

int *tab[10];
jest 10-cio element-ową tablicą wskaźników, a
int (*tab)[10];
jest wskaźnikiem do 10-cio element-owej tablicy?

quetzalcoatl 2009-03-12 13:07

[email protected]: wyrzucilem 'flejmłora', o ktorego nie umieszczanie sam prosiles owczesniej..

winerfresh: mozna, jak najbardziej. napisalem jednak tak, zeby bylo wyraznie widac roznice pomiedzy przykladami, tzn. zeby bylo widac ktory 'blok' czynnosci doszedl - porownaj DSD z DDD
zwroc uwage, ze identyczna konwencje zastosowalem przy tworzeniu tych struktur -- przeciez ostatecznie te petle z new tez mozna by bylo 'posklejac'

winerfresh 2009-03-11 14:20

A tego:

for(int i=0;i<x;++i)
    for(int j=0;j<y;++j)
        delete[] tabl[i][j];
for(int i=0;i<x;++i)
    delete[] tabl[i];

Nie można zapisać tak:
for(int i=0;i<x;++i) {
    for(int j=0;j<y;++j)
        delete[] tabl[i][j];
    delete[] tabl[i];
}

??

quetzalcoatl 2008-10-05 22:49

punktzrzutu - racja! dzieki, juz poprawione. glupia literowka powielona kopiowaniem linii:)

punktzrzutu 2008-10-05 11:34

W dwóch ostatnich przykładach są błędy: for(int i=0;i<x;++x) - błędna pętla, powinno być: for(int i=0;i<x;++i)