reviewstash

Everyone loves Bjarne's std::vector! Anyone who seriously believes that a two dimensional matrix is substantially more efficient than a properly managed std:vector is simply incorrect - I know, I've done the performance comparisons (it's hard for me to admit that). 

Here is a rundown of the basics required for implementing high-memory, expensive algorithms with the std::vector class:

//declaration
vector<vector<int> > myVector; 
//do not forget the space, it is to help the compiler distinguish
//between templates (generics) and multi-dimensional vectors

//initialization
myVector.resize(MY_ HEIGHT);
//setting the vector to your maximum intended size prevents
//expensive automatic resizing from occurring
//and reduces overhead immensely
for(int i = 0; i < MY_HEIGHT; ++i)
  myVector[i].resize(MY_WIDTH);
//we must initialize each vector's vectors

//function prototypes that use vectors
void myFunc(vector<vector<int> >& myVector);
//you really, really should pass by reference
//if you don't, you will recopy the entire std:vector on the heap
//doing so is a terrible idea
//another fun note - by default, C++ implicitly passes any array by reference

//manual deallocation (for champions)
//let's clear each of the i vector's vectors
for(int i = 0; i < MY_HEIGHT; ++i)
  myVector[i].clear();
//exit loop
//time to clear the i vectors
myVector.clear();
//you really don't need to worry about doing this if your std::vector is taken out of scope

As another note, a std::vector is a semi-managed data structure, so, while the size of the vector construct goes to the stack, all of the actual elements are stored on the heap for you.

It is important to make sure your data is being stored on the heap - the stack does not have enough space (only ~4 Kilobytes) to handle all of the information necessary.

Finally, I would seriously consider alternatives to an "int" primitive. A single int can hold 32 bits. If you are using unsigned, this is a maximum value of 2^32. Do you really need to store a value this large? For example, it is clear that: 32*100*100 >> 16*100*100. A program could be using 2 Gigabytes of memory, when it only really needs 1 Gigabyte!

For most implementation work, you might find the very cool uint8_t or uint16_t to be optimal. These are, of course, unsigned, but for most algorithms (besides negative weighted traversals), those two types are immensely useful. Sometimes (-2pow31) to (2pow31 - 1) clearly isn't what you need; 0 to 2pow16 is usually right on the money!