Dziwny sposób przydzielania dwuwymiarowej tablicy?


110

W projekcie ktoś przesunął tę linię:

double (*e)[n+1] = malloc((n+1) * sizeof(*e));

Co rzekomo tworzy dwuwymiarową tablicę podwójnych liczb (n + 1) * (n + 1).

Podobno mówię, ponieważ do tej pory nikt, kogo zapytałem, nie mógł mi powiedzieć, co to dokładnie robi, skąd się wzięło ani dlaczego powinno działać (co podobno działa, ale jeszcze tego nie kupuję).

Być może brakuje mi czegoś oczywistego, ale byłbym wdzięczny, gdyby ktoś mógł mi wyjaśnić powyższą linijkę. Ponieważ osobiście czułbym się znacznie lepiej, gdybyśmy użyli czegoś, co naprawdę rozumiemy.


15
Nawet jeśli zadziała, zwolnij popychacza.
Martin James

22
@MartinJames Why? Jak inaczej przydzieliłbyś tablicę 2D w sąsiedniej pamięci? Zniekształcona tablica 1D? To jest programowanie z lat 90., teraz mamy VLA.
Lundin

43
Dla przypomnienia, jest to jedyny sposób na dynamiczne przydzielanie rzeczywistej tablicy 2D.
Quentin

15
@Kninnug Nie, to zadeklarowałoby tablicę wskaźników, a nie tablicę 2D. Jeśli chcesz mieć tablicę 2D, nie ma powodu, dla którego miałbyś kiedykolwiek chcieć przydzielić tablicę wskaźników. Jest powolny ze względu na fragmentację sterty i słabe wykorzystanie pamięci podręcznej i jest niebezpieczny, ponieważ nie można go używać jako tablicy (z memcpy itp.). Dodatkowo kod jest nadęty. Potrzebowałbyś wielu wywołań free () i łatwo byłoby spowodować wycieki pamięci. Chociaż taki kod może być szeroko rozpowszechniony, jest po prostu zły.
Lundin

15
Ten problem byłby jaśniejszy do wyjaśnienia / odpowiedzi, gdyby próbka nie używała tych samych wartościowanych wymiarów, n+1ale zamiast tegodouble (*e)[rows] = malloc(columns * sizeof *e);
chux - Przywróć Monikę

Odpowiedzi:


87

Zmienna ejest wskaźnikiem do tablicy n + 1elementów typu double.

Użycie operatora wyłuskiwania on edaje typ bazowy, ektórym jest „tablica n + 1elementów typu double”.

mallocPołączenia wystarczy wykonuje baza-typ e(jak opisano powyżej) i otrzymuje swój rozmiar, namnaża się przez to n + 1, że wielkość i przechodzącą w mallocfunkcji. Zasadniczo przydzielanie tablicy n + 1tablic n + 1elementów double.


3
@MartinJames sizeof(*e)jest odpowiednikiem sizeof(double [n + 1]). Pomnóż to przez, n + 1a dostaniesz wystarczająco.
Jakiś programista,

24
@MartinJames: Co w tym złego? To nie jest takie trudne, gwarantuje, że przydzielone wiersze są ciągłe i można je indeksować jak każdą inną tablicę 2D. Często używam tego idiomu we własnym kodzie.
John Bode

3
Może się to wydawać oczywiste, ale działa to tylko w przypadku tablic kwadratowych (te same wymiary).
Jens

18
@Jens: Tylko w tym sensie, że jeśli podasz n+1oba wymiary, wynik będzie kwadratowy. Jeśli to zrobisz double (*e)[cols] = malloc(rows * sizeof(*e));, wynik będzie miał dowolną określoną liczbę wierszy i kolumn.
user2357112 obsługuje Monikę

9
@ user2357112 Teraz wolałbym raczej zobaczyć. Nawet jeśli oznacza to, że musisz dodać int rows = n+1i int cols = n+1. Boże, chroń nas przed sprytnym kodem.
candied_orange

56

