Ile poziomów wskaźników możemy mieć?


443

Ile wskaźników ( *) jest dozwolonych w jednej zmiennej?

Rozważmy następujący przykład.

int a = 10;
int *p = &a;

Podobnie możemy mieć

int **q = &p;
int ***r = &q;

i tak dalej.

Na przykład,

int ****************zz;

582
Jeśli stanie się to dla ciebie prawdziwym problemem, robisz coś bardzo złego.
ThiefMaster

279
Możesz dodawać kolejne poziomy wskaźników, aż mózg eksploduje lub kompilator się nie stopi - w zależności od tego, co nastąpi wcześniej.
JeremyP,

47
Ponieważ wskaźnik do wskaźnika jest znowu, no cóż, tylko wskaźnikiem, nie powinno być żadnych teoretycznych ograniczeń. Może kompilator nie będzie w stanie obsłużyć go poza jakimś absurdalnie wysokim limitem, ale dobrze ...
Christian Rau

73
w najnowszym c ++ powinieneś użyć czegoś takiegostd::shared_ptr<shared_ptr<shared_ptr<...shared_ptr<int>...>>>
josefx

44
@josefx - pokazuje to problem w standardzie C ++ - nie ma sposobu na podniesienie inteligentnych wskaźników do potęg. Musimy natychmiast zażądać rozszerzenia w celu wsparcia np. (pow (std::shared_ptr, -0.3))<T> x;Dla poziomów -0,3 pośrednich.
Steve314,

Odpowiedzi:


400

Do CNorma określa dolna granica:

5.2.4.1 Limity tłumaczeń

276 Implementacja musi być w stanie przetłumaczyć i wykonać co najmniej jeden program, który zawiera co najmniej jedno wystąpienie każdego z następujących limitów: [...]

279 - 12 deklaratory wskaźników, tablic i funkcji (w dowolnych kombinacjach) modyfikujące arytmetykę, strukturę, sumę lub typ pustki w deklaracji

Górny limit jest specyficzny dla implementacji.


121
Standard C ++ „zaleca”, aby implementacja obsługiwała co najmniej 256. (Czytelność zaleca, aby nie przekraczać 2 lub 3, a nawet wtedy: więcej niż jeden powinien być wyjątkowy.)
James Kanze

22
Limit ten dotyczy liczby w jednej deklaracji; nie narzuca górnej granicy, ile pośredniości można osiągnąć za pomocą wielu typedefs.
Kaz.

11
@Kaz - tak, to prawda. Ale ponieważ specyfikacja (nie jest zamierzona gra słów) określa obowiązkową dolną granicę, jest to efektywna górna granica, którą wszystkie kompilatory zgodne ze specyfikacją muszą obsługiwać. Oczywiście może być niższa niż górna granica specyficzna dla dostawcy. Przeformułowane inaczej (w celu dostosowania go do pytania PO), jest to maksimum dozwolone przez specyfikację (wszystko inne byłoby specyficzne dla dostawcy). Nieco stycznej programiści powinni (przynajmniej w ogólnym przypadku) potraktować to jako swoją górny limit (chyba że mają uzasadniony powód, aby polegać na górnej granicy specyficznej dla dostawcy) ... myślę.
luis.spinal

5
Z drugiej strony, zacznę się skaleczyć, gdybym musiał pracować z kodem, który miał długie łańcuchy dereferencyjne (szczególnie, gdy wszędzie było swobodnie .)
luis.spinal

11
@beryllium: Zazwyczaj liczby te pochodzą z ankiety dotyczącej oprogramowania przed standaryzacją. W tym przypadku przypuszczalnie przyjrzeli się zwykłym programom C i istniejącym kompilatorom C i znaleźli co najmniej jeden kompilator, który miałby problemy z więcej niż 12 i / lub żadnymi programami, które się nie zepsuły, gdybyś ograniczył go do 12.

155

