Dlaczego tablice o zmiennej długości nie są częścią standardu C++?

(Tło: mam pewne doświadczenie we wdrażaniu kompilatorów C i C++.)

Tablice o zmiennej długości w C99 były w zasadzie błędem. Aby wesprzeć VLAs, C99 musiał poczynić następujące ustępstwa na rzecz zdrowego rozsądku:

• sizeof x nie zawsze jest stałą czasu kompilacji; kompilator musi czasami generować kod, aby ocenić sizeof - wyrażenie w czasie wykonywania.

• Użycie dwuwymiarowego VLAs (int A[x][y]) wymagało nowej składni deklaracji funkcje, które przyjmują 2D VLAs jako parametry: void foo(int n, int A[][*]).

• Mniej ważne w świecie C++, ale niezwykle ważne dla grupy docelowej programistów systemów wbudowanych, deklarowanie VLA oznacza chomping arbitralnie duży kawałek stosu. To jest gwarantowane przepełnienie stosu i awaria. (Za każdym razem, gdy deklarujesz int A[n], w domyśle twierdzisz, że masz 2GB stosu. Wszakże jeśli wiesz "n jest tu zdecydowanie mniej niż 1000", to po prostu zadeklarujesz int A[1000]. Zastąpienie 32-bitowej liczby całkowitej n dla {[10] } jest przyznaniem, że nie masz pojęcia, jakie powinno być zachowanie Twojego programu.)

Ok, przejdźmy teraz do rozmowy o C++. W C++ mamy takie samo silne rozróżnienie między "systemem typów" i "systemem wartości", jak w C89... ale naprawdę zaczęliśmy polegać na nim w sposób, w jaki C nie ma. Na przykład:

template<typename T> struct S { ... };
int A[n];
S<decltype(A)> s;  // equivalently, S<int[n]> s;

If n were ' t a compile-time constant (tj. if A were of zmiennie zmodyfikowany Typ), to jaki na ziemi byłby Typ S? Czy typ S również może być określony tylko w czasie wykonywania?

A co z tym:

template<typename T> bool myfunc(T& t1, T& t2) { ... };
int A1[n1], A2[n2];
myfunc(A1, A2);

Kompilator musi wygenerować kod dla pewnej instancji myfunc. Jak powinien wyglądać ten kod? Jak możemy statycznie wygenerować ten kod, jeśli nie znamy typu A1 podczas kompilacji?

Gorzej, co jeśli okaże się w czasie pracy, że n1 != n2, tak że !std::is_same<decltype(A1), decltype(A2)>()? W takim przypadku wezwanie do myfunc nie powinien nawet kompilować, ponieważ dedukcja typu szablonu powinna zawieść! Jak moglibyśmy naśladować to zachowanie w czasie pracy?

Zasadniczo C++ zmierza w kierunku pchania coraz większej liczby decyzji w czas kompilacji : generowanie kodu szablonu, ocena funkcji i tak dalej. W międzyczasie C99 był zajęty wprowadzaniem tradycyjnie decyzji w czasie kompilacji (np. sizeof) do środowiska uruchomieniowego {40]}. Mając to na uwadze, czy naprawdę ma to sens aby poświęcić jakiś wysiłek próbując zintegrować VLAs w stylu C99 z C++?

Jak każdy inny odpowiadający już zauważył, C++ zapewnia wiele mechanizmów alokacji sterty (std::unique_ptr<int[]> A = new int[n]; lub std::vector<int> A(n); będąc oczywistymi), gdy naprawdę chcesz przekazać ideę "nie mam pojęcia, ile pamięci RAM mogę potrzebować."A C++ zapewnia sprytny model obsługi wyjątków do radzenia sobie z nieuniknioną sytuacją, że ilość pamięci RAM, której potrzebujesz, jest większa niż ilość pamięci RAM, którą masz. Ale mam nadzieję, że ta odpowiedź daje Ci dobre pojęcie, dlaczego VLAs w stylu C99 były a nie dobrym dopasowaniem do C++-a nawet nie bardzo dobrym dopasowaniem do C99. ;)

Aby dowiedzieć się więcej na ten temat, zobacz N3810 "Alternatives for Array Extensions", artykuł Bjarne Stroustrupa z października 2013 r.na temat VLAs. POV Bjarne ' a bardzo różni się od mojego; N3810 skupia się bardziej na znalezieniu dobrej składni C++ish dla rzeczy, i na zniechęcaniu do używania surowych tablic w C++, podczas gdy ja skupiłem się bardziej o implikacjach dla metaprogramowania i rodzaju systemu. Nie wiem, czy uważa implikacje metaprogramowania / typesystem za rozwiązane, rozwiązywalne, czy po prostu nieciekawe.

Dobrym postem na blogu, który trafia w wiele z tych samych punktów, jest "legalne użycie tablic o zmiennej długości" (Chris Wellons, 2019-10-27).

Możesz zawsze użyć alloca() do przydzielania pamięci na stosie w czasie wykonywania, jeśli chcesz:

void foo (int n)
{
    int *values = (int *)alloca(sizeof(int) * n);
}

Przydzielenie na stos oznacza, że zostanie on automatycznie zwolniony, gdy stos się odwija.

Krótka notatka: jak wspomniano na stronie podręcznika Mac OS X dla alloca (3), " funkcja alloca () jest zależna od Maszyny i kompilatora; jej użycie jest odwagą."Tak dla twojej wiadomości.