Jest to typowy sposób dynamicznego przydzielania tablic 2D.

  • ejest wskaźnikiem tablicy do tablicy typu double [n+1].
  • sizeof(*e)dlatego podaje typ typu wskazanego, czyli rozmiar jednej double [n+1]tablicy.
  • Przydzielasz miejsce na n+1takie tablice.
  • Ustawiasz wskaźnik tablicy tak, eaby wskazywał na pierwszą tablicę w tej tablicy tablic.
  • Pozwala to na użycie ejako e[i][j]dostępu do poszczególnych elementów w tablicy 2D.

Osobiście uważam, że ten styl jest znacznie łatwiejszy do odczytania:

double (*e)[n+1] = malloc( sizeof(double[n+1][n+1]) );

12
Dobra odpowiedź, ale nie zgadzam się z twoim sugerowanym stylem, preferując ptr = malloc(sizeof *ptr * count)styl.
chux - Przywróć Monikę

Dobra odpowiedź i podoba mi się twój preferowany styl. Nieznacznym ulepszeniem może być wskazanie, że musisz to zrobić w ten sposób, ponieważ między wierszami może występować wypełnienie, które należy wziąć pod uwagę. (Przynajmniej, myślę, że to jest powód, trzeba zrobić to w ten sposób). (Daj mi znać, jeśli się mylę.)
davidbak

2
@davidbak To to samo. Składnia tablic jest jedynie samodokumentującym się kodem: mówi „przydziel miejsce na tablicę 2D” z samym kodem źródłowym.
Lundin

1
@davidbak Uwaga: niewielka wada komentarza malloc(row*col*sizeof(double)) występuje, gdy row*col*sizeof()przepełnienia, ale tak się nie sizeof()*row*coldzieje. (np. row, col are int)
chux - Przywróć Monikę

7
@davidbak: sizeof *e * (n+1)łatwiejsze w utrzymaniu; Jeśli kiedykolwiek zdecydujesz się zmienić typ podstawowy (od doubledo long double, na przykład), a potem tylko trzeba zmienić deklarację e; nie musisz modyfikować sizeofwyrażenia w mallocwywołaniu (co oszczędza czas i chroni Cię przed zmianą w jednym miejscu, ale nie w drugim). sizeof *ezawsze poda odpowiedni rozmiar.
John Bode

39

Ten idiom naturalnie wypada z alokacji tablicy 1D. Zacznijmy od przydzielenia tablicy 1D dowolnego typu T:

T *p = malloc( sizeof *p * N );

Proste, prawda? Wyrażenie *p ma typ T, więc sizeof *pdaje taki sam wynik jak sizeof (T), więc mamy wystarczająco dużo miejsca alokacji dla N-elementowe tablicy T. Dotyczy to każdego typuT .

Teraz Tzastąpmy typem tablicowym, takim jak R [10]. Wtedy staje się nasz przydział

R (*p)[10] = malloc( sizeof *p * N);

Semantyka tutaj jest dokładnie taka sama, jak w przypadku metody alokacji 1D; zmienił się tylko typ p. Zamiast T *tego jest teraz R (*)[10]. Wyrażenie *pma typ, Tktóry jest typem R [10], więc sizeof *pjest równoważne temu, sizeof (T)które jest równoważne sizeof (R [10]). Więc przydzielamy wystarczającą ilość miejsca na tablicę Nby 10elementu R.

Jeśli chcemy, możemy pójść jeszcze dalej; przypuśćmy, że Rjest typem tablicowym int [5]. Zastąp to Ri otrzymamy

int (*p)[10][5] = malloc( sizeof *p * N);

Ta sama umowa - sizeof *pjest taka sama jak sizeof (int [10][5])i kończymy przydzielanie ciągłego kawałka pamięci wystarczająco dużej, aby pomieścić tablicę Nby 10by . 5int

Więc to jest strona alokacji; a co ze stroną dostępową?

Pamiętaj, że []operacja z indeksem dolnym jest zdefiniowana w kategoriach arytmetyki wskaźnika: a[i]jest zdefiniowana jako *(a + i)1 . W ten [] sposób operator indeksu niejawnie odwołuje się do wskaźnika. Jeśli pjest wskaźnikiem do T, możesz uzyskać dostęp do wskazanej wartości albo przez jawne wyłuskiwanie za pomocą *operatora jednoargumentowego :