W rzeczywistości programy C zwykle wykorzystują nieskończoną pośrednią wskazówkę. Jeden lub dwa poziomy statyczne są wspólne. Potrójna pośrednia rzadkość. Ale nieskończoność jest bardzo powszechna.

Nieskończoną pośrednią wskaźnikowość osiąga się za pomocą struktury, oczywiście, bez bezpośredniego deklaratora, co byłoby niemożliwe. Potrzebna jest struktura, aby można było uwzględnić inne dane w tej strukturze na różnych poziomach, na których może się to zakończyć.

struct list { struct list *next; ... };

teraz możesz mieć list->next->next->next->...->next. Jest to naprawdę tylko kilka indirections wskaźnik: *(*(..(*(*(*list).next).next).next...).next).next. I .nextjest to po prostu noop, gdy jest to pierwszy element konstrukcji, więc możemy to sobie wyobrazić ***..***ptr.

Naprawdę nie ma na to ograniczenia, ponieważ łącza mogą być przemieszczane za pomocą pętli, a nie gigantycznego wyrażenia takiego jak ten, a ponadto struktura może być łatwo wykonana jako okrągła.

Innymi słowy, połączone listy mogą być ostatecznym przykładem dodania kolejnego poziomu pośredniego rozwiązania problemu, ponieważ robisz to dynamicznie z każdą operacją wypychania. :)


48
Jest to jednak zupełnie inna kwestia - struktura zawierająca wskaźnik do innej struktury jest zupełnie inna niż wskaźnik-wskaźnik. Int ***** to odmienny typ od int ****.
puszysty

12
Nie jest „bardzo” inny. Różnica jest puszysta. Jest bliżej składni niż semantyki. Wskaźnik do obiektu wskaźnika, czy wskaźnik do obiektu struktury, który zawiera wskaźnik? To jest to samo. Dotarcie do dziesiątego elementu listy to dziesięć poziomów pośredniej odpowiedzi. (Oczywiście zdolność do wyrażania nieskończonej struktury zależy od tego, czy typ struktury może wskazywać na siebie za pomocą niekompletnego typu struktury, tak więc list->nexti list->next->nextsą one tego samego typu; w przeciwnym razie musielibyśmy zbudować typ nieskończony.)
Kaz

34
Nie zauważyłem świadomie, że twoje imię jest puszyste, kiedy użyłem słowa „puszysty”. Wpływ podświadomości? Ale jestem pewien, że wcześniej użyłem tego słowa w ten sposób.
Kaz

3
Pamiętaj również, że w języku maszynowym możesz po prostu iterować coś takiego, LOAD R1, [R1]o ile R1 jest prawidłowym wskaźnikiem na każdym kroku. Nie ma w tym żadnego typu innego niż „słowo, które ma adres”. To, czy istnieją zadeklarowane typy, nie determinuje pośrednictwa i liczby poziomów.
Kaz

4
Nie, jeśli struktura jest okrągła. Jeśli R1przechowuje adres lokalizacji, która wskazuje na siebie, LOAD R1, [R1]może być wykonywany w nieskończonej pętli.
Kaz

83

Teoretycznie:

Możesz mieć tyle poziomów pośrednich, ile chcesz.

Praktycznie:

Oczywiście nic, co zajmuje pamięć, nie może być nieokreślone, będą ograniczenia wynikające z zasobów dostępnych w środowisku hosta. Praktycznie więc istnieje maksymalne ograniczenie wsparcia, które wdrożenie może wesprzeć, a wdrożenie powinno je odpowiednio udokumentować. We wszystkich takich artefaktach standard nie określa maksymalnego limitu, ale określa dolne limity.

Oto odniesienie:

C99 Standard 5.2.4.1 Limity tłumaczenia:

- 12 deklaratorów wskaźników, tablic i funkcji (w dowolnych kombinacjach) modyfikujących arytmetykę, strukturę, sumę lub typ pustki w deklaracji.

Określa dolny limit, który musi obsługiwać każda implementacja . Należy zauważyć, że w przypisie norma mówi dalej:

18) Wdrożenia powinny unikać nakładania stałych limitów tłumaczeń, gdy tylko jest to możliwe.


16
pośrednie nie przepełniają żadnych stosów!
Basile Starynkevitch

1
Poprawione, miałem błędne odczucie czytania i odpowiadania na q jako limit parametrów przekazywanych do funkcji. Nie wiem dlaczego ?!
Alok Zaoszczędź

2
@basile - oczekiwałbym, że głębokość stosu będzie problemem w analizatorze składni. Wiele formalnych algorytmów analizowania ma stos jako kluczowy element. Większość kompilatorów C ++ prawdopodobnie używa wariantu zejścia rekurencyjnego, ale nawet to zależy od stosu procesora (lub, pedantycznie, od języka działającego tak, jakby istniał stos procesora). Większe zagnieżdżanie reguł gramatycznych oznacza głębszy stos.
Steve314

8
pośrednie nie przepełniają żadnych stosów! -> Nie! stos parsera może zostać przepełniony. W jaki sposób stos odnosi się do pośrednictwa wskaźnika? Stos parsera!
Pavan Manjunath,

Jeśli *jest przeciążony dla kilku klas w rzędzie, a każde przeciążenie zwraca obiekt innego typu w rzędzie, wówczas może wystąpić przepełnienie stosu dla takich łańcuchowych wywołań funkcji.
Nawaz

76

Jak powiedzieli ludzie, nie ma limitu „w teorii”. Jednak poza zainteresowaniem uruchomiłem to z g ++ 4.1.2 i działało z wielkością do 20 000. Kompilacja była jednak dość wolna, więc nie próbowałem wyżej. Domyślam się, że g ++ też nie narzuca żadnych ograniczeń. (Spróbuj ustawić size = 10i przejrzeć plik ptr.cpp, jeśli nie jest to od razu oczywiste).

g++ create.cpp -o create ; ./create > ptr.cpp ; g++ ptr.cpp -o ptr ; ./ptr

create.cpp

#include <iostream>

int main()
{
    const int size = 200;
    std::cout << "#include <iostream>\n\n";
    std::cout << "int main()\n{\n";
    std::cout << "    int i0 = " << size << ";";
    for (int i = 1; i < size; ++i)
    {
        std::cout << "    int ";
        for (int j = 0; j < i; ++j) std::cout << "*";
        std::cout << " i" << i << " = &i" << i-1 << ";\n";
    }
    std::cout << "    std::cout << ";
    for (int i = 1; i < size; ++i) std::cout << "*";
    std::cout << "i" << size-1 << " << \"\\n\";\n";
    std::cout << "    return 0;\n}\n";
    return 0;
}

72
Nie mogłem dostać więcej niż 98242, kiedy próbowałem. (Zrobiłem skrypt w Pythonie, podwajając liczbę, *aż dostałem taki, który nie powiódł się, i poprzedni, który mijał; następnie przeszukałem binarnie ten przedział pod kątem pierwszego, który się nie powiódł. Cały test trwał mniej niż sekundę biegać.)
James Kanze,

63

Sprawdza się fajnie.

  • Visual Studio 2010 (w systemie Windows 7), możesz mieć 1011 poziomów, zanim pojawi się ten błąd:

    błąd krytyczny C1026: przepełnienie stosu parsera, program jest zbyt złożony

  • gcc (Ubuntu), 100k + *bez awarii! Chyba sprzęt jest tu granicą.

(testowany tylko ze zmienną deklaracją)


5
Rzeczywiście, produkcje dla jednoargumentowych operatorów są rekurencyjne, co oznacza, że ​​parser redukujący przesunięcie przesunie wszystkie *węzły na stos, zanim będzie mógł dokonać redukcji.
Kaz.

28

Nie ma limitu, sprawdź przykład tutaj .

Odpowiedź zależy od tego, co rozumiesz przez „poziomy wskaźników”. Jeśli masz na myśli „Ile poziomów pośredni możesz mieć w jednej deklaracji?” odpowiedź brzmi „co najmniej 12.”

