tags:

views:

210

answers:

8

Possible Duplicate:
Segmentation fault on large array sizes

Hi all

I am trying to create a very big array in the VS 2010 using C++.

When I try to create a array like below

int dp[4501][4501]
or
int dp[1000][1000]

It threw an exception "Stack Overflow" Then I change it to:

int dp[100][100]

everything is fine.

So if I want to create a big array like above, what should I do?

Best Regards,

+4  A: 

Put it on the heap.

Marc Bollinger
Except don't directly use `new` nor `malloc`.
GMan
There's nothing explicitly wrong with them, especially at the level of understanding where this is aimed.
Marc Bollinger
@Marc, there is nothing explicity wrong with them, but "new int[4501][4501]" is wrong, which is what GMan meant.
Michael Aaron Safyan
@Marc: Using manual memory management is bad programming, wrap it up. `std::vector` exists for this purpose.
GMan
+3  A: 

You should use dynamic allocation:

typedef std::vector<int> int_vector;
int_vector dp(10000);

A double array can be simulated by nesting arrays:

typedef std::vector<int_vector> int_double_vector;
int_double_vector dp(4501, int_vector(4501));
GMan
I don't like typedef's used like this. Why? Simple: Your `int_array` is actually an *int* **vector**, and your `int_double_array` has nothing to do with a **double** at all. (Plus I have to do *two* lookups to find out what it actually is.) Bad style, IMHO. Use typedef's for really complex or cryptic things only, and even then only if their declarations are frequent throughout your code. (Iterators for maps of vectors of pairs, or function pointers spring to mind.) For declarations used but two or three times, they're a tool of obfuscation.
DevSolar
@Dev: I think you're reading way too into it. :) Happy? Double means two, and only coincidentally is the double-precision floating-point type called double, don't let that get in the way of English definitions. Code is for humans.
GMan
The wording int_double_vector _really_ sucks. You should do sth like 2d_int_vector instead. Other than that there is no problem with the typedef, it is hell better than working with a std::vector<std::vector<int> >::iterator...
ypnos
"double" in context of programming usually (and in context of "types in programming" almost exclusively) means "double precision floating point".
el.pescado
@ypnos: After 10 years of C++ maintenance coding, I actually much prefer code without a typedef in sight. Yes, that includes `std::vector< std::vector< int > >::const_iterator` and similar stuff. The ratio of useful typedefs vs. obfuscating ones is, in my experience, about 1 in 20.
DevSolar
+5  A: 

Use dynamic allocation or the STL. There was a recent thread about a very similar question. See this.

vpit3833
A: 

Your stack has overflowed with too many bits. You must drain them. Preferably onto a heap of other bits. I suggest /F67108864. The /F stands for "F'ing hell why is the stack so small compared to the heap?". The 67108863 is arbitrary.

John
We need tags for answers. Tags like *funny-but-wrong-approach*
Ben Voigt
A: 

If you want to avoid new[], or avoid using std::vector, make the array global. This will put the array on heap and stack overflow will not occur.

Donotalo
Please no global variables. There are infinitely many better solutions in this case (`vector` is not the only container class).
Philipp
@Philipp: global variables are useful in certain circumstances. And if you put global variable into namespace (or make a static global member in a struct or class), then there is absolutely nothing wrong with them. Another solution is to make variable (declared within function) static.
SigTerm
Global variables usually cause more problems than they solve. And they are definitely not a solution if all you want is heap allocation.
Philipp
I guess the OP is trying to solve some programming problem, where getting 'Correct' is everything. Coding like professional programmers is overkill for someone only willing to get his/her solution 'Correct'. Also, using containers instead of plain array will take more time to solve the problem. Once I had such problem. I used std::vector and got Time Limit Exceeded. I just replaced the vector with plain array and got my solution passed.
Donotalo
-1 for providing a "bad practice" solution.
Alexandre C.
I've mentioned why I've suggested using global. When you solve a problem from programming contest, you don't practice software engineering.
Donotalo
A: 

Your declaration looks a bit as if dp will be used as a matrix. In that case, a dedicated (dense) matrix class such as boost::numeric::ublas::matrix is the simplest solution, easier and more local than a vector of vectors. If the matrix is sparsely populated, use a sparse matrix class instead.

Philipp
A: 

So if I want to create a big array like above, what should I do?

Avoid using the stack for these cases (in other words, avoid creating arrays like these which aren't heap-allocated when working inside a function). Just to give you an idea, my thread-local stack is only 16 kilobytes large. 4501 * 4501 * 4 (assuming 4 bytes per int) = ~81 megabytes.

Consider something like this instead:

typedef vector<int> Row;
typedef vector<Row> Matrix;
Matrix dp(4501, Row(4501) );

If you want to create a 10x50 matrix:

Matrix dp(10, Row(50) );

You can use this just like your normal dp array had it not overflowed the stack. This one will be allocated and automatically deallocated to/from the heap so that you don't have to worry about stack overflow when using it.

dp[5][10] = 123;

Good luck!

[Edit] There are also matrix solutions in boost worth looking into but suggesting boost might be a bit premature given the nature of the topic.