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

Nie używałem C bardzo często przez ostatnie kilka lat. Kiedy dzisiaj przeczytałem to pytanie , natknąłem się na składnię C, której nie znałem.

Najwyraźniej w C99 obowiązuje następująca składnia:

void foo(int n) {
    int values[n]; //Declare a variable length array
}

To wydaje się dość przydatną funkcją. Czy kiedykolwiek była dyskusja na temat dodania go do standardu C ++, a jeśli tak, to dlaczego został pominięty?

Niektóre potencjalne przyczyny:

• Owłosione dla dostawców kompilatora do wdrożenia
• Niezgodny z inną częścią standardu
• Funkcjonalność można emulować za pomocą innych konstrukcji C ++

Standard C ++ stwierdza, że ​​rozmiar tablicy musi być stałym wyrażeniem (8.3.4.1).

Tak, oczywiście zdaję sobie sprawę, że w przykładzie z zabawką można by użyć std::vector<int> values(m);, ale to przydziela pamięć ze stosu, a nie ze stosu. A jeśli chcę wielowymiarową tablicę, taką jak:

void foo(int x, int y, int z) {
    int values[x][y][z]; // Declare a variable length array
}

vectorwersja staje się całkiem niezdarna:

void foo(int x, int y, int z) {
    vector< vector< vector<int> > > values( /* Really painful expression here. */);
}

Plasterki, wiersze i kolumny będą również potencjalnie rozłożone w całej pamięci.

Patrząc na dyskusję comp.std.c++, widać wyraźnie, że to pytanie jest dość kontrowersyjne z niektórymi bardzo ważnymi nazwami po obu stronach argumentu. Z pewnością nie jest oczywiste, że a std::vectorjest zawsze lepszym rozwiązaniem.

Niedawno odbyła się dyskusja na ten temat w usenet: Dlaczego nie ma VLA w C ++ 0x .

Zgadzam się z tymi osobami, które wydają się zgadzać, że tworzenie potencjalnie dużej tablicy na stosie, która zwykle ma niewiele miejsca, nie jest dobre. Argumentem jest, że jeśli znasz wcześniej rozmiar, możesz użyć tablicy statycznej. A jeśli nie znasz wcześniej rozmiaru, napiszesz niebezpieczny kod.

C99 VLA mogłyby zapewnić niewielką korzyść z możliwości tworzenia małych tablic bez marnowania miejsca lub wywoływania konstruktorów dla nieużywanych elementów, ale wprowadzą dość duże zmiany w systemie typów (musisz być w stanie określić typy w zależności od wartości środowiska wykonawczego - to nie istnieje jeszcze w obecnym C ++, z wyjątkiem newspecyfikatorów typu operatora, ale są one traktowane specjalnie, aby środowisko wykonawcze nie wymykało się zakresowi newoperatora).

Możesz użyć std::vector, ale nie jest to to samo, ponieważ używa pamięci dynamicznej, a użycie własnego alokatora stosu nie jest łatwe (wyrównanie również stanowi problem). Nie rozwiązuje również tego samego problemu, ponieważ wektor jest pojemnikiem o zmiennym rozmiarze, podczas gdy VLA mają stały rozmiar. Propozycja C ++ Dynamic Array ma na celu wprowadzenie rozwiązania opartego na bibliotece, jako alternatywy dla VLA opartego na języku. Jednak, o ile mi wiadomo, nie będzie to część C ++ 0x.

(Tło: Mam doświadczenie w implementacji kompilatorów C i C ++.)

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

• sizeof xnie jest już zawsze stałą czasową kompilacji; kompilator musi czasem wygenerować kod, aby ocenić sizeof-wyrażenie w czasie wykonywania.

• Pozwalając Włas dwuwymiarowe ( int A[x][y]) wymagane nową składnię deklarowania funkcji, które mają 2D Włas jako parametry: void foo(int n, int A[][*]).

• Mniej ważne w świecie C ++, ale niezwykle ważne dla docelowej grupy C programistów systemów wbudowanych, zadeklarowanie VLA oznacza przełamanie dowolnej dużej części stosu. Jest to gwarantowane przepełnienie stosu i awaria. (Zawsze możesz zadeklarować int A[n], jesteś pośrednio twierdząc, że masz 2GB stosu oszczędzić. Po tym wszystkim, jeśli znasz „ njest zdecydowanie mniej niż 1000 Here”, wtedy po prostu zadeklarować int A[1000]. Podstawiając 32-bitową liczbę całkowitą nza 1000to wstęp że nie masz pojęcia, jakie powinno być zachowanie twojego programu).

