Incrementally dynamic allocation of memory in C/C++

Question

I have a for-loop that needs to incrementally add columns to a matrix. The size of the rows is known before entering the for-loop, but the size of the columns varies depending on some condition. Following code illustrates the situation:

  N = getFeatureVectorSize();
  float **fmat; // N rows, dynamic number of cols     
  for(size_t i = 0; i < getNoObjects(); i++)
  {
    if(Object[i] == TARGET_OBJECT)
    {
      float *fv = new float[N];
      getObjectFeatureVector(fv);    
      // How to add fv to fmat?
    }
  }

Edit 1 This is how I temporary solved my problem:

  N = getFeatureVectorSize();
  float *fv = new float[N];
  float *fmat = NULL;
  int col_counter = 0;
  for(size_t i = 0; i < getNoObjects(); i++)
  {
    if(Object[i] == TARGET_OBJECT)
    {
      getObjectFeatureVector(fv);    
      fmat = (float *) realloc(fmat, (col_counter+1)*N*sizeof(float));
      for(int r=0; r<N; r++) fmat[col_counter*N+r] = fv[r];
      col_counter++;
    }
  }
  delete [] fv;
  free(fmat);

However, I'm still looking for a way to incrementally allocate memory of a two-dimensional array in C/C++.

Is `N` the column size and `getNoObjects()` the row size? If so, it appears your row size *is* known in advance. What does `getObjectFeatureVector()` do? — pattivacek, Jul 23 '13 at 13:31
The size of feature vector is calculated according to some user input parameters. — Rasoul, Jul 23 '13 at 14:04
So the feature vector size (here `N`) is the row size? Is `getNoObjects()` return the column size? Because it appears that that is also known before entering the loop, unless it produces different output on every iteration of the loop. — pattivacek, Jul 23 '13 at 14:13
`N` is the row size. `getNoObjects()` is not the column size. The column size depends on the number of matches `(Object[i] == TARGET_OBJECT)` that takes place in the for-loop. — Rasoul, Jul 23 '13 at 14:18
I have expanded my answer now that I better understand your matrix design. Thanks for clarifying! — pattivacek, Jul 23 '13 at 15:10

score 1 · Answer 1 · answered Jul 23 '13 at 15:24

1

To answer your original question

// How to add fv to fmat?

When you use float **fmat you are declaring a pointer to [an array of] pointers. Therefore you have to allocate (and free!) that array before you can use it. Think of it as the row pointer holder:

float **fmat = new float*[N];

Then in your loop you simply do

fmat[i] = fv;

However I suggest you look at the std::vector approach since it won't be significantly slower and will spare you from all those new and delete.

answered Jul 23 '13 at 15:24

Fozi

4,973
1
32
56

It seems what I was looking for. It just remains to know how to free the allocated memory by `fmat` (which is holding pointers to `fv`'s). – Rasoul Jul 23 '13 at 15:46
@Rasoul You have to `delete []` each `fmat[i]` and then also `delete [] fmat`. That's why I suggest the `vector` solution instead. – Fozi Jul 23 '13 at 15:58
I tested `delete [] fmat` and I got `glibc detected` run-time error. I changed it to `delete [] *fmat` and got no error. So I guess the latter is correct. – Rasoul Jul 23 '13 at 16:22
@Rasoul `delete [] *fmat` is the same as `delete [] fmat[0]`. `delete [] fmat` should work, are you sure the allocation is ok and you did not delete it before? – Fozi Jul 23 '13 at 16:26
This is what I have tested: `for(int col=0; col – Rasoul Jul 23 '13 at 16:29
@Rasoul Remove the `*`. It's simply `delete [] fmat;`. – Fozi Jul 23 '13 at 16:31
@Rasoul You should **really** take a look at my other answer. None of these problems, same speed. – Fozi Jul 23 '13 at 16:39
From your code I understood that we are doing two different things! Please note that we don't know the number of columns in advance. – Rasoul Jul 23 '13 at 16:44

score 0 · Answer 2 · edited May 23 '17 at 10:25

0

better - use boost::MultiArray as in the top answer here :

How do I best handle dynamic multi-dimensional arrays in C/C++?

trying to dynamically allocate your own matrix type is pain you do not need.

Alternatively - as a low-tech, quick and dirty solution, use a vector of vectors, like this :

C++ vector of vectors

edited May 23 '17 at 10:25

Community

1
1

answered Jul 23 '13 at 13:26

Graham Griffiths

2,196
1
12
15

If I want to use C++ vector of vector, how I should initialize the inner `vector` with `fv`? Besides, the performance is important. – Rasoul Jul 23 '13 at 14:05
create it with the correct number of entries (N I think) and then just assign to them. std::vector innerVector(N); innerVector(0) = 1.0; innerVector(1) = 3.4; etc. It's true, it's not the highest performance solution, but it's probably the fastest way to get something working and correct, and worth testing to see if it meets your performance requirements – Graham Griffiths Jul 23 '13 at 14:15
If you really have to dynamically allocate, check out the advice in the answer here : http://stackoverflow.com/questions/16559241/why-does-the-top-code-work-and-the-bottom-code-not-in-c-for-dynamic-matrix-all?rq=1 i.e. allocate just a single long array and treat it as a matrix when indexing into it. – Graham Griffiths Jul 23 '13 at 14:20
you could even create a single long vector of size N * NObjects. Actually that's probably the easiest way. Memory allocation is taken care of for you, and you just index into it as if it were a matrix (as per previous comment) – Graham Griffiths Jul 23 '13 at 14:22
Unfortunately it is not practical since the number of objects and the length of the feature vector are both large numbers. In comparison a small percentage of objects fulfils the if-condition. In other words, the number of columns is greatly less than `getNoObjects()`. – Rasoul Jul 23 '13 at 14:26

pattivacek · Answer 3 · 2013-07-23T15:09:31.477

If you want to do this without fancy data structures, you should declare fmat as an array of size N of pointers. For each column, you'll probably have to just guess at a reasonable size to start with. Dynamically allocate an array of that size of floats, and set the appropriate element of fmat to point at that array. If you run out of space (as in, there are more floats to be added to that column), try allocating a new array of twice the previous size. Change the appropriate element of fmat to point to the new array and deallocate the old one.

This technique is a bit ugly and can cause many allocations/deallocations if your predictions aren't good, but I've used it before. If you need dynamic array expansion without using someone else's data structures, this is about as good as you can get.

Fozi · Answer 4 · 2013-07-23T17:15:31.013

To elaborate the std::vector approach, this is how it would look like:

// initialize
N = getFeatureVectorSize();
vector<vector<float>> fmat(N);

Now the loop looks the same, you access the rows by saying fmat[i], however there is no pointer to a float. You simply call fmat[i].resize(row_len) to set the size and then assign to it using fmat[i][z] = 1.23.

In your solution I suggest you make getObjectFeatureVector return a vector<float>, so you can just say fmat[i] = getObjectFeatureVector();. Thanks to the C++11 move constructors this will be just as fast as assigning the pointers. Also this solution will solve the problem of getObjectFeatureVector not knowing the size of the array.

Edit: As I understand you don't know the number of columns. No problem:

deque<vector<float>> fmat();

Given this function:

std::vector<float> getObjectFeatureVector();

This is how you add another column:

fmat.push_back(getObjectFeatureVector());

The number of columns is fmat.size() and the number of rows in a column is fmat[i].size().

Incrementally dynamic allocation of memory in C/C++

4 Answers4