Czy dwuwymiarowe tablice w C są potrzebne, aby wszystkie elementy były przyległe?

Question

Usłyszałem od znajomego, że dwuwymiarowe tablice w C są obsługiwane tylko syntaktycznie.

Powiedział, że lepiej użyć float arr[M * N] zamiast float[M][N], ponieważ kompilatory C, takie jak gcc, nie mogą zagwarantować, że na każdym systemie/platformie dane znajdują się w szeregu w pamięci.

Chcę użyć tego jako argumentu w mojej pracy magisterskiej, ale nie mam żadnego odniesienia.

Pierwsze pytanie:

Czy to prawda, co on mówi?

Drugie pytanie:

Wiesz, jeśli nie jest to książka lub artykuł, gdzie znaleźć to stwierdzenie?

dziękuję + Pozdrowienia

Answer 1

1. Nie, to nie tak.

2. Spójrz na standard C. Niektóre odpowiednie bity (pogrubienie kopalni nacisk):

   6.2.5 Rodzaje ¶20

   Tablica typu opisano ciągły przydzielony zestaw niepusty przedmiotów o szczególnym rodzaju obiektu element, zwany element typu.

   6.7.6.2 Array declarators ¶3 (nota 142)

   Kiedy kilka "tablica" Dane są przyległe, wielowymiarowa tablica jest zadeklarowana.

   6.5.2.1 Array indeksowanie ¶3

   Kolejne operatorzy indeksie dolnym wyznacza element wielowymiarowej tablicy obiektu. ... Wynika z tego, że tablice są przechowywane w wierszu-głównym zamówieniu (ostatni indeks zmienia się najszybciej).

   A może najbardziej wyraźnie, przykład w 6.5.2.1 Tablica indeksowanie ¶4:

   Przykład że obiekt macierzy zdefiniowany w zgłoszeniu

   int x[3][5];

   tutaj x jest 3 x 5 Tablica int s; dokładniej: x to tablica trzech obiektów elementarnych, z których każdy jest tablicą złożoną z pięciu następujących po sobie elementów: . W wyrażeniu x[i], które jest równoważne (*((x)+(i))), x jest najpierw konwertowane na wskaźnik początkowej macierzy o wartości wynoszącej , składającej się z pięciu następujących liczb: int s. Następnie i jest dostosowywany zgodnie z typem x, co pojęciowo pociąga za sobą pomnożenie i przez rozmiar obiektu, do którego wskazuje wskaźnik, a mianowicie tablica pięciu obiektów int. Wyniki są dodawane, a kierunek niezależny jest stosowany do , co daje tablicę pięciu następujących: int s. W przypadku użycia w wyrażeniu x[i][j], ta tablica jest z kolei konwertowana na wskaźnik do pierwszego z int, tak więc uzyskuje wartość int.

wielowymiarowe tablice w C są tylko "tablice tablic". Działają dobrze i są w 100% określone przez normę.

Pomocne może być również przeczytanie Section 6, Arrays and Pointers w FAQ na stronie comp.lang.c.

Answer 2

Sekcja 6.2.5.20 wymaga, aby tablice były alokowane w sposób ciągły. Dotyczy to zarówno tablicy tablic, jak i macierzy jednowymiarowej.

Twój przyjaciel jest po prostu błędny.

Answer 3

Sprawa jest nieco bardziej subtelny niż pozostałe odpowiedzi sprawiają, że brzmią:

Chociaż wielowymiarowe tablice są (semantycznie, prawdopodobnie nie fizycznie) przyległe, wskaźnik arytmetyka jest definiowana tylko jeśli pobyt w granicach tablica, której początkowo wskazywał twój wskaźnik (w rzeczywistości możesz przejść 1 element poza górną granicę, ale tylko wtedy, gdy nie masz dereferencji).

Oznacza to, że semantyka językowa zabrania przechodzenia przez wielowymiarową tablicę od początku do końca, a implementacja sprawdzania obwiedni języka C (która jest z zasady możliwa, ale rzadko widywana w środowisku naturalnym ze względu na wydajność) może podnieść segfault, wydrukuj diagnostykę lub spraw, by demony latały z twojego nosa za każdym razem, gdy przekroczysz granicę tablicy.

Nie jestem pewien, czy kompilatory wykorzystują te informacje do celów optymalizacji, ale w zasadzie mogą. Na przykład, jeśli masz

float *p = &arr[2][3]; 
float *q = &arr[5][9]; 

następnie p + x i q + y nigdy nie powinien alias, niezależnie od wartości x i y.

Answer 4

Wbudowane tablice wielowymiarowe w C są realizowane za pomocą translacji indeksu.Oznacza to, że na przykład tablica 3D T a[M][N][K] jest zaimplementowana jako tablica 1D T a_impl[M * N * K], z wielowymiarowym dostępem a[i][j][k], który jest niejawnie przetłumaczony na jednowymiarowy dostęp a_impl[((i * N) + j) * K + k]. Specyfikacja językowa nie opisuje tego wdrożenia w sposób jednoznaczny, jednak wymagania wymagają tego bezpośrednio.

Biorąc to pod uwagę, nie jest jasne, dlaczego Twój znajomy poleciłby ci jednoznaczne użycie float arr[M * N] zamiast polegania na niejawnej implementacji tej samej rzeczy przez kompilator.

Sytuacja, która może sprawić, że do rozważenia float arr[M * N] podejście jest, gdy obie M i N są wartościami run-time i kompilator nie obsługuje tablice o zmiennej długości (lub z jakiegoś powodu nie chcą z nich korzystać). W takich przypadkach wbudowana obsługa tablic wielowymiarowych nie ma już zastosowania, ponieważ opiera się na wszystkich rozmiarach (z wyjątkiem pierwszego) będących stałymi w czasie kompilacji. Może to właśnie miał na myśli twój przyjaciel.