int i = 0;

int *ip01 = & i;

int **ip02 = & ip01;

int ***ip03 = & ip02;

int ****ip04 = & ip03;

int *****ip05 = & ip04;

int ******ip06 = & ip05;

int *******ip07 = & ip06;

int ********ip08 = & ip07;

int *********ip09 = & ip08;

int **********ip10 = & ip09;

int ***********ip11 = & ip10;

int ************ip12 = & ip11;

************ip12 = 1; /* i = 1 */

Jeśli masz na myśli „ile poziomów wskaźnika można użyć, zanim program będzie trudny do odczytania”, to kwestia gustu, ale jest limit. Posiadanie dwóch poziomów pośrednich (wskaźnik do wskaźnika do czegoś) jest powszechne. Co więcej, trudniej jest o tym pomyśleć; nie rób tego, chyba że alternatywa byłaby gorsza.

Jeśli masz na myśli „Ile poziomów pośrednictwa wskaźnika możesz mieć w czasie wykonywania”, nie ma limitu. Ten punkt jest szczególnie ważny w przypadku list cyklicznych, w których każdy węzeł wskazuje następny. Twój program może zawsze podążać za wskazówkami.


7
Prawie na pewno jest limit, ponieważ kompilator musi śledzić informacje w skończonej ilości pamięci. ( g++Przerwana z błędem wewnętrznym przy 98242 na moim komputerze Spodziewam się, że rzeczywista granica zależy od urządzenia i obciążenia Ja też nie należy się spodziewać, że jest to problem występujący w rzeczywistym kodzie...)
James Kanze

2
Tak @ MatthieuM. : Właśnie zastanowiłem się teoretycznie :) Dzięki James za wypełnienie odpowiedzi
Nandkumar Tekale

3
Cóż, połączone listy nie są tak naprawdę wskaźnikiem do wskaźnika, są wskaźnikiem struktury, która zawiera wskaźnik (albo to, albo kończy się niepotrzebne rzucanie)
Random832

1
@ Random832: Nand powiedział „Jeśli masz na myśli„ Ile poziomów pośrednictwa wskaźnika możesz mieć w czasie wykonywania ””, więc wyraźnie usunął ograniczenie mówienia o wskaźnikach do wskaźników (* n).
LarsH

1
Nie rozumiem, o co ci chodzi: „ Nie ma limitu, sprawdź przykład tutaj. „Ten przykład nie dowodzi, że nie ma limitu. To tylko dowodzi, że możliwa jest 12-gwiazdkowa pośrednia zdolność. Nic też nie dowodzi circ_listprzykładu dotyczącego pytania PO: fakt, że można przechodzić przez listę wskaźników, nie oznacza, że ​​kompilator może skompilować pośrednią liczbę gwiazdek.
Alberto,

24

Jest nawet zabawniejszy ze wskaźnikiem funkcji.

#include <cstdio>

typedef void (*FuncType)();

static void Print() { std::printf("%s", "Hello, World!\n"); }

int main() {
  FuncType const ft = &Print;
  ft();
  (*ft)();
  (**ft)();
  /* ... */
}

Jak pokazano tutaj, daje to:

Witaj świecie!
Witaj świecie!
Witaj świecie!

I nie wiąże się to z żadnymi narzutami związanymi ze środowiskiem uruchomieniowym, więc prawdopodobnie możesz je układać tyle, ile chcesz ... dopóki kompilator nie zadławi pliku.


20

Nie ma limitu . Wskaźnik to fragment pamięci, którego zawartość jest adresem.
Jak powiedziałeś

int a = 10;
int *p = &a;

Wskaźnik do wskaźnika jest również zmienną, która zawiera adres innego wskaźnika.

int **q = &p;

Oto qwskaźnik do wskaźnika, którego adres pjuż zawiera adres a.

