6

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!

hunse
  • 3,175
  • 20
  • 25
  • 2
    You violated the Rule Of Three. I know it's not related to the point, but it's a good habit to have seeing or typing a destructor definition automatically ring warning bells and get you to think about copying and assignment. (And if you don't want to bother, declare them private in C++03 or deleted in C++11). – aschepler Jul 17 '14 at 19:46

4 Answers4

3
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.

Brian Bi
  • 111,498
  • 10
  • 176
  • 312
2

You've written your array extents backwards. This works:

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

If you want to keep the array extents in the same order you can use a type alias or appropriate template:

  using A = float[n];
  A* array = new A[m];

or

// at file scope
template<typename T, unsigned N> using add_extent = T[N];
// ...
  add_extent<float, n>* array = new add_extent<float, n>[m];

A multidimensional array whether on the stack or the heap is allocated as a single block of m*n elements. When you index a pointer to array type (like float (*array)[n]), the pointer is incremented n elements at a time, per the stride of the array type.

ecatmur
  • 152,476
  • 27
  • 293
  • 366
  • I've seen multidimensional arrays done as separate blocks: `float** data2 = new float*[m]; for (int i = 0; i < m; i++) data2[i] = new float[n];` – hunse Jul 17 '14 at 20:22
  • @hunse that's possible, but inefficient compared to a single block. Note that `float**` is a different type to `float (*)[N]`. – ecatmur Jul 17 '14 at 20:24
  • @hunse if you're thinking about arrays with multiple variable dimensions, there are library solutions that still give you a single allocation, and perform index arithmetic for you, principally Boost.MultiArray: http://www.boost.org/doc/libs/1_55_0/libs/multi_array/doc/user.html – ecatmur Jul 17 '14 at 20:27
  • I just tried out `boost::multi_array`, and for the basic creation and data-writing task I tried it's much slower than just making my own flat array on the heap and doing the indexing myself. This is true whether I use no optimization or `-O3` (with g++). EDIT: I should follow that up by saying with `-O3`, the writing part is only slightly slower, but allocating the object is MUCH slower. As in even slower than allocating the array as separate blocks, which is surprising. – hunse Jul 17 '14 at 20:36
  • Thanks. Your statement "the pointer is incremented n elements at a time, per the stride of the array type" really helped me understand what's going on. – hunse Jul 18 '14 at 13:40
1

All the memory goes on the heap. The compiler allocates one giant chunk of memory for the array-of-arrays, and sets up the indexing so that it's accessible.

And as an aside if anyone ever copies or assigns your Array class you'll leak memory and/or double delete.

nobody
  • 19,814
  • 17
  • 56
  • 77
Mark B
  • 95,107
  • 10
  • 109
  • 188
1

In the line

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

An instance of Array<T> is allocated on the heap. You already understood that, given your first statement about allocations in general.

Perhaps the confusing part is the use of float[n] as a template parameter?

The template parameter T, as denoted by the keyword class in your definition of Array, represents a type. It isn't in itself related to any form of allocation.

As a demonstration of this, let's write a simple template which doesn't make any use of its parameter:

#include <cassert>

using namespace std;

template <typename T>
class A {
};

int main(){

    A<float[100]> a1;
    A<float[1000]> a2;
    float f[100];

    assert(sizeof(a1) == sizeof(a2));
    cout << "a1 : " << sizeof(a1) << endl;
    cout.<< "f : " << sizeof(f) << endl;
}

Output:

a1 : 1
f : 400

So float[n] here is indeed a type(1).

On the other end, when you use the keyword new, you know that something is being allocated on the heap. So as I said, the array variable will point to a memory chunk in the heap. Furthermore the template itself contains a heap allocation (again, keyword new).

Finally, I would like to nuance the basic premise that new indicates a heap allocation. While by default it is the case, when used in placement mode, the actual allocation could very well be on the stack.

(1) Note that C++ accepts it as such because n is declared as a constant, and thus the resulting type may be evaluated at compilation time. Remove the const trait of the definition of n, and the compiler will complain.

Community
  • 1
  • 1
didierc
  • 14,572
  • 3
  • 32
  • 52