OK, przejdźmy teraz do rozmowy o C ++. W C ++ mamy takie samo rozróżnienie pomiędzy „systemem typów” i „systemem wartości”, co C89… ale tak naprawdę zaczęliśmy na nim polegać w sposób, w jaki C nie. Na przykład:

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

Gdyby nnie była stała czasowa kompilacji (tj. Gdyby Abyła zmiennie zmodyfikowanego typu), to czym, u licha, byłby typ S? Czy Styp byłby również określany 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 określonej instancji myfunc. Jak powinien wyglądać ten kod? Jak możemy statycznie wygenerować ten kod, jeśli nie znamy typu A1w czasie kompilacji?

Co gorsza, co się stanie, jeśli okaże się to w czasie wykonywania n1 != n2, tak !std::is_same<decltype(A1), decltype(A2)>()? W takim przypadku wywołanie do myfunc nie powinno się nawet kompilować , ponieważ dedukcja typu szablonu powinna zakończyć się niepowodzeniem! Jak możemy naśladować to zachowanie w czasie wykonywania?

Zasadniczo C ++ zmierza w kierunku popychania coraz większej liczby decyzji do czasu kompilacji : generowania kodu szablonu, constexproceny funkcji i tak dalej. Tymczasem C99 był zajęty popychanie tradycyjnie kompilacji decyzje (np sizeof) do wykonywania . Mając to na uwadze, czy naprawdę warto w ogóle podejmować wysiłki, próbując zintegrować VLA w stylu C99 z C ++?

Jak już zauważył każdy inny odpowiadający, C ++ zapewnia wiele mechanizmów alokacji sterty ( std::unique_ptr<int[]> A = new int[n];lub std::vector<int> A(n);oczywiste), gdy naprawdę chcesz przekazać ideę „Nie mam pojęcia, ile pamięci RAM może potrzebować”. A C ++ zapewnia sprytny model obsługi wyjątków do radzenia sobie z nieuchronną sytuacją, w której potrzebna ilość pamięci RAM jest większa niż ilość pamięci RAM, którą masz. Ale mam nadzieję, że ta odpowiedź daje dobre wyobrażenie o tym, dlaczego VLA w stylu C99 nie pasowały do ​​C ++ - a nawet nie pasowały do ​​C99. ;)

Aby uzyskać więcej informacji na ten temat, patrz N3810 „Alternatywy dla rozszerzeń macierzy” , artykuł Bjarne Stroustrup z października 2013 r. Na temat VLA. POV Bjarne'a bardzo różni się od mojego; N3810 skupia się bardziej na znalezieniu dobrej składni języka C ++ dla rzeczy i na zniechęcaniu do używania surowych tablic w C ++, podczas gdy bardziej skupiłem się na implikacjach dla metaprogramowania i systemu typów. Nie wiem, czy uważa, że ​​implikacje metaprogramowania / systemu typów są rozwiązane, możliwe do rozwiązania lub po prostu nieciekawe.

Dobry post na blogu, który dotyka wielu z tych samych punktów, to „Uzasadnione użycie tablic o zmiennej długości” (Chris Wellons, 27.10.2019).

Zawsze możesz użyć przydziału () do przydzielenia pamięci na stosie w czasie wykonywania, jeśli chcesz:

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

Przydział na stosie oznacza, że ​​zostanie on automatycznie uwolniony, gdy stos się odwija.

Szybka uwaga: Jak wspomniano na stronie podręcznika systemowego Mac OS X dla programu Alba (3), „Funkcja Alcala () zależy od maszyny i kompilatora; jej użycie jest zniechęcone”. Tak, żebyś wiedział.

W mojej własnej pracy zdałem sobie sprawę, że za każdym razem, gdy chciałem czegoś takiego, jak tablice automatyczne o zmiennej długości lub alga (), tak naprawdę nie obchodziło mnie, że pamięć fizycznie znajduje się na stosie procesora, tylko że pochodzi od jakiś rozdzielacz stosu, który nie powodował powolnych podróży na stos ogólny. Mam więc obiekt na wątek, który posiada pewną pamięć, z której może pchać / pop bufory o zmiennej wielkości. Na niektórych platformach zezwalam na to przez MMU. Inne platformy mają stały rozmiar (zwykle towarzyszy temu również stały rozmiar procesora, ponieważ nie ma mmu). Jedna platforma, z którą pracuję (podręczna konsola do gier) ma zresztą cenny mały stos procesorów, ponieważ znajduje się w rzadkiej, szybkiej pamięci.

