Automatically resizing arrays

I am implementing a sort of MATLAB-esque interpreter. I had asked a question in a previous thread about std::vector and apparently it's not really want I want.

In MATLAB, you can dynamically allocate arrays in a very poor and inefficient fashion, i.e.

a(54,34) = 4.5;

would allocate an array of that size and set the very bottom right corner to 4.5. You can further say

a(54,66) = 23532;

which would resize the array and set that value.

My question is, what would be the most efficient way to implement this? Right now I'm just thinking that it needs to allocate an array larger than the initial dimensions (create a reserve), and every time you go to set a value, through overloaded operations or whatever, it'll have to check to see if you're requesting a location outside of the reserve and possibly resize and copy the old data. If it's not outside the reserve size, increase the "size" variable of the array to match the new largest dimensions accessed.

I can't really think of a better way to do this. I'd like to avoid if statements for every time you want to set a value...but I don't think I'm going to get around it. Thanks in advance for any suggestions.

Quote:

---

I'd like to avoid if statements for every time you want to set a value...but I don't think I'm going to get around it.

---

There's no way around it.

You could use a std::vector of std::vector's, and resize as needed. That way the std::vector will handle memory allocation, re-allocation, etc. for you. The at() method will let you know when access is out of range.

Use these underneath ... judiciously:
Allocator (C++) - Wikipedia, the free encyclopedia

You want either a "sparse matrix" or a

Code:

---

std::map<std::pair<int, int>, int>

---

Quote:

---

Originally Posted by iMalc

You want either a "sparse matrix" or a

Code:

---

std::map<std::pair<int, int>, int>

---

---

The array might not be sparse though, the matrix might be full of actual data and then some idiot decides he wants to add an additional column.

Edit: This will mostly be for use with a 1-D array

If you don't use a sparse array (ie, add elements to every index), then use push_back.
Otherwise you can just add resize statements to resize the vector to the row/column you are currently going to assign. Not as convenient as Matlab, but tt isn't that complicated, at least.

Trying to copy MATLAB's behavior exactly. The problem with push_back AFAIK is that it only inserts a value at the end of the array. I need the ability to assign a value far far away.

You simply need a class with a method that allows you to read or write any cell, and which resizes upon out-of-bounds access. This is not hard. I was feeling generous so...

Code:

---

#include <vector>

template <typename T>
class growableMatrix
{
        std::vector<T> contents;
        size_t num_rows, num_cols;
public:
        growableMatrix(size_t rows=0, size_t cols=0) :
          contents(rows*cols), num_rows(rows), num_cols(cols)
        {}
        T &operator()(size_t row, size_t col)
        {
                if (row >= num_rows && col < num_cols)
                {
                        num_rows = row+1;
                        contents.resize(num_rows*num_cols);
                }
                else if (row >= num_rows || col >= num_cols)
                {
                        size_t new_num_rows = std::max(row+1, num_rows);
                        size_t new_num_cols = std::max(col+1, num_cols);
                        std::vector<T> new_contents(new_num_rows * new_num_cols);
                        for (size_t i = 0; i<num_rows; ++i)
                                for (size_t j = 0; j<num_cols; ++j)
                                        new_contents[i * new_num_cols + j] = contents[i * num_cols + j];
                        new_contents.swap(contents);
                        num_rows = new_num_rows;
                        num_cols = new_num_cols;
                }
                return contents[row * num_cols + col];
        }
        T operator()(size_t row, size_t col) const
        {
                if (row >= num_rows || col >= num_cols)
                        return T();
                return contents[row * num_cols + col];
        }
        size_t width() const { return num_cols; }
        size_t height() const { return num_rows; }
};


        // Example usage:
        growableMatrix<double> x;
        x(3, 4) = 12;
        x(4, 5) = 20;
        x(4, 8) = 32;
        x(6, 8) = 48;
        x(2, 7) = 14;

        assert(x(3, 4) == 12);
        assert(x(4, 5) == 20);
        assert(x(4, 8) == 32);
        assert(x(6, 8) == 48);
        assert(x(2, 7) == 14);

        const growableMatrix<double> &y = x;       
        assert(y(10, 99) == 0.0);
        assert(y(4, 8) == 32);
        assert(y.height() == 7 && y.width() == 9);

---

Heck I even tested it today.
Note that it does not support negative indexing, I assume this is not required. You'll note that I also added a const accessor that allows you to perform reads, even to coordinates which have never been written to, in which case you'll get back zero.

Lol, I didn't want someone to do it for me. I just wanted to make sure that the obvious solution is the most efficient solution. Thank you though.

Nevermind, you're welcome. It's not complete of course, it's lacking a swap method for starters. Sometimes the best way to describe a solution is to show rather than tell.

One of the main reasons I come here is to get inspired by mildly interesting problems that make me go "Hey I know a good way of doing that which would result in some nice reusable code".

Hmm, I also just noticed that if it weren't for lines 16 & 17, it would provide the strong exception safety guarantee. Lines 14-18 aren't really necessary anyway, they're just an optimisation I thought of that I'm not sure makes any significant difference. I'll fix my local copy, and might put it up on my site some time later.