Nie ma nic szczególnego w wskaźniku do wskaźnika.
Nie ma więc limitu łańcucha poniterów, którzy przechowują adres innej wskazówki.
to znaczy.

 int **************************************************************************z;

jest dozwolone.


17

Każdy programista C ++ powinien słyszeć o (nie) znanym trzygwiazdkowym programatorze

I naprawdę wydaje się, że istnieje jakaś magiczna „bariera wskaźnikowa”, która musi zostać zamaskowana

Cytat z C2:

Trzygwiazdkowy programista

System oceny dla programistów C. Im bardziej pośrednie są twoje wskaźniki (tj. Im więcej „*” przed zmiennymi), tym wyższa będzie Twoja reputacja. Programiści C bez gwiazd praktycznie nie istnieją, ponieważ praktycznie wszystkie nietrywialne programy wymagają użycia wskaźników. Większość z nich to programiści z gwiazdą. W dawnych czasach (no cóż, jestem młody, więc dla mnie wyglądają one jak dawne czasy), czasami można było znaleźć kawałek kodu wykonanego przez trzygwiazdkowego programistę i drżeć z podziwu. Niektórzy twierdzili nawet, że widzieli trzygwiazdkowy kod z włączonymi wskaźnikami funkcji na więcej niż jednym poziomie pośrednim. Brzmiało to dla mnie tak samo jak UFO.


2
github.com/psi4/psi4public/blob/master/src/lib/libdpd/... i tym podobne napisał czterogwiazdkowy programista. Jest także moim przyjacielem i jeśli przeczytasz wystarczająco kod, zrozumiesz powód, dla którego jest wart 4 gwiazdek.
Jeff

13

Zauważ, że istnieją dwa możliwe pytania: ile poziomów pośrednictwa wskaźnika możemy osiągnąć w typie C i ile poziomów pośrednictwa wskaźnika możemy upchnąć w jednym deklaratorze.

Standard C pozwala nałożyć maksimum na te pierwsze (i podaje dla tego minimalną wartość). Można to jednak obejść za pomocą wielu deklaracji typedef:

typedef int *type0;
typedef type0 *type1;
typedef type1 *type2; /* etc */

Tak więc ostatecznie jest to problem implementacyjny związany z ideą, jak duży / złożony może być program C, zanim zostanie odrzucony, co jest bardzo specyficzne dla kompilatora.


4

Chciałbym zaznaczyć, że tworzenie typu z dowolną liczbą * jest czymś, co może się zdarzyć przy metaprogramowaniu szablonu. Zapomniałem, co dokładnie robiłem, ale zasugerowano, że mogę stworzyć nowe odrębne typy, które mają pewien rodzaj meta manewru między nimi za pomocą rekurencyjnych typów T *.

Metaprogramowanie szablonów jest powolnym schodzeniem w szaleństwo, więc nie ma potrzeby usprawiedliwiania się przy generowaniu typu o kilku tysiącach poziomów pośrednich. Jest to po prostu wygodny sposób na mapowanie liczb całkowitych peano, na przykład, na rozwinięcie szablonu jako języka funkcjonalnego.


Przyznaję, że nie rozumiem w pełni twojej odpowiedzi, ale dostałem nowy obszar do zbadania. :)
ankush981,

3

Zasada 17.5 normy MISRA C z 2004 r. Zabrania stosowania więcej niż 2 poziomów pośrednich wskaźników.


15
Jest to prawie zalecane dla programistów, a nie dla kompilatorów.
Cole Johnson

3
Przeczytałem dokument z regułą 17.5 o więcej niż 2 poziomach pośredniego wskaźnika. I niekoniecznie zakazuje więcej niż 2 poziomów. Stwierdza, że ​​należy przestrzegać orzeczenia, ponieważ więcej niż 2 poziomy odpowiadają "non-compliant"ich standardom. Ważnym słowem lub frazą w ich orzeczeniu jest użycie słowa "should"z tego oświadczenia: Use of more than 2 levels of indirection can seriously impair the ability to understand the behavior of the code, and should therefore be avoided.Są to wytyczne ustanowione przez tę organizację, w przeciwieństwie do reguł określonych przez standard językowy.
Francis Cugler,

