C++: Variable length multidimensional array

Question

I need a two dimensional array where the length of neither dimension is known at compile time. I want [][] access.

There are several questions about this already, suggesting boost::multi_array, std::vector<std::vector<type>>, allocating one array for the x dimension and X arrays for the y dimension, so on and so forth.

The catch is that I do not control the data, it already exists as a single contiguous array (size x*y). I have a pointer to it and the size of both dimensions, and I am more or less wrapping it to get [][] access.

I would like to avoid creating a whole bunch of objects (like allocating an array of std::vectors and pointing them all at the right things), and boost.

I considered creating a class to hold both dimensions and the pointer, and overloading [][], but that doesn't work because [][] is two operators, and the second [] applies to a different object.

Ultimately I'm looking for something that amounts to using [][] as syntactic sugar for some kind of access(int x, int y) function. Is that possible?

The main [] returns a proxy object that points to the original object and stores the first dimension, and whose [] takes the second dimension. — Neil Kirk, Aug 20 '14 at 11:21
I think I'm just gonna overload `operator()` rather than juggle a transient object. @Rapptz's link does answer the question, though, so this is definitely a duplicate. — Monchoman45, Aug 20 '14 at 11:48
[Howto](http://www.parashift.com/c++-faq/matrix-subscript-op.html) | [part two](http://www.parashift.com/c++-faq/matrix-array-of-array.html) | [part three](http://www.parashift.com/c++-faq/matrix-c-style-subscript.html) — n. m. could be an AI, Aug 20 '14 at 13:51

score 2 · Accepted Answer · answered Aug 20 '14 at 12:10

2

You may wrap it in a class and overload operator [], something like:

template <typename T>
class MultiArray
{
public:
    explicit MultiArray(T* arr, int sizex, int sizey) : data(arr), sizey(sizey) {}

    const T* operator [] (int x) const { return &data[x * sizey]; }
    T* operator [] (int x) { return &data[x * sizey]; }

private:
    T* data;
    int sizey;
};

Live example

answered Aug 20 '14 at 12:10

Jarod42

203,559
14
181
302

duplicate answer to a duplicate question. – MatthiasB Aug 20 '14 at 12:27
@MatthiasB: The *duplicate question* uses multiple arrays whereas OP has one unique 1D-array. – Jarod42 Aug 20 '14 at 12:33
This is a duplicate question, but it's not a duplicate answer. prem.baranwal suggests creating a pointer array as a proxy, whereas this suggests overloading one `operator[]` and letting the compiler handle the second `[]` normally. – Monchoman45 Aug 20 '14 at 12:34
Actually, the go-to question doesn't have this answer (one guy suggested it but didn't care to try it), so I'm going to accept this one because it's actually quite useful, since I'm only dealing with two dimensions. – Monchoman45 Aug 20 '14 at 12:38
@Monchoman45 then this should be merged, or added as improvement/edit into the answer in the original question. @Jaroj42 OP asks especially for double `[][]` operator, independend of 1d or 2d array. While the implementation is slightly different, the final structure is quite simmilar. So in my opinion, it is duplicate... – MatthiasB Aug 20 '14 at 12:42
Of course the implementation is slightly different but the final structure is similar. They're both trying to solve the same problem, and came to valid solutions. Isn't that the point? The major difference between the two is that this one requires `(Y + 1) * pointer_size` less memory, which is a pretty big difference. – Monchoman45 Aug 20 '14 at 12:51

score 0 · Answer 2 · answered Aug 20 '14 at 11:19

You need to have two classes DataTypeP and DataTypePP. While initializing DataTypePP, you will need to distribute the memory chunks to different DataTypeP references.

class DataTypeP {
    int *ptr;
public:
    int operator[](int y){ return ptr[y];}
};
class DataTypePP{
    DataTypeP  *bPtr;
public:
    DataTypeP  operator[](int x){ return bPtr[x];}
};

int main(){
    DataTypePP a;
    cout<<a[1][2];
    return 0;
}

Jaffa · Answer 3 · 2014-08-20T13:18:41.990

With a std::vector<std::vector<type*>>, you can build the inside vector using custom input operator that iterate over your data and return a pointer to each data.

For example:

size_t w, h;
int* myData = retrieveData(&w, &h);

std::vector<std::vector<int*>> data;
data.reserve(w);

template<typename T>
struct myIterator : public std::iterator<std::input_iterator_tag, T*>
{
    myIterator(T* data) :
      _data(data)
    {}
    T* _data;

    bool operator==(const myIterator& rhs){return rhs.data == data;}
    bool operator!=(const myIterator& rhs){return rhs.data != data;}
    T* operator*(){return data;}
    T* operator->(){return data;}

    myIterator& operator++(){data = &data[1]; return *this; }
};

for (size_t i = 0; i < w; ++i)
{
    data.emplace_back(myIterator<int>(&myData[i * h]),
        myIterator<int>(&myData[(i + 1) * h]));
}

Live example

This solution has the advantage of providing you with a real STL container, so you can use special for loops, STL algorithms, and so on.

for (const auto& i : data)
  for (const auto& j : i)
    std::cout << *j << std::endl;

std::cout << "or with index access: " << std::endl;

for (size_t i = 0; i < w; ++i)
  for (size_t j = 0; j < h; ++j)
    std::cout << *data[i][j] << std::endl;

However, it does create vectors of pointers, so if you're using small datastructures such as this one you can directly copy the content inside the array.

Doesn't this create Y + 1 `std::vector` instances? And it also looks like it's copying the entire original table. — Monchoman45, Aug 20 '14 at 12:49
No, it just copies pointer to the data, so here for ints it's useless but for more complex data this may be interesting. It creates W instances of std::vector containing H pointers. I haven't got a compiler here to test the code, but that should work and we can fix it if it doesn't ! — Jaffa, Aug 20 '14 at 12:57

C++: Variable length multidimensional array

3 Answers3