Dwa wymiary na dwa sposoby

2008-10-12 11:33

W 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:

  1. int** tab = new int* [width];
  2. for (int i = 0; i < width; ++i)    tab&#91;i] = new int [height];[/cpp]
  3. Gdyby można było zrobić to w jednym kroku przy pomocy instrukcji w rodzaju:
  4. &#91;cpp]int** tab = new int [width][height];[/cpp]
  5. 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.
  6.  
  7. 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:
  8. [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:

  1. int* tab = new int [width * height];
  2. tab[1 * width + 1] = 10;    // odp. tab[1][1] = 10
  3. 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 :)

Tags:
Author: Xion, posted under Programming »


2 comments for post “Dwa wymiary na dwa sposoby”.
  1. Kos:
    October 12th, 2008 o 13:34

    Btw, 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. :)

  2. 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)

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.