1

Nie ma czegoś takiego jak prawdziwy limit, ale limit istnieje. Wszystkie wskaźniki są zmiennymi, które zwykle są przechowywane w stosie, a nie w stosie . Stos jest zazwyczaj niewielki (można zmienić jego rozmiar podczas łączenia). Powiedzmy, że masz stos 4 MB, co jest dość normalnym rozmiarem. Powiedzmy, że mamy wskaźnik o rozmiarze 4 bajtów (rozmiary wskaźnika nie są takie same w zależności od architektury, ustawień docelowych i ustawień kompilatora).

W takim przypadku 4 MB / 4 b = 1024maksymalna możliwa liczba to 1048576, ale nie powinniśmy ignorować faktu, że niektóre inne rzeczy są w stosie.

Jednak niektóre kompilatory mogą mieć maksymalną liczbę łańcuchów wskaźników, ale limitem jest wielkość stosu. Jeśli więc zwiększysz rozmiar stosu podczas łączenia z nieskończonością i będziesz mieć maszynę z pamięcią nieskończoności, na której działa system operacyjny obsługujący tę pamięć, będziesz mieć nieograniczony łańcuch wskaźników.

Jeśli użyjesz int *ptr = new int;i umieścisz wskaźnik na stosie, nie jest to tak zwyczajny sposób, że limitem będzie rozmiar sterty, a nie stos.

EDYCJA Po prostu zdaj sobie z tego sprawę infinity / 2 = infinity. Jeśli urządzenie ma więcej pamięci, zwiększa się rozmiar wskaźnika. Więc jeśli pamięć to nieskończoność, a wielkość wskaźnika to nieskończoność, to jest to zła wiadomość ... :)


4
A) Wskaźniki mogą być przechowywane na stercie ( new int*). B) An int*i an int**********mają ten sam rozmiar, przynajmniej na rozsądnych architekturach.

@rightfold A) Tak, wskaźniki mogą być przechowywane w stercie. Ale byłoby zupełnie inaczej, jak tworzenie kontenera zawierającego wskaźniki wskazujące następny poprzedni wskaźnik. B) Oczywiście int*i int**********mają taki sam rozmiar, nie powiedziałem, że mają inne.
ST3

2
Wtedy nie widzę, jak rozmiar stosu jest nawet zdalnie istotny.

@rightfold Myślałem o zwykłym sposobie dystrybucji danych, gdy wszystkie dane są w stosie, a na stosie są to tylko wskaźniki do tych danych. Byłoby to normalne , ale zgadzam się, że możliwe jest umieszczanie wskaźników na stosie.
ST3

„Oczywiście int * i int ********** mają ten sam rozmiar” - standard tego nie gwarantuje (chociaż nie znam żadnej platformy, na której nie jest to prawda).
Martin Bonner wspiera Monikę

0

To zależy od miejsca, w którym przechowujesz wskaźniki. Jeśli są na stosie, masz dość niski limit. Jeśli przechowujesz go na stosie, limit jest znacznie znacznie wyższy.

Spójrz na ten program:

#include <iostream>

const int CBlockSize = 1048576;

int main() 
{
    int number = 0;
    int** ptr = new int*[CBlockSize];

    ptr[0] = &number;

    for (int i = 1; i < CBlockSize; ++i)
        ptr[i] = reinterpret_cast<int *> (&ptr[i - 1]);

    for (int i = CBlockSize-1; i >= 0; --i)
        std::cout << i << " " << (int)ptr[i] << "->" << *ptr[i] << std::endl;

    return 0;
}

Tworzy wskaźniki 1M i na pokazach, w którym punkcie łatwo zauważyć, co łańcuch przechodzi do pierwszej zmiennej number.

BTW. Wykorzystuje 92Kpamięć RAM, więc wyobraź sobie, jak głęboko możesz się posunąć.

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.