Dwa wymiary na dwa sposoby
2008-10-12 11:33W C++ dynamiczne tablice z więcej niż jednym wymiarem tworzy się zwykle w sposób dość złożony. Najpierw bowiem – w przypadku dwóch wymiarów – tworzymy tablicę wskaźników na jej wiersze, a następnie same wiersze:
- int** tab = new int* [width];
- for (int i = 0; i < width; ++i) tab[i] = new int [height];[/cpp]
- Gdyby można było zrobić to w jednym kroku przy pomocy instrukcji w rodzaju:
- [cpp]int** tab = new int [width][height];[/cpp]
- byłoby z pewnością nieco prościej. Nie jest to jednak możliwe i istnieje ku temu dobry powód. Rezultat takiej alokacji byłby bowiem inny niż pętli powyżej.
- W tym pierwszym przypadku zawartość tablicy jest bowiem umieszczona w kilku osobnych kawałkach pamięci, nie zaś w jednym dużym. Sprawia to jednak, że zwykły operator indeksowania <code>[]</code> daje się zastosować wobec wskaźnika na taką tablicę w dobrze znany sposób:
- [cpp]tab[1][1] = 10;
Skądinąd wiadomo bowiem, że zapis tab[i] jest tylko cukierkiem składniowym zastępującym *(tab + i). Dlatego też w wyniku pierwszej dereferencji (indeksowania) musimy otrzymać wskaźnik (na wiersz tablicy), aby ponowną operację przeprowadzić drugi raz i dostać się do pojedynczego elementu.
Kiedy zaś tablica 2D jest umieszczona w jednym kawałku pamięci, wtedy element tab[i][j] powinien zostać obliczony inaczej – np. jako *(tab + j * width + i), jeśli elementy są układane w pamięci wierszami. Kompilator musiałby więc skądś wiedzieć, jaka jest szerokość (width) tablicy, a ponadto nie rozpatrywać każdej pary nawiasów kwadratowych osobno, lecz traktować je jako łączną operację indeksowania. Zwłaszcza pierwszy wymóg nie wydaje się rozsądny.
Warto jednak – jeśli zależy nam efektywności – używać drugiego sposobu przechowywania tablic dwuwymiarowych:
- int* tab = new int [width * height];
- tab[1 * width + 1] = 10; // odp. tab[1][1] = 10
- delete[] tab;
Dostęp do elementów jest wtedy szybszy, bo oszczędzamy sobie jednej dereferencji wskaźnika (która może być kosztowna, jeśli tablica jest porozrzucana po pamięci). Szczegóły indeksowania można zaś opakować w zgrabną klasę z przeciążonymi operatorami.
Albo po prostu użyć gotowego rozwiązania, np. klasy multi_array z Boosta :)
-
Kos:
October 12th, 2008 o 13:34Btw, odnośnie pierwszego przykładu, można zrobić coś podobnego, lecz zaoszczędzić na alokacjach:
// pisane z pamięci, mogłem coś przekręcić :)
int** tab = new int* [width];
tab[0] = new int[width*height];for (int i = 1; i < width; ++i)
tab[i] = tab[i-1] + width;Mamy wtedy całą tablicę jako ciągły blok pamięci i możemy ją stosować tak, jak “zwykłą” dwuwymiarową tablicę.
Podaję to jako ciekawostkę, bo oczywiście drugie rozwiązanie, które opisałeś, jest efektywniejsze (mniej dereferencji, jak napisałeś), oraz po prostu wygodniejsze – zawsze milej mieć to opakowane w klasę, która za nas pilnuje pamięci. :)
-
Kos:
October 12th, 2008 o 13:35(no i faktycznie przekręciłem – zauważyłem 2 sekundy po wysłaniu posta, że niepotrzebnie mnożyłem przez sizeof :D)
// Pozwoliłem sobie to poprawić :) (Xion)
Recent posts
