Thread: Dynamically Allocated Multidimensional Array

Originally Posted by AndrewHunter

Umm...do you not click on any links? Multidimensional Arrays-C++ Click the thing in red, it has answered all these questions

Yes, in fact I do click the links and had already read the page. The only time it mentioned push_back() was here:

You can also do some interesting things with dynamic multi-dimensional arrays with vectors. For example, if you only allocate the first dimension, then use the .push_back() to add records to the 2nd dimension it's no longer a grid, but an array with a dynamically sized 2nd dimension (much like a street of buildings each with a different amount of floors). This functionality can be achieved using pointers, but is much harder to do.

Pardon my ignorance, but I can't deduce from here how to use push_back() with a 2D vector, and it gives no examples in the code. I also read from this link that:

A vector is, essentially, a resizable array; the vector class allows random access via the [] operator, but adding an element anywhere but to the end of a vector causes some overhead as all of the elements are shuffled around to fit them correctly into memory.

which leads me to believe that I should use push_back() instead of using [], or at least that it would be a lot easier. Are you saying that I can't or shouldn't use push_back()??? If not, please give me an example of how it can be used with a 2D array.

Originally Posted by LyTning94

Pardon my ignorance, but I can't deduce from here how to use push_back() with a 2D vector, and it gives no examples in the code.

What the article means is that you can have a vector of differently sized vectors, which you cannot do with a regular multidimensional array.

For example:

Code:

std::vector< std::vector<int> > array2D;

array2D.resize(100);
// array2D is a std::vector< std::vector<int> > that now contains
// 100 std::vector<int>s (each intialised with the default constructor)
	
array2D[0].push_back(1);
array2D[0].push_back(2);
array2D[0].push_back(3);
array2D[0].push_back(4);	
// array2D[0] is now an std::vector<int> that contains 4 elements

array2D[1].push_back(2);
array2D[1].push_back(2);
// array2D[1] is now an std::vector<int> that contains 2 elements

array2D[2].resize(20);
// array2D[2] is an std::vector<int> that contains 20 elements
// (each intialised with the default constructor)

array2D[3].resize(30);
// array2D[3] is an std::vector<int> that contains 30 elements
// (each intialised with the default constructor)

array2D[x].resize(y);
// array2D[x] is an std::vector<int> that contains y elelments

This means you can save on memory, if you don't intend to have a "grid", because you can have various differently sized vectors depending on your needs.

which leads me to believe that I should use push_back() instead of using [], or at least that it would be a lot easier. Are you saying that I can't or shouldn't use push_back()??? If not, please give me an example of how it can be used with a 2D array.

Using [] to access random elements is done in constant time, so you shouldn't have any additional overhead when simply accessing elements using [] with a vector. I think what the article means is that there may be additional overhead if you insert a new element in the middle of the vector, because the vector keeps each element in contiguous memory (which means if you insert a new element in the middle, it has to move some or all of the existing elements around in memory). push_back(...) places the element at the end of the memory block, so it shouldn't have to move everything around normally. I may be wrong about that though, so hopefully a more knowledgeable coder can confirm this for you.

Thanks for the help and the explanation. I think I understand everything that I need to know.