Nie twierdzę, że wrzucanie buforów o zmiennej wielkości do stosu procesorów nigdy nie jest potrzebne. Szczerze mówiąc, byłem zaskoczony, gdy odkryłem, że nie jest to standard, ponieważ z pewnością wydaje się, że koncepcja dobrze pasuje do języka. Jednak dla mnie wymagania „zmienny rozmiar” i „muszą znajdować się fizycznie na stosie procesora” nigdy nie zostały spełnione. Chodzi o szybkość, więc stworzyłem swój własny „równoległy stos dla buforów danych”.

Są sytuacje, w których przydzielanie pamięci sterty jest bardzo kosztowne w porównaniu do wykonywanych operacji. Przykładem jest matematyka matematyczna. Jeśli pracujesz z małymi matrycami, powiedz od 5 do 10 elementów i wykonuj dużo arytmetyki, narzut malloc będzie naprawdę znaczący. Jednocześnie zmiana wielkości na stałą czasową kompilacji wydaje się bardzo marnotrawna i nieelastyczna.

Myślę, że C ++ sam w sobie jest tak niebezpieczny, ż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 w środowisku wykonawczym, co czyni go bardziej użytecznym: ludzie, którzy piszą programy o kluczowym znaczeniu dla wydajności, będą w dużej mierze korzystać z C ++ i potrzebują jak największej wydajności. Jedną z takich możliwości jest przenoszenie rzeczy ze stosu na stos. Innym jest zmniejszenie liczby bloków sterty. Dopuszczenie VLA jako członków obiektów byłoby jednym ze sposobów na osiągnięcie tego. Pracuję nad taką sugestią. Wprawdzie jest to nieco skomplikowane, ale wydaje się całkiem wykonalne.

Wygląda na to, że będzie dostępny w C ++ 14:

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

Aktualizacja: Nie wprowadzono go do C ++ 14.

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

Byłoby to mniej przydatne w C ++, ponieważ musimy już std::vectorwypełnić tę rolę.

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. Ponadto rozsądnie jest nie przydzielać dużych bloków danych na stos, ponieważ ma on raczej ograniczony rozmiar.

C99 pozwala na VLA. I nakłada pewne ograniczenia na sposób deklarowania VLA. Aby uzyskać szczegółowe informacje, patrz 6.7.5.2 normy. C ++ nie zezwala na VLA. Ale g ++ pozwala na to.

Takie tablice są częścią C99, ale nie są częścią standardowego C ++. jak powiedzieli inni, wektor jest zawsze o wiele lepszym rozwiązaniem, i prawdopodobnie dlatego tablice o zmiennej wielkości nie są w standardzie C ++ (lub w proponowanym standardzie C ++ 0x).

BTW, na pytania dotyczące „dlaczego” standard C ++ jest taki, jaki jest, moderowana grupa dyskusyjna Usenet comp.std.c ++ jest miejscem, do którego można się udać.

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

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

}

Edycja: Możesz utworzyć wektor, który używa alokatora stosu (alokatora), ponieważ alokator jest parametrem szablonu.

Mam rozwiązanie, które faktycznie dla mnie zadziałało. Nie chciałem przydzielać pamięci z powodu fragmentacji w procedurze, która musiała działać wiele razy. Odpowiedź jest bardzo niebezpieczna, więc używaj jej na własne ryzyko, ale korzysta z montażu, aby zarezerwować miejsce na stosie. Mój przykład poniżej wykorzystuje tablicę znaków (oczywiście zmienna o innym rozmiarze 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
    } 
}

Zagrożeń jest wiele, ale wyjaśnię kilka: 1. Zmiana wielkości zmiennej do połowy zabiłaby pozycję stosu 2. Przekroczenie granic tablicy zniszczyłoby inne zmienne i możliwy kod 3. To nie działa w 64 bitach build ... potrzebujesz innego zestawu dla tego (ale makro może rozwiązać ten problem). 4. Specyficzny dla kompilatora (może mieć problemy z przemieszczaniem się między kompilatorami). Nie próbowałem, więc naprawdę nie wiem.