T x = *p;

lub korzystając z []operatora indeksu:

T x = p[0]; // identical to *p

Tak więc, jeśli pwskazuje na pierwszy element tablicy , możesz uzyskać dostęp do dowolnego elementu tej tablicy, używając indeksu na wskaźniku p:

T arr[N];
T *p = arr; // expression arr "decays" from type T [N] to T *
...
T x = p[i]; // access the i'th element of arr through pointer p

Teraz powtórzmy naszą operację podstawienia i zastąpmy Ttypem tablicy R [10]:

R arr[N][10];
R (*p)[10] = arr; // expression arr "decays" from type R [N][10] to R (*)[10]
...
R x = (*p)[i];

Jedna natychmiast widoczna różnica; jawnie usuwamy odwołanie pprzed zastosowaniem operatora indeksu dolnego. Nie chcemy indeksować do p, chcemy indeksować do tego, co p wskazuje na (w tym przypadku tablicę arr[0] ). Ponieważ jednoargumentowy *ma niższy priorytet niż []operator indeksu dolnego , musimy użyć nawiasów, aby jawnie grupować pz *. Ale pamiętajcie z góry, że *pto to samo co p[0], więc możemy to zastąpić

R x = (p[0])[i];

Lub tylko

R x = p[0][i];

Tak więc, jeśli pwskazuje tablicę 2D, możemy indeksować do tej tablicy w następujący psposób:

R x = p[i][j]; // access the i'th element of arr through pointer p;
               // each arr[i] is a 10-element array of R

Biorąc to do tych samych wniosków, jak powyżej, zastępując Rw int [5]:

int arr[N][10][5];
int (*p)[10][5]; // expression arr "decays" from type int [N][5][10] to int (*)[10][5]
...
int x = p[i][j][k];

Działa to tak samo, jeśli pwskazuje na zwykłą tablicę lub jeśli wskazuje na przydzieloną pamięć malloc.

Ten idiom ma następujące zalety:

  1. To proste - tylko jeden wiersz kodu, w przeciwieństwie do fragmentarycznej metody alokacji
    T **arr = malloc( sizeof *arr * N );
    if ( arr )
    {
      for ( size_t i = 0; i < N; i++ )
      {
        arr[i] = malloc( sizeof *arr[i] * M );
      }
    }
  2. Wszystkie wiersze przydzielonej tablicy są * ciągłe *, co nie ma miejsca w przypadku powyższej metody alokacji fragmentarycznej;
  3. Zwolnienie tablicy jest równie łatwe za pomocą pojedynczego wywołania funkcji free. Ponownie, nie jest to prawdą w przypadku fragmentarycznej metody alokacji, w której trzeba cofnąć przydział każdego z nich, arr[i]zanim będzie można zwolnić arr.

Czasami preferowana jest metoda alokacji fragmentarycznej, na przykład gdy sterta jest mocno pofragmentowana i nie można przydzielić pamięci jako ciągłego fragmentu lub chcesz przydzielić tablicę „postrzępioną”, w której każdy wiersz może mieć inną długość. Ale ogólnie jest to lepsza droga.


1. Pamiętaj, że tablice nie są wskaźnikami - zamiast tego wyrażenia tablicowe są w razie potrzeby konwertowane na wyrażenia wskaźnikowe.


4
+1 Podoba mi się sposób, w jaki prezentujesz koncepcję: alokacja szeregu elementów jest możliwa dla dowolnego typu, nawet jeśli te elementy same są tablicami.
logo_writer

1
Twoje wyjaśnienie jest naprawdę dobre, ale zauważ, że alokacja ciągłej pamięci nie jest korzyścią, dopóki naprawdę jej nie potrzebujesz. Pamięć ciągła jest droższa od pamięci nieciągłej. W przypadku prostych tablic 2D nie ma różnicy w układzie pamięci (z wyjątkiem liczby wierszy do alokacji i zwalniania), więc preferuj używanie nieciągłej pamięci.
Oleg Lokshyn
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.