Why are the values stored in memory locations changing?

Question

I am trying to implement segment tree. In the following way:

#include<bits/stdc++.h>
using namespace std;
int size;
int construct(int *arr,int *s,int curr,int end,int ad)
{
    if(arr[curr]==arr[end])
    {
        s[ad]=arr[curr];
        return s[ad];   
    }
    int mid=(curr+end)/2;
    s[ad]=construct(arr,s,curr,mid,ad*2+1)+construct(arr,s,mid+1,end,ad*2+2);
    return s[ad];
}
int* cons(int *arr,int n)
{
    int height=ceil(log2(n));
    size=(int)(2*pow(2,height)-1);
    int s[(int)(2*pow(2,height)-1)]={0};
    construct(arr,s,0,n-1,0);
    //printf("\n In cons function \n\n");
    for (int i = 0; i <size; ++i)
    {
        printf("%d  %p\n",s[i], &s[i] );
    }
    int *po=s;
    printf("\n%p  %d\n",po,size );
    return po;
}
int main()
{
    int arr[6]={1,3,5,7,9,11};   
    int *b=cons(arr,6);
    printf("%p  %d\n\n",b,size );
    //printf("\n\n In main function \n\n");
    for (int i = 0; i <size; ++i)
    {
        printf("%d  %p\n",b[i],&b[i]);
    }
return 0;   
}

When I am printing array values in function cons, it displays expected values. Then I return the address of the starting of the array which I store in the main function. Now when I print the same values in main function, some of the values are different, even though the address where the value is stored remain same.

Here's a sample output:

36  0x7ffce0eb6130
9  0x7ffce0eb6134
27  0x7ffce0eb6138
4  0x7ffce0eb613c
5  0x7ffce0eb6140
16  0x7ffce0eb6144
11  0x7ffce0eb6148
1  0x7ffce0eb614c
3  0x7ffce0eb6150
0  0x7ffce0eb6154
0  0x7ffce0eb6158
7  0x7ffce0eb615c
9  0x7ffce0eb6160
0  0x7ffce0eb6164
0  0x7ffce0eb6168

0x7ffce0eb6130  15
0x7ffce0eb6130  15

36  0x7ffce0eb6130
9  0x7ffce0eb6134
9  0x7ffce0eb6138
0  0x7ffce0eb613c
-521445060  0x7ffce0eb6140
32764  0x7ffce0eb6144
20  0x7ffce0eb6148
0  0x7ffce0eb614c
0  0x7ffce0eb6150
0  0x7ffce0eb6154
18  0x7ffce0eb6158
0  0x7ffce0eb615c
9  0x7ffce0eb6160
0  0x7ffce0eb6164
0  0x7ffce0eb6168

Answer 1

Look at your code:

int* cons(int *arr,int n)
{
    ....
    int s[(int)(2*pow(2,height)-1)]={0};
    ...
    int *po=s;
    printf("\n%p  %d\n",po,size );
    return po;
}

Which is called by

int *b=cons(arr,6);

Here, po is a pointer to the first element of s. This po, which points to a local variable, is then returned to the caller of cons. Eventually b points to released stack space.

Later you have

printf("%d %p\n",b[i],&b[i]);

which refers to released stack. This is undefined behavior. In practice, the implementation of printf reuses the released stack, overwriting parts of b (maybe all of it). That's why reading a released stack is undefined behavior.

There are several possible solutions. Use and return std::vector, instead of a pointer. Usually, this is the preferred solution.

In C you may pass a pointer to the output array to cons. Also, in C, you might use malloc() inside cons, and use it instead of the s array in cons. You would return that pointer, and the caller would be responsible to call free(). But all this only if you want to stick to C idioms, instead of C++.