What does int **p in mean?

Question

I understand that we use this when we need to give a pointer to an array of pointers in the dynamic memory but what I don't understand is that how this works in the stack.

Does this make an array of pointers in the stack too that is pointing to the array of pointers in the heap or does it make a single pointer in the stack that is pointing to the array of pointers in the heap? if yes, then what is the difference between

int **p = new int*[100]

and

int *p = new int[100]

Thanks in advance. I have been trying to understand this for a long time now and have read a lot of documentation online but I still don't understand this.

Answer 1

int **p declares a pointer on the stack which points to pointer(s) on the heap. Each of that pointer(s) point to an integer or array of integers on the heap.

This:

int **p = new int*[100];

means that you declared a pointer on the stack and initialized it so that it points to an array of 100 pointers on heap. For now each of that 100 pointers point nowhere. By "nowhere" I mean that they point neither to a valid chunk of memory, nor they are nullptrs. They are not initialized, thus they contain some garbage value which was in the memory before the pointers were allocated. You should assign something sensible to them in a loop before usage. Note that p[0] - p[99] pointers are not guaranteed to point to adjacent regions of memory if you assign return values of new to them. For example, if you allocate memory for each of them as p[i] = new int[200];, p[0][201] will not reference p[1][2], but will lead to an undefined behavior.

And this:

int *p = new int[100];

is a pointer on the stack which points to an array of 100 integers on the heap.

Answer 2

Don't worry, pointers and arrays in C are always a source of confusion. In general, when you declare an array of, say type int, you create a pointer of type int that points to the first element in a contiguous block of memory that will store ints. For example, if I have a simple array of ints using int *p_to_intarr = new int[3], I get this:

+++++++  <--------- p_to_intarr
| int |
+++++++
| int |
+++++++
| int |
+++++++

In general, if I want an array of type T, I create a pointer to type T like T *ptr_to_Tarr = new T[3].

So what if I want an array of array of ints? Lets just replace the T in with the type of an "array of ints" and this will give us an array of "array of ints". Well we just say in our first example that the type of an array of ints in int *, and so an array of array of ints would be: int* *ptr_to_arrayofintarr = new int*[3]. Note we just replaced the T with int star. This is often written more neatly as int **ptr_to_arrayofintarr = new int*[3].

So int **p could be a pointer to a 2d array. It could also be a reference to a 1d array; depends on the specific case :)

Answer 3

The new expression evaluates to a pointer of some type, pointing to memory that has been allocated in the free store (essentially the heap) but not necessarily in the free store. (It can still be in the free store depending on the context; for instance, consider an initialization-list in a constructor for an object being allocated in the free store.)

The object(s) initialized by new is/are of course in the free store.

In the assignment statements you've shown, you can see the type of the pointer returned by new on the left side of the equals sign, and the type of the free store object(s) to the right of the new. Thus the only object that is locally evaluated (i.e. might be on the stack) is, in the first case, a pointer-to-pointer-to-int, and in the second case, a pointer-to-int. The objects in free space are an array of pointers-to-ints in the first case and a simple array of ints in the second.

Note that just because the array in the first assignment consists of pointers doesn't mean that the pointers themselves actually point to anything yet; new does not magically recursively allocate free space for objects to be targeted by any pointers in an array it creates. (This wouldn't make much sense anyway.)

Answer 4

The ** means that you have a pointer to pointers. In more practical terms, it means you have a two-dimensional array.

Since each element of the array is also a pointer, you need to initialize those pointers as well:

for (int i = 0; i < 100; ++i)
    p[i] = new int[200];

This initializes a 100x200 array. You can access the bottom-right corner with p[99][199].

When it's time to delete the pointer you have to reverse the process:

for (int i = 0; i < 100; ++i)
    delete [] p[i];
delete [] p;