Fast convert double pointer array into single pointer, probably can be continuous

Question

I am using a library that returns the image as a big 2D array int**. I need to convert it into int* 1D array. I think I've managed to do it quite fast by copying memory blocks:

// have int labels** as 2D array, also have rows and cols 

//create 1D array
int *labels1D = new int[rows*cols];

//copy contents
for(int i = 0; i < rows; i++) {        
    // Here I don't know anything about how those arrays were allocated
    // Maybe std::copy would handle it for me?
    std::copy_n(labels[i], cols, labels1D + i*cols);
}

So the first question is whether I can do something better here? Is everything safe here assuming that library is a black box?

---

I do not want much to modify the library code, but I've found additionally how the source array in my side library this->currentLabels was created:

int** currentLabels; //in class declaration
...
// in the code
this->currentLabels = new int*[this->height];

for (int i = 0; i < this->height; ++i) {
    this->currentLabels[i] = new int[this->width];

    for (int j = 0; j < this->width; ++j) {
     // some code for setting the value
        }

    }

Looks like the values for rows and cols are known.

So the second question is: can I modify this code to make it allocate the 2D array in one memory block:

this->currentLabels = malloc(nrows*sizeof(int*) + (nrows*(ncolumns*sizeof(int)));

to allow me then just map it somehow to my 1D array without copying memory?

---

EDIT: Thanks to @SamVarshavchik , the mapping seems to be working in the following way:

// Allocate 2-D array as one block:

// Allocate pointers:
int** labels = new int*[rows];
// Allocate data:
auto ptr=new int[rows*cols];

for(int i = 0; i < rows; i++) {
    labels[i] = &ptr[i*cols];
}

// fill with values ranging 0 to certain number
for(int i = 0; i < rows; i++){
    for(int j = 0; j < cols; j++){
        // the code for setting the values
        labels[i][j] = i+j;
    }
}    

// have int labels** as 2D array, also have rows and cols 

//create 1D array
int *labels1D; // = new int[rows*cols];

//assign contents:
labels1D = &labels[0][0];

The right way to destroy it in the library code seems to be

delete[] ptr;  //user2079303 fixed
delete[] labels;

Answer 1

So the first question is whether I can do something better here?

You could use std::vector to make the memory management safer and simpler. I don't see much else to improve.

The problem is that I need to send int * into another object (OpenCV Mat constructor) so I'm limited with exactly those types. Thanks anyway!

This is not a problem. You can use the data member function of vector, that returns a pointer to the internal array that you can send into your another project.

---

So the second question is: can I modify this code to make it allocate the 2D array in one memory block:

I'm assuming that you're bound to the interface that requires you to pass around int**.

If you can accept two allocations, that is simple: First allocate the array of pointers of appropriate size. Then allocate a flat array containing all values, and assign it to the first element of the pointer array. Then assign the rest of the pointers to correct positions of the value array.

A single allocation is possible, but tricky. You can allocate a raw char array big enough for both the array of pointers and the value array, and construct with placement new. This is tricky since it is very low level, and you must make sure that the arrays are aligned properly, and you must allocate extra space to make the alignment possible. This would be easier to implement in C which has aligned_alloc (which seems to be in the upcoming C++17 as well).

---

The right way to destroy it in the library code seems to be

delete ptr;
delete labels;

No, that seems to be the wrong way. The correct way to delete memory allocated with new[] is delete[].

Answer 2

You might get a bit of an improvement by using pointer arithmetic rather than array access.

We may use pointers to track our source and target and increment them on each pass of the loop, this way we save multiplications. Doing so with each involved pointer also has the advantage of removing the need for variable i, which saves all operations involving it, just need to compute the end pointer. Also checking for inequality is usually faster than a "less than" comparission.

//create 1D array
int *labels1D = new int[rows*cols];

//copy contents
int *targetPointer = labels1D;
int **sourcePointer = labels;
int *endTargetPointer = targetPointer + rows*cols;
while( targetPointer != endTargetPointer) {        
    std::copy_n(*sourcePointer++, cols, targetPointer );
    targetPointer += cols;
}

Though I would not be surprised if some optimizers are able to get code like this from OP's original code.