How many levels of pointers can we have?

Question

How many pointers (*) are allowed in a single variable?

Let's consider the following example.

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

Similarly we can have

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

and so on.

For example,

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

Answer 1

The C standard specifies the lower limit:

5.2.4.1 Translation limits

276 The implementation shall be able to translate and execute at least one program that contains at least one instance of every one of the following limits: [...]

279 — 12 pointer, array, and function declarators (in any combinations) modifying an arithmetic, structure, union, or void type in a declaration

The upper limit is implementation specific.

Answer 2

Actually, C programs commonly make use of infinite pointer indirection. One or two static levels are common. Triple indirection is rare. But infinite is very common.

Infinite pointer indirection is achieved with the help of a struct, of course, not with a direct declarator, which would be impossible. And a struct is needed so that you can include other data in this structure at the different levels where this can terminate.

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

now you can have list->next->next->next->...->next. This is really just multiple pointer indirections: *(*(..(*(*(*list).next).next).next...).next).next. And the .next is basically a noop when it's the first member of the structure, so we can imagine this as ***..***ptr.

There is really no limit on this because the links can be traversed with a loop rather than a giant expression like this, and moreover, the structure can easily be made circular.

Thus, in other words, linked lists may be the ultimate example of adding another level of indirection to solve a problem, since you're doing it dynamically with every push operation. :)

Answer 3

Theoretically:

You can have as many levels of indirections as you want.

Practically:

Of course, nothing that consumes memory can be indefinite, there will be limitations due to resources available on the host environment. So practically there is a maximum limit to what an implementation can support and the implementation shall document it appropriately. So in all such artifacts, the standard does not specify the maximum limit, but it does specify the lower limits.

Here's the reference:

C99 Standard 5.2.4.1 Translation limits:

— 12 pointer, array, and function declarators (in any combinations) modifying an arithmetic, structure, union, or void type in a declaration.

This specifies the lower limit that every implementation must support. Note that in a footenote the standard further says:

18) Implementations should avoid imposing fixed translation limits whenever possible.

Answer 4

As people have said, no limit "in theory". However, out of interest I ran this with g++ 4.1.2, and it worked with size up to 20,000. Compile was pretty slow though, so I didn't try higher. So I'd guess g++ doesn't impose any limit either. (Try setting size = 10 and looking in ptr.cpp if it's not immediately obvious.)

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;
}

Answer 5

Sounds fun to check.

• Visual Studio 2010 (on Windows 7), you can have 1011 levels before getting this error:

  fatal error C1026: parser stack overflow, program too complex

• gcc (Ubuntu), 100k+ * without a crash ! I guess the hardware is the limit here.

(tested with just a variable declaration)

Answer 6

There is no limit, check example here.

The answer depends on what you mean by "levels of pointers." If you mean "How many levels of indirection can you have in a single declaration?" the answer is "At least 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 */

If you mean "How many levels of pointer can you use before the program gets hard to read," that's a matter of taste, but there is a limit. Having two levels of indirection (a pointer to a pointer to something) is common. Any more than that gets a bit harder to think about easily; don't do it unless the alternative would be worse.

If you mean "How many levels of pointer indirection can you have at runtime," there's no limit. This point is particularly important for circular lists, in which each node points to the next. Your program can follow the pointers forever.

Answer 7

It's actually even funnier with pointer to functions.

#include <cstdio>

typedef void (*FuncType)();

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

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

As illustrated here this gives:

Hello, World!
Hello, World!
Hello, World!

And it does not involve any runtime overhead, so you can probably stack them as much as you want... until your compiler chokes on the file.

Answer 8

There is no limit. A pointer is a chunk of memory whose contents are an address.
As you said

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

A pointer to a pointer is also a variable which contains an address of another pointer.

int **q = &p;

Here q is pointer to pointer holding the address of p which is already holding the address of a.

There is nothing particularly special about a pointer to a pointer.
So there is no limit on chain of poniters which are holding the address of another pointer.
ie.

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

is allowed.

Answer 9

Every C++ developer should have heard of the (in)famous Three star programmer

And there really seems to be some magic "pointer barrier" that has to be camouflaged

Quote from C2:

Three Star Programmer

A rating system for C-programmers. The more indirect your pointers are (i.e. the more "*" before your variables), the higher your reputation will be. No-star C-programmers are virtually non-existent, as virtually all non-trivial programs require use of pointers. Most are one-star programmers. In the old times (well, I'm young, so these look like old times to me at least), one would occasionally find a piece of code done by a three-star programmer and shiver with awe. Some people even claimed they'd seen three-star code with function pointers involved, on more than one level of indirection. Sounded as real as UFOs to me.

Answer 10

Note that there are two possible questions here: how many levels of pointer indirection we can achieve in a C type, and how many levels of pointer indirection we can stuff into a single declarator.

The C standard allows a maximum to be imposed on the former (and gives a minimum value for that). But that can be circumvented via multiple typedef declarations:

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

So ultimately, this is an implementation issue connected to the idea of how big/complex can a C program be made before it is rejected, which is very compiler specific.

Answer 11

I'd like to point out that producing a type with an arbitrary number of *'s is something that can happen with template metaprogramming. I forget what I was doing exactly, but it was suggested that I could produce new distinct types that have some kind of meta maneuvering between them by using recursive T* types.

Template Metaprogramming is a slow descent into madness, so it is not necessary to make excuses when generating a type with several thousand level of indirection. It's just a handy way to map peano integers, for example, onto template expansion as a functional language.

Answer 12

Rule 17.5 of the 2004 MISRA C standard prohibits more than 2 levels of pointer indirection.

Answer 13

There isn't such a thing like real limit but limit exists. All pointers are variables that are usually storing in stack not heap. Stack is usually small (it is possible to change its size during some linking). So lets say you have 4MB stack, what is quite normal size. And lets say we have pointer which is 4 bytes size (pointer sizes are not the same depending on architecture, target and compiler settings).

In this case 4 MB / 4 b = 1024 so possible maximum number would be 1048576, but we shouldn't ignore the fact that some other stuff is in stack.

However some compilers may have maximum number of pointer chain, but the limit is stack size. So if you increase stack size during linking with infinity and have machine with infinity memory which runs OS which handles that memory so you will have unlimited pointer chain.

If you use int *ptr = new int; and put your pointer into heap, that is not so usual way limit would be heap size, not stack.

EDIT Just realize that infinity / 2 = infinity. If machine has more memory so the pointer size increases. So if memory is infinity and size of pointer is infinity, so it is bad news... :)

Answer 14

It depends on the place where you store pointers. If they are in stack you have quite low limit. If you store it in heap, you limit is much much much higher.

Look at this 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;
}

It creates 1M pointers and at the shows what point to what it is easy to notice what the chain goes to the first variable number.

BTW. It uses 92K of RAM so just imagine how deep you can go.