Only the stack can store local (pointer) variables, not Heap?

Solution 1:

Yes, you can put your pointer on the free store (heap) and have it point to a variable on the stack. The trick is to create a pointer to a pointer (int**):

int main()
{
    int i = 0; // int on the stack

    int** ip = new int*; // create an int* (int pointer) on the free store (heap)

    // ip (the int**) is still on the stack

    *ip = &i;
    // Now your free store (heap) located pointer points
    // to your stack based variable i

    delete ip; // clean up
}

NOTE: The terms "heap" and "stack" are general, well understood, computing terms. In C++ they are referred to in the Standard as the "free store" and (although not directly named) a "stack" is 100% implied (eg. through references to "stack-unwinding") and therefore required.

Solution 2:

stack and heap are not specifically defined by the standard. Those are implementation details.

Heap refers to a data structure that many operating systems use to help them safely manage the allocated space for different programs running at the same time. Read more here

Here is a diagram for a simple heap so that you can have a mental model of it:

Keep in mind that this is not exactly what operating systems use. In fact, operating systems use a far more advanced form of the heap data structure that allows them to perform many sorts of complex memory-related tasks. Also, not every OS implements the free store using the heap data structure. Some may use different techniques.

Whereas a stack is much simpler:

can we have a pointer that is actually located on the heap, and it points to a variable located on Stack?

Yes, it's possible but rarely needed:

#include <iostream>

int main( )
{
    int a_variable_on_stack { 5 };
    int** ptr_on_stack { new int*( &a_variable_on_stack ) };

    std::cout << "address of `a_variable_on_stack`: " << &a_variable_on_stack << '\n'
              << "address of ptr on the heap: " << ptr_on_stack << '\n'
              << "value of ptr on the heap: " << *ptr_on_stack << '\n';

    std::cin.get( );
}

Possible output:

address of `a_variable_on_stack`: 0x47eb5ffd2c
address of ptr on the heap: 0x1de33cc3810
value of ptr on the heap: 0x47eb5ffd2c

Notice how the address of a_variable_on_stack and value of ptr stored on heap are both 0x47eb5ffd2c. In other words, a pointer on the heap is holding the address of a variable that is on the stack.

Solution 3:

In short:

Variables declared within a function are allocated on the stack, and can point to whatever you want (to address of other variables on the stack and to address of other variables on the heap).

Same is for variables declared on the heap. They can point to address of other variables on the heap or to address of variables on the stack. There is no limitation here.

However, variables declared on the stack, are by nature temporary, and when function return this memory is reclaimed. Therefor it is not a good practice to have pointers to variable's address at the stack, unless you know the function did not finish yet (i.e. using local variables address from within the same function or by functions calls from within the same function). A common mistake of novice C/C++ developers, is to return from function, address of variable declared on the stack. When function returns, this memory is reclaimed and will be soon reused for other function calls memory, so accessing this address has undefined behavior.

Solution 4:

I am new to C and C++.

Your question is not C or C++ specific, but it is about programming languages in general.

... whenever a function is called, its variables get memory allocated on the stack ...

This is correct: Nearly all compilers do it this way.

However, there are exceptions - for example on SPARC or TriCore CPUs, which have a special feature...

... allocated on the heap via malloc ...

malloc never allocates memory on the stack but on the heap.

... is not guaranteed that the storage allocated by malloc is 100% on the heap ...

Unlike the word "stack", the meaning of the word "heap" differs a bit from situation to situation.

In some cases, the word "heap" is used to specify a certain memory area that is used by malloc and new.

If there is not enough memory in that memory area, malloc (or new) asks the operating system for memory in a different memory area.

However, other people would also call that memory area "heap".

... in both cases, variable p is on the stack, and it points to the object on the heap.

This is correct.

... can we have a pointer that is actually located on the heap, and it points to a variable located on Stack?

Sure:

int ** allocatedMemory;

void myFunction()
{
    int variableOnStack;
    allocatedMemory = (int **)malloc(sizeof(int *));
    *allocatedMemory = &variableOnStack;
    ...
}

The variable allocatedMemory points to some data on the heap and that data is a pointer to a variable (variableOnStack) on the stack.

However, when the function myFunction() returns, the variable variableOnStack does no longer exist. Let's say the function otherFunction() is called after myFunction():

void otherFunction()
{
    int a;
    int b;
    ...
}

Now we don't know if *allocatedMemory points to a, to b or even the "return address" because we don't know which of the two variables is stored at the same address as variableOnStack.

Bad things may happen if we write to **allocatedMemory now...

In order to access something in heap, we can only access it via pointers on the stack??

... diagram "B" ...

To access some data on the heap, you definitely need some pointer that is not stored on the heap.

This pointer can be:

• A global or static variable
  In my example above, allocatedMemory is a global variable.
  Global and static variables are neither stored in a completely different memory area (not heap nor stack)
• A local variable on the stack
• A local variable in a CPU register
  (I already wrote that local variables are not always stored on the stack)

Theoretically, the situation in diagram "B" is possible: Simply overwrite the variable allocatedMemory by NULL (or another pointer).

However, a program cannot directly access data on the heap.

This means that p* (which is some data on the heap) cannot be accessed any more if there is no more pointer "outside" the heap that points to p*.