Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Array as template parameter: stack or heap?

My knowledge of the stack as compared with the heap is very rudimentary, but when it comes to arrays, from what I know something like this is created on the stack

float x[100];

whereas something like this is created on the heap

float* x = new float[100];

But what happens if I create a template array class, and pass it in a "stack" array type (like float[100])? Example:

#include <iostream>

using namespace std;

template <class T>
class Array {
public:
    int size;
    T* data;

    Array(int size_) : size(size_) {
        data = new T[size];
    }

    ~Array() {
        delete [] data;
    }
};

int main() {
    int m = 1000000;
    const int n = 100;
    Array<float[n]>* array = new Array<float[n]>(m);

    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            array->data[i][j] = i * j;

    cout << array->data[10][9] << endl;
    delete array;
}

What exactly is going on here? Is this memory created on the stack, or on the heap? My guess is the heap, but how does this work? Does the compiler allocate one large block of memory, and then store pointers that index into it every n elements? Or does it allocate many smaller blocks of memory (not necessarily contiguous), and store pointers to each block?

Furthermore, I can't seem to do this without the aid of a template. Specifically, this code does not compile:

int m = 1000;
const int n = 100;
(float[n])* array = new (float[n])[m];

What is going on here?

EDIT:

Thanks for the syntax tips, everyone. What I was really interested in is what happens in the block

int m = 1000;
const int n = 100;
float (*array)[n] = new float[m][n];

but I didn't know how to write it without the use of templates. One thing I was really interested in is if the compiler allocates this as one large block on the heap, how can you use the syntax array[i][j] to access a particular element without storing pointers to every n-th element? Then I realized that since n is constant, sizeof(float[n]) is fixed, so when you make the array, the compiler is allocating an array of m elements where each element is a float[n], which in my case is 100 * 4 = 400 bytes. Now it all makes sense. Thanks!

like image 270
hunse Avatar asked Jul 17 '14 19:07

hunse


1 Answers

Array<float[n]>* array = new Array<float[n]>(m);

What is going on here is two heap allocations. The Array object will be allocated on the heap because you used new to create it. The new-expression calls the Array constructor, which again uses new to allocate the array data; therefore data is also allocated on the heap.

It is better to do this:

Array<float[n]> array(m);

This allocates array on the stack (so it will automatically be destroyed at the end of the block). However, while the array object itself is on the stack, the data is still stored on the heap because it's allocated on the heap in the Array constructor. This is similar to what happens when you have a std::vector or std::string local variable.

Furthermore, I can't seem to do this without the aid of a template. Specifically, this code does not compile:

This is just because your syntax is wrong. The correct syntax is:

float (*array)[n] = new float[m][n];

The left-hand side shows the correct way to declare a pointer to an array. For the right-hand side, you want an array of m float[n]s. This is denoted float[m][n]; the [m] doesn't go at the end.

like image 66
Brian Bi Avatar answered Sep 20 '22 13:09

Brian Bi