W mojej własnej pracy zdałem sobie sprawę, że za każdym razem, gdy chciałem czegoś w rodzaju automatycznych tablic o zmiennej długości lub alloca(), nie przejmowałem się tym, że pamięć była fizycznie zlokalizowana na stosie procesora, tylko że pochodziła z jakiegoś alokatora stosu, który nie powodował powolnych podróży do ogólnego stosu. Mam więc obiekt per-thread, który posiada pewną pamięć, z której może popychać / pop bufory o zmiennej wielkości. Na niektórych platformach pozwalam na to za pośrednictwem mmu. Inne perony mają stały rozmiar (zwykle wraz ze stosem procesora o stałej wielkości, ponieważ nie ma mmu). Jedna platforma, z którą pracuję (przenośna konsola do gier) i tak ma cenny mały stos procesora, ponieważ znajduje się w niewielkiej, szybkiej pamięci.

Nie mówię, że wpychanie buforów o zmiennej wielkości na stos procesora nigdy nie jest potrzebne. Szczerze mówiąc byłem zaskoczony, kiedy odkryłem, że nie jest to standard, ponieważ z pewnością wydaje się, że koncepcja pasuje do języka wystarczająco dobrze. Dla mnie jednak wymagania "zmienny rozmiar" i " musi być fizycznie zlokalizowane na stosie procesora " nigdy nie powstały razem. Chodziło o szybkość, więc stworzyłem własny rodzaj "stosu równoległego dla buforów danych".

Wydaje się, że będzie on dostępny w C++14:

Https://en.wikipedia.org/wiki/C%2B%2B14#Runtime-sized_one_dimensional_arrays

Update: nie przerobiono go na C++14.

Są sytuacje, w których alokacja pamięci sterty jest bardzo kosztowna w porównaniu z wykonywanymi operacjami. Przykładem jest matematyka macierzowa. Jeśli pracujesz z małymi macierzami powiedz 5 do 10 elementów i wykonaj dużo arytmetyki, narzut malloca będzie naprawdę znaczący. Jednocześnie uczynienie rozmiaru stałą czasową kompilacji wydaje się bardzo marnotrawne i nieelastyczne.

Myślę, że C++ jest tak niebezpieczne samo w sobie, że argument "staraj się nie dodawać więcej niebezpiecznych funkcji" nie jest zbyt silny. Z drugiej strony, ponieważ C++ jest prawdopodobnie najbardziej wydajnym językiem programowania, funkcje, które sprawiają, że jest bardziej przydatne, są zawsze użyteczne: ludzie, którzy piszą programy o krytycznym działaniu, będą w dużym stopniu używać C++ i potrzebują jak największej wydajności. Jedną z takich możliwości jest przenoszenie rzeczy ze sterty na stertę. Redukcja liczby bloków sterty jest inna. Jednym ze sposobów osiągnięcia tego celu jest dopuszczenie VLAs jako elementów obiektowych. Pracuję nad taką sugestią. Jest to nieco skomplikowane do wdrożenie, co prawda, ale wydaje się całkiem wykonalne.

To zostało rozważone do włączenia w C++ / 1x, , ale zostało porzucone (jest to korekta do tego, co powiedziałem wcześniej).

Byłoby to mniej przydatne w C++, ponieważ mamy już std::vector do wypełnienia tej roli.

Użyj do tego std::vector. Na przykład:

std::vector<int> values;
values.resize(n);

Pamięć zostanie przydzielona na stercie, ale ma to tylko niewielką wadę wydajności. Co więcej, mądrze jest nie przydzielać dużych bloków danych na stosie, ponieważ jest on raczej ograniczony pod względem rozmiaru.

Tablice takie jak ta są częścią C99, ale nie częścią standardowego C++. jak inni mówili, wektor jest zawsze dużo lepszym rozwiązaniem, dlatego tablice o zmiennej wielkości nie są w standatrd C++ (lub w proponowanym standardzie C++0x).

BTW, na pytania "dlaczego" standard C++ jest taki jaki jest, moderowana Grupa dyskusyjna Usenet comp.choroby weneryczne.c++{[4] } to miejsce, do którego warto się udać.

C99 pozwala na VLA. I wprowadza pewne ograniczenia dotyczące sposobu deklarowania VLA. Szczegółowe informacje można znaleźć w pkt 6.7.5.2 normy. C++ wyłącza VLA. Ale g++ na to pozwala.

Jeśli znasz wartość podczas kompilacji, możesz wykonać następujące czynności:

template <int X>
void foo(void)
{
   int values[X];

}

Edit: możesz utworzyć wektor a, który używa alokatora stosu (alloca), ponieważ alokator jest parametrem szablonu.

Mam rozwiązanie, które naprawdę działa dla mnie. Nie chciałem przydzielać pamięci z powodu fragmentacji na rutynę, która musiała działać wiele razy. Odpowiedź jest niezwykle niebezpieczna, więc używaj jej na własne ryzyko, ale wykorzystuje montaż, aby zarezerwować miejsce na stosie. Mój przykład poniżej używa tablicy znaków (oczywiście inna zmienna wielkości wymagałaby więcej pamięci).

void varTest(int iSz)
{
    char *varArray;
    __asm {
        sub esp, iSz       // Create space on the stack for the variable array here
        mov varArray, esp  // save the end of it to our pointer
    }

    // Use the array called varArray here...  

    __asm {
        add esp, iSz       // Variable array is no longer accessible after this point
    } 
}

Niebezpieczeństwa tutaj jest wiele, ale wyjaśnię kilka: 1. Zmiana rozmiaru zmiennej w połowie drogi through zabiłoby pozycję stosu 2. Przekroczenie granic tablicy zniszczyłoby inne zmienne i możliwy kod 3. To nie działa w 64-bitowej kompilacji... potrzeba do tego innego zestawu (ale makro może rozwiązać ten problem). 4. Specyficzny dla kompilatora (może mieć problemy z poruszaniem się między kompilatorami). Nie próbowałem, więc naprawdę Nie wiem.