Moving from old C-style pointer to C++ smart pointers with little changes in the code?

Question

I have a function in which the nodes of a binary 'tree' are populated with values recursively computed based on the input vector, which represents the values on the leaves. An old C++ implementation of the function is as follows

using namespace std;

double f(const size_t h, vector<double>& input) {
    double** x;
    x = new double*[h+1];
    x[0] = input.data();

    for (size_t l = 1; l <= h; l++)
            x[l] = new double[1<<(h-l)];
    // do the computations on the tree where x[l][n] is the value 
    // on the node n at level l.


    result = x[l][0];

    for (size_t l = 1; l <= h; l++)
            delete[] x[l];

    delete[] x;

    return result;
}

Now I'm trying to write a 'modern' implementation of the code using smart pointers in C++11/C++14. I attempted to define x using std::unique_ptr specialization for arrays so that I do not have to change the 'computation' procedure. The obvious problem with such an approach is that the contents of `input' will be deleted at the end of the function (because the unique pointer that takes the ownership of the data will be destroyed at the end of the function).

One simple (and perhaps safe) solution would be to allocate the memory for the whole tree (including the leaves) in x and copy the values of the leaves from input to x[0] in the beginning of the function (in this case I can even used nested std::vectors instead of std::unique_ptrs specialized for arrays as the type of x). But I prefer to avoid the cost of copying.

Alternatively one can change the computational procedures to read the values of the leaves directly from input not from x which requires changing too many small pieces of the code.

Is there any other way to do this?

Answer 1

C++11/14 didn't really introduce anything that wasn't already achievable prior using the modern std::vector for managing the memory of dynamic arrays.

The obvious problem with [std::unique_ptr] is that the contents of `input' will be deleted at the end of the function

Indeed. You may not "steal" the buffer of the input vector (except into another vector, by swapping or moving). This would lead to undefined behaviour.

Alternatively one can change the computational procedures to read the values of the leaves directly from input not from x which requires changing too many small pieces of the code.

This alternative makes a lot of sense. It is unclear why the input vector must be pointed by x[0]. The loops start from 1, so it appears to not be used by them. If it is only ever referenced directly, then it would make much more sense to use the input argument itself. With the shown code, I expect that this would simplify your function greatly.

Also the fact that the input is not taken as const std::vector& bothers me.

This is another reason to not point to the input vector from the modifiable x[0]. The limitation can however be worked around using const_cast. This is the kind of situation what const_cast is for.

Let us assume henceforth that it makes sense for the input to be part of the local array of arrays.

One simple (and perhaps safe) solution would be to allocate the memory for the whole tree (including the leaves) in x ... I can even used nested std::vectors ... But I prefer to avoid the cost of copying.

You don't necessarily need to copy if you use a vector of vectors. You can swap or move the input vector into x[0]. Once the processing is complete, you can restore the input if so desired by swapping or moving back. None of this is necessary if you keep the input separate as suggested.

---

I suggest another approach. The following suggestion is primarily a performance optimization, since it reduces the number of allocations to 2. As a bonus, it just so happens to also easily fit with your desire to point to input vector from the local array of arrays. The idea is to allocate all of the tree in one flat vector, and allocate another vector for bare pointers into the content vector.

Here is an example that uses the input vector as x[0], but it is easy to change if you choose to use input directly.

double f(const size_t h, const std::vector<double>& input) {
    std::vector<double*> x(h + 1);
    x[0] = const_cast<double*>(input.data()); // take extra care not to modify x[0]

    // (1 << 0) + (1 << 1) + ... + (1 << (h-1)) == (1 << h) - 1
    std::vector<double> tree((1 << h) - 1);
    for (std::size_t index = 0, l = 1; l <= h; l++) {
        x[l] = &tree[index];
        index += (1 << (h - l));
    }

    // do the computations on the tree where x[l][n] is the value 
    // on the node n at level l.

    return x[l][0];
}

Answer 2

This certainly looks like a job for a std::vector<std::vector<double>>, not std::unique_ptr, but with the additional complexity that you conceptually want the vector to own only a part of its contents, while the first element is a non-owned reference to the input vector (and not a copy).

That's not directly possible, but you can add an additional layer of indirection to achieve the desired effect. If I understand your problem correctly, you want to behave x such that it supports an operator[] where an argument of 0 refers to input, whereas arguments > 0 refer to data owned by x itself.

I'd write a simple container implemented in terms of std::vector for that. Here is a toy example; I've called the container SpecialVector:

#include <vector>

double f(const std::size_t h, std::vector<double>& input) {

    struct SpecialVector {
        SpecialVector(std::vector<double>& input) :
            owned(),
            input(input)
        {}

        std::vector<std::vector<double>> owned;
        std::vector<double>& input;

        std::vector<double>& operator[](int index) {
            if (index == 0) {
                return input;
            } else {
                return owned[index - 1];
            }
        }

        void add(int size) {
            owned.emplace_back(size);
        }
    };

    SpecialVector x(input);

    for (std::size_t l = 1; l <= h; l++)
            x.add(1<<(h-l));
    // do the computations on the tree where x[l][n] is the value 
    // on the node n at level l.

    auto result = x[1][0];

    return result;
}

int main() {
    std::vector<double> input { 1.0, 2.0, 3.0 };
    f(10, input);
}

This approach allows the rest of the legacy code to continue to use [] exactly as it did before.

Answer 3

Write a class Row, which contains a flag for ownership controlling destruction behavior and implement operator[], then create a vector of row.

As noted above, you have issues if input is constant, as you cannot explicitly enforce it at compiler level, and you have to be careful not to write where you cannot, but this is not worse then what you have now.

I have not tried to compile it, but your new Row class could look a bit like this.

class Row
{
   double *p;
   bool f;
public:
   Row() :p(0), f(false) {}
   void init(size_t n) { p = new double[n]; f=true; }
   void init(double *d) { p=d;, f=false;}
   double operator[](size_t i) { return p[i]; }
   ~Row() { if (flag) delete